Camp προετοιμασίας 25ου ΠΔΠ

11-15 Μαρτίου 2013, Πολυτεχνειούπολη Ζωγράφου

Γενικά

• Πρόγραμμα διαλέξεων και εξετάσεων

---

Εισαγωγικά θέματα

• Προβλήματα υλοποίησης και brute force (junior)
  • Nearest Fraction (Codeforces 281B), λύση: 281b.c
  • Big Segment (Codeforces 242B), λύση: 242b.c
  • Books (Codeforces 279B), λύση: 279b.c
  • Shooshuns and Sequence (Codeforces 222a), λύση: 222a.c

Δομές δεδομένων

• Εισαγωγικά για δομές δεδομένων (junior)

  • Πίνακες
  • Λίστες
  • Ουρές και στοίβες
  • Χάρτες (maps) και δένδρα (trees), binary search tree (not balanced): bst.cpp

• Δομές δεδομένων και STL

  • Διαφάνειες
  • Παραδείγματα
  • STL best practice
  • Προτεινόμενο βιβλίο: The C++ Standard Library, A Tutorial And Reference
  • Πρόβλημα Γ' φάσης SOUND με set, λύση: sound.cpp

• Advanced data structures, διαφάνειες

  • Scrivener (IOI 2012), υλικό και testcases, λύση: scrivener.cpp
  • Binary indexed tree, πρόβλημα Increasing Subsequences, λύση: incseq.cpp
  • Segment Tree, πρόβλημα Can you answer these queries III, λύση: gss3.cpp
  • Segment Tree και Lazy Propagation, πρόβλημα Intervals, λύση: interval.cpp
  • Trie, πρόβλημα HERKABE
  • Square root trick: Josephus problem

Γράφοι

• Διάσχιση DFS, BFS, διαφάνειες, dfs-bfs-adjlist.cpp (junior)
  • Elevator Trouble (SPOJ ELEVTRBL), λύση: ELEVTRBL.cpp
  • Is it a Tree (SPOJ PT07Y), λύση: PT07Y.cpp
• Ελάχιστο συνδετικό δένδρο, διαφάνειες
• Συντομότερα μονοπάτια, διαφάνειες
  • Easy Dijkstra (SPOJ EZDIJKST), λύση: EZDIJKST.cpp και χωρίς τη χρήση STL: EZDIJKST-no-STL.cpp
• Εύρεση κύκλων και Bellman-Ford: bellman-ford.cpp
  • Millionaire

Υπολογιστική γεωμετρία

• Διαφάνειες
• Graham-Scan
• Point in convex polygon σε O(logN): logNpointinpolygon.cpp
• Προβλήματα
  • Sort by angle
  • Doors and Penguins: λύση: doorspen.cpp

Συμπληρωματικό υλικό

• Camp προετοιμασίας 2012
• Camp προετοιμασίας 2011

---

Προβλήματα εξέτασης

• FISHTANK (junior), λύση: fishtank.cpp, testcases: fishtank.tgz.
• KDIFF (senior), λύση: kdiff.cpp, testcases: kdiff.tgz.
• GOLFO (junior), λύση: golfo.cpp, testcases: golfo.tgz.
• GYMNAST (senior), λύση: gymnast.c, testcases: gymnast.tgz.
• CARMEET, λύση: carmeet.cpp, testcases: carmeet.tgz.
• NETWORK, λύση: network.cpp, testcases: network.tgz.

Τα test cases για όλα τα προβλήματα εξέτασης βρίσκονται στο Hellenico.

---

Επιμέλεια: Νίκος Παπασπύρου, Δημήτρης Φωτάκης, Κυριάκος Αξιώτης, Μάκης Αρσένης, Μανώλης Ζαμπετάκης, Διονύσης Ζήνδρος, Βαγγέλης Κηπουρίδης, Βασίλης Νάκος, Σωτήρης Νικολουτσόπουλος, Γιώργος Παναγιωτάκος, Δημήτρης Τερζόπουλος, Γιάννης Χατζημίχος.