Programming competitions 2022/23 fall

Raamatuid ja muid materjale:

• Tennisberg, T., Gabrel, K. (2017, 2018) Võistlusprogrammeerimine. Lehel olevad lingid ülesannetele on TK kursuse vmt osa ja ei puutu otseselt meisse.
• Laaksonen, A. (2018) Competitive Programmer's Handbook
• Halim, S., Halim, F., Effendy, S. (2020) Competitive programming 4 ja selle varasemad versioonid (ei ole tasuta kättesaadav)
• CP-Algorithms
• Codeforces catalog. See on wiki-list praktiliselt kõikidest läbi aegade kirjutatud (kasulikest) Codeforces blogidest. Tuleb arvestada, et siin on väga erinevale lugejaskonnale suunatud materjale --- osad on algajatele, osad on sisuliselt teadusartikli tasemel.

Kursusel toetume esimesele (ja võib-olla pisut teisele) raamatule, ülejäänu on toodud laiemaks kontekstiks.

Praktikumide materjalid

• Praktikum 1: VP peatükk. Arvestuse saamiseks tuleb ära lahendada 3 tavaülesannet (ABCDE seast) või 2 lisaülesannet (XYZ seast) 27.09 õhtuks.
• Praktikum 2: VP peatükk. Arvestuse saamiseks tuleks lahendada 3 tavaülesannet (ABCD seast) või 2 lisaülesannet (XYZ seast) 04.10 õhtuks.
• Praktikum 3: VP peatükk (keerukus, punktid 3.1 kuni 3.3), VP peatükk (kahendotsing, punkt 2.5). Arvestuse saamiseks tuleks lahendada 2 tavaülesannet (ABCD seast) või 1 lisaülesanne (XY seast) 18.10 õhtuks.
• Praktikum 4: Arvestuse saamiseks 3 ülesannet 25.10 õhtuks.
• Praktikum 5: CPH, peatükk 15. Arvestuse saamiseks 2 tavaülesannet (ABC seast) või 1 lisaülesanne (XY seast) 08.11 õhtuks.
• Praktikum 6: VP peatükk, punkt 8.2. Arvestuse saamiseks tuleks lahendada 3 ülesannet 22.11 õhtuks.
• Praktikum 7: VP peatükk, punktid 11.4.1 ja 11.6. Arvestuse saamiseks tuleks lahendada kas A ja B või X 13.12 õhtuks.
• Praktikum 8: VP peatükk. Arvestuse saamiseks tuleks lahendada üks ülesannetest A ja B 20.12 õhtuks.

Mõned praktilised nõuanded programmeerimiskeelte osas

• Võistlusprogrammerimise industry standard on C++: selles kirjutatud programmid on kiired ja samas on C++ standardteek piisavalt suur. Kõikvõimalikud näited on samuti kõige suurema tõenäosusega C++-s. Kursusel on võimalik ja lubatud kasutada ka kõiki teisi programmeerimiskeeli, mida Codeforces kasutada võimaldab.
• Kursuse praktikumides ja harjutusvõistlustes on teatud keeltel pikem ajalimiit, mis peaks nendes keeltes võistlemise "ausamaks" tegema. Näiteks kui ülesande ajalimiit on 1 sekund, siis Java programmil rakendatakse ajalimiiti 1.5 sekundit ja Haskelli programmil 3 sekundit. Samas tuleb arvestada, et "päris" võistlustel sellist varianti üldiselt ei ole ja näiteks Pythoni kasutajad on tavaliselt ebaeelisseisus.
• Pythonis kirjutades on PyPy interpretaator sageli kiirem.
• Kui te kasutate C++ koodis sisendi-väljundi jaoks cin ja cout ning printf ja scanf ei kasuta, siis võib olla mõistlik panna programmi algusesse ios::sync_with_stdio(false). See võtab cin-cout ning printf-scanf omavahel sünkroonist välja, mis teeb sisendi-väljundi kiiremaks (samas ei tohi siis printf ega scanf kasutada, vastasel juhul võib väljund ekraanile ilmuda ebaloogilises järjekorras).
• Samuti on kasu programmi alguses cin.tie(0) kasutamist --- loe seletust siit.
• C++ (võistlusprogrammeerimise) koodis ei tasu reavahetuse jaoks kasutada võtmesõna endl. See tühjendab peale reavahetuse trükkimise iga kord väljundipuhvri. Kui seda teha palju kordi, teeb see väljundi trükkimise aeglaseks.