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
Υπολογιστική γεωμετρία
- Διαφάνειες
- Graham-Scan
- Point in convex polygon σε O(logN): logNpointinpolygon.cpp
- Προβλήματα
Συμπληρωματικό υλικό
Προβλήματα εξέτασης
- 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.
Επιμέλεια: Νίκος Παπασπύρου, Δημήτρης Φωτάκης, Κυριάκος Αξιώτης, Μάκης Αρσένης, Μανώλης Ζαμπετάκης, Διονύσης Ζήνδρος, Βαγγέλης Κηπουρίδης, Βασίλης Νάκος, Σωτήρης Νικολουτσόπουλος, Γιώργος Παναγιωτάκος, Δημήτρης Τερζόπουλος, Γιάννης Χατζημίχος.