Kas yra ACM ICPC?
ACM ICPC - kasmetinės studentų komandinės programavimo varžybos, kuriose varžosi komandos iš visų pasaulio universitetų. Komandą sudaro 3 studentai, kurie per 5 valandas turi išspręsti nuo 8 iki 12 uždavinių. Komandai yra skiriamas tik vienas kompiuteris.
Taisyklės
ACM ICPC taisyklės šiek tiek skiriasi nuo mokyklinių olimpiadų:
- Čia nėra dalinai išspręstų užduočių – programa turi praeiti visus testus, tik tada už ją bus duodami taškai.
- Sprendžiama komandomis po tris.
- Vienai komandai duodamas vienas kompiuteris. Pradžioje tai nesukelia daug problemų, nes kol vienas komandos narys kodina, kiti gali spręsti likusias užduotis. Sunkumų kyla konkurso pabaigoje, kai žinai uždavinio sprendimą, tačiau kompiuteris užimtas, o laiko ir beveik nėra.
- Konkursas trunka penkias valandas.
- Komandos rikiuojamos pagal išspręstų uždavinių skaičių.
- Jei kelios komandos turi vienodą išspręstų uždavinių skaičių, tai jos rikiuojamos pagal laiką. Laikas gaunamas susumavus kiekvieno išspręsto uždavinio sprendimo trukmę ir baudos minutes. Pavyzdžiui, jei komandai pavyko išspręsti uždavinį A per 15 minučių nuo konkurso pradžios ir uždavinį B per 65 minutes nuo konkurso pradžios bei buvo išvengta baudos minučių, tai jos bendras laikas yra 15 + 65 = 80. Už neišspręstus uždavinius laikas neskaičiuojamas.
- Baudos minutės skaičiuojamos tik išspręstiems uždaviniams. Už kiekvieną bandymą, kuris neįvykdė visų testų, pridedama po 20 baudos minučių. Pavyzdžiui, jei komanda iš šešto bandymo (tai yra, penki bandymai buvo nesėkmingi) išsprendė uždavinį A, bet po 10 bandymų taip ir nepavyko išspręsti uždavinio B, tai ji gaus 5 * 20 = 100 baudos minučių.
- Dažniausiai leidžiamos programavimo kalbos — C, C++, Java. Retais atvejais galimi ir kiti variantai.
- Užduotys pateikiamos anglų kalba.
Žodynėlis
- AC (accepted) — programa tilpo į nustatytus laiko ir atminties apribojimus bei išvedė teisingus rezultatus.
- WA (wrong answer) — programa tilpo į nustatytus laiko ir atminties apribojimus, bet išvedė neteisingus rezultatus. Pagrindinis galvos skausmo sukelėjas.
- TLE (time limit exceeded) — programa netilpo į laiko apribojimus. Galimybės dvi: pasirinktas nepakankamai spartus algoritmas; algoritmas tinkamas, tačiau neoptimaliai implementuotas.
- MLE (memory limit exceeded) — programa netilpo į atminties apribojimus.
- RE (runtime error) — programa nulūžo vykdymo metu. Didžiausia tikimybė, kad kažkur išeita už masyvo ribų arba netinkamai elgiamasi su dinamine atmintimi.
- PE (presentation error) — rezultatai išvedami netinkamu formatu (nereikalingi tarpai, neteisingai išdėstytos eilutės). Itin retai sutinkamas, o moderniose vertinimo sistemose iš vis negalimas.
- DP (dynamic programming) — dinaminio programavimo algoritmas.
- Ad hoc (lotyniškai „šiam tikslui“) — taip apibūdinamas algoritmas, tinkamas spręsti būtent pasirinktai užduočiai. Tokie algoritmai nepatenka į jokias algoritmų klasifikavimo kategorijas.
Liaudies išmintis
- Protingiausia uždavinius spręsti iš eilės pagal sudėtingumą — nuo lengviausio iki sudėtingiausio.
- Jeigu nežinai, kuris uždavinys lengviausias, užmesk akį į rezultatų lentelę. Daugiausia kartų išspręstas uždavinys, tikėtina, bus ir lengviausias.
- Jei manai, kad žinai, kaip spręsti pasirinktą uždavinį, bet rezultatų lentelėje niekas kitas jo dar neišsprendė, pamąstyk, ar tavo sugalvotas algoritmas iš tiesų bus teisingas.
- Dinaminės atminties griebkis tik tuo atveju, jei tikrai gerai moki ja naudotis arba jei su statine atmintimi nepavyktų išspręsti uždavinio.
- Kuo mažiau
if
'ų, tuo mažesnė tikimybė įvelti klaidą. - Į
int
telpa skaičiai nuo −231 iki 231−1 (apytiksliai [−2⋅109; 2⋅109]). Jei to neužtenka, naudokislong long
(taip, būtina parašyti dukart) – nuo −263 iki 263−1 (apytiksliai [−9⋅1018; 9⋅1018]). - Globalūs kintamieji yra blogis. Bet jie gali palengvinti kodo rašymą, todėl pravartu juos naudoti.
- Komentarų niekas neskaito. Jei matai, kad komandos narys nesupranta tavo kodo, paaiškink jam žodžiu.
- Nežinai, ar tavo sugalvotas algoritmas tilps į laiką? Įsistatyk pradinius duomenis į algoritmo sudėtingumo lygtį O(...) (didžiosios O notacija) ir žiūrėk, ar gautas skaičius neviršija 50 mln. operacijų.
- Atsibodo tūkstantį kartų rašyti
long long
? Įterpk eilutętypedef long long ll;
ir toliau kintamuosius galėsi kurti sull variableName = 0;
(tinka ir kitiems tipams). - Nemėgsti testinių duomenų vesti iš klaviatūros, bet moki paleisti programą iš komandinės eilutės? Naudok I/O redirection:
$ program.exe < input_file.txt
. - Algoritmo implementavimo sudėtingumas lygiai toks pats svarbus kaip ir laiko ir atminties sąnaudos. Jei du algoritmai — vienas lėtesnis, kitas greitesnis — gali išspręsti uždavinį, visada pasirink tą, kuris lengviau implementuojamas.
- Jeigu gali greitai parašyti algoritmą, kuris telpa į laiką tik su mažomis įvestimis, taip ir padaryk. Kartais užtenka pažiūrėti į rezultatus su mažiausiais duomenimis, kad atrastum dėsningumą ir žinotum atsakymą likusioms įvestims.
- Kartais paprasčiau spėti sprendinį ir patikrinti, ar jis tinkamas, negu jį apskaičiuoti. O spėliojant kai kada praverčia dvejatainė paieška.
ios::sync_with_stdio(false)
paspartins tavostd::cin
irstd::cout
, tačiau tada negalėsi kartu naudotiscanf()
irprintf()
.scanf()
irprintf()
yra kur kas greitesni užstd::cin
irstd::cout
. Jei duomenų kiekis artėja prie 106, verta apsvartyti šį spartos skirtumą. Kartais pakeitimas vieno į kitą gali reikšti AC vietoj TLE. (Jei duomenų nuskaitymas neužima daug laiko, kur kas saugiau pasirinktistd::cin
irstd::cout
).
Literatūra
Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai[1] (nuoroda į knygą) — šią knygą būtina perskaityti dar mokykloje (mokytoja man ją įteikė, kai dešimtoje klasė praėjau mokyklos (ar miesto, dabar neprisimenu) etapą). Puikus įvadas į algoritmo sudėtingumo nustatymą, grafus bei į keletą elementarių, bet fundamentalių algoritmų.
Competitive programming[2] (nuoroda į knygą) — taip pat stipriai rekomenduoju perskaityti. Ši knyga labiau atitinka universitetinio lygio konkursuose sutinkamas užduotis.
topcoder Algorithm Tutorials (nuoroda) — galima rasti algoritmų ir duomenų struktūrų, retai sutinkamų kitoje literatūroje, tačiau labai praverčiančių konkursuose. Pravartu užmesti akį į geometriją, nes čia ji tinkama panaudojimui kompiuteryje (o ne matematikos sąsiuvinyje).
Matematikos knyga[3] (nuoroda į knygą) — nors ir parašyta „Matematikos“, bet tinka ir informatikai. Verta atkreipti dėmesį į skyrius apie modulių aritmetiką (ypač 1.2, 1.3) ir kombinatoriką (3 skyrius). Taip pat geometrijos supratimas nepakenks.
C++ STL (standard template library) (nuoroda į puslapį) — visos standartinės duomenų struktūros jau seniai implementuotos, tereikia mokėti jomis pasinaudoti. Atkreipti dėmesį į vector
, list
, set
ir map
klases.
C++ <algorithm> (STL algorithms) (nuoroda į puslapį) — fundamentalūs algoritmai taip pat yra implementuoti. Būtinas įrankis prie STL konteinerių. Mažų mažiausiai reikia mokėti naudotis sort()
metodu.
Introduction to Algorithms[4] (nuoroda į knygą) — visiškai pakvaišusiems dėl algoritmų. Kadangi ši knyga yra ne itin orientuota į programavimo konkursus, rekomenduočiau pirmiau atkreipti dėmesį į auksčiau paminėtus šaltinius.
- ^ PETRAUSKAS, Linas; SKŪPIENĖ, Jūratė. Informatikos olimpiados: algoritmai ir taikymo pavyzdžiai. Vilnius: Nacionalinė Moksleivių Akademija, 2006. 234 p. ISBN 9955-9894-0-8.
- ^ HALIM, Steven; HALIM, Felix. Competitive Programming. Lulu, 2010. 152 p.
- ^ JURONIS, Vaidotas, et al. Matematikos knyga. Creative Commons, 2011. 233 p.
- ^ CORMEN, Thomas H., et al. Introduction to Algorithms. Cambridge: The MIT Press, 2009. 1312 p. ISBN 0262-0338-4-4.