Trening
Den beste måten å trene på er å gjøre tidligere oppgaver. Ved å bruke treningsserverene vil du få besvarelsen automatisk rettet, akkurat som i de ordentlige konkurranserundene.
Aller først er det lurt å ha lest seg opp på oppgaveformatet for de ulike rundene.
Runde 1 har denne treningsserveren. Trykk “Trening” i menyen til venste. Når du går tom for tid blir løsninger tilgjengelige. Alternativt finnes noen tidligere oppgavesett fra da runde 1 var på papir. Det meste av algoritmisk tenking vil være trening til 1. runde, så hvis du går tom for treningsmateriale kan du gå over til runde 2-trening.
Runde 2 og finalen har denne treningsserveren. Løsningsforslag ligger på siden med tidligere oppgaver, men det er ytterst anbefalt å prøve selv på konkurranseserveren før man ser på løsningsforslag.
Resten av denne siden inneholder læringsressurser for konkurranseprogrammering i nio og videre.
Innhold
Programmeringsspråk
Fra runde 2 og oppover må man kunne programmere i enten C, C++, Python, eller Java.
Python
Språket som er lettest å lære. Det er enkel syntaks, og behagelig å jobbe med lister. All kode sjekkes mens den kjøres, så man får gode feilmeldinger når noe krasjer, men det ferdige programmet blir til gjengjeld mye tregere.
Java
Raskere enn Python, krever litt mer skriving, men koden
blir til gjengjeld veldig tydelig, med statiske typer.
Hvis du har skrevet noe feil kan det enten oppdages under kompilering,
eller bli en Exception
som kastes mens programmet kjører.
C/C++
På IOI er det kun C/C++ som er tillatt, siden det definitivt er raskest og mest populært. Det er til gjengjeld en god del vanskeligere å finne ut hva som har gått galt dersom du har bugs i koden. C++ har svært mye syntaks og funksjonalitet, så selv kompileringsfeil kan være vanskelige å tyde.
Python og Java kaster henholdsvis Error
s og Exception
s hvis du gjør noe ulovlig.
De forteller deg nøyaktig hvilken linje feilen skjer på, og hvordan programmet kom seg dit.
I C++ får du en Segmentation Fault
hvis du er heldig, ellers
skjer noe udefinert uten at du får noe advarsel om det.
C++ gir deg likevel mye bedre kontroll over datamaskinen,
og den kompilerte koden kjører rett på CPUen.
Ved å kjenne til noen verktøy, slik som valgrind
og gdb
,
kan du fikse feil i C++-koden raskere, og ende opp med
svært raske programmer.
Kom i gang med C++
For å lære C++ for konkurranseprogrammering er det lurt å ha et læreverk. For en god introduksjon til språket finnes C++ Made easy og C++ Langauge.
I konkurranser er det sjelden du får bruk for objektorientering og egne klasser, men å kunne bruke C++ sine innebygde klasser er svært praktisk. C++ har mange datastrukturer, se STL Tutorial.
Pensum
Fredrik Anfinsen har laget et glimrende kompendium som dekker mye av pensum til runde 2, finalen og internasjonale konkurranser.
Uansett hvilket programmeringsspråk du bruker er det veldig lurt å vite hvordan man enklest får satt opp og brukt disse datastrukturene:
- Dynamic array (vector)
- Queue
- Stack
- Set
- Map
- Priority Queue
Det er også kjekt vite hvordan du representerer rotfestede trær som noder med pekere mellom foreldre og barn.
For å representere generelle grafer bør du både kunne bruke nabomatriser, eller gi hver node en naboliste. Husk at kantene både kan ha retning og/eller vekter!
Når det gjelder algoritmer det kan være lurt å kunne, vil vi anbefale å ta en titt på innholdsfortegnelsen til kompendiet.
Hvordan lese input og skrive output
Uansett hvilket språk du velger blir input og output gjort gjennom
lesing fra stdin
og skriving til stdout
, slik man også gjør
når man skriver konsoll-programmer.
Oppgaveteksten oppgir alltid hvordan input er formatert, og hvordan du skal printe output. Skal du f.eks. ha desimaltall i output får du oppgitt hvor nøyaktige de minst må være. Hvis du er mer nøyaktig enn nødvendig går også det fint.
Python
Les inn linjer med input()
, skriv ut output med print()
.
Du kan også lese input med stdin.readlines()
, men merk at den beholder \n
-tegn på hver linje.
Java
Les inn input fra System.in
, for eksempel med Scanner
1 eller BufferedReader
.
Skriv ut output med System.out.println()
og lignende.
C++
Du kan bruke <cstdlib>
sin scanf()
for å lese inn tekst og tall fra input,
eller bruke <iostream>
sin std::cin >> x
og std::getline(cin, x)
2.
Printing av output gjøres via printf()
eller std::cout << x
.
Merk at alt som printes til std::cerr
ignoreres3.
Hvordan få programmet raskt nok?
Oppgavene i konkurransene er nesten alltid laget slik at en løsning som implementerer riktig algoritme har grei margin til tidsbegrensningen. Hvis tidsbegrensningen er 1 sekund, vil det tregeste testtilfellet gjerne ta et noen tidels sekunder.
Konkurransene handler altså ikke om å presse millisekunder ut av funksjonene sine, men å finne algoritmer som gjør at mengden arbeid datamaskinen må gjøre ikke er større enn nødvendig.
Det er fort gjort å forsøke å optimalisere bort en for-løkke, selv om det noen linjer nedenfor står to nøstede for-løkker som definitivt kommer til å ta mesteparten av kjøretiden.
Tenk derfor heller på antall operasjoner datamaskinen må gjøre, ikke om det er mulig å få noen av operasjonene til å kjøre noen prosent raskere.
Store O-notasjon
Når vi analyserer kjøretid til algoritmer bruker vi ofte Store O-notasjon. Den ser helt bort ifra kjøretiden per operasjon, eller nøyaktig antall operasjoner for en gitt input. Notasjonen forteller oss kun hvordan kjøretid vokser når størrelsen på input vokser.
Insertion sort har en gjennomsnittlig kjøretid i O(n^2)
.
Det betyr at en dobling av lengden til listen gir omtrent 4 ganger så lang kjøretid.
Vi sier at insertion sort har kvadratisk kjøretid.
En annen sorteringsalgoritme, merge sort, har kjøretid O(n log n)
.
Hvis vi dobler listelengden, gir det bare litt mer enn en dobling av kjøretiden.
Vi sier at merge sort har linearitmisk kjøretid.
Notasjonen forteller oss altså ikke hvor lang tid det vil ta å sortere en
liste med 100 000
elementer, men vi skjønner at for store n
vil merge sort være bedre.
Tommelfingerregler
En algoritme med kjøretid O(g(n))
tar maks C * g(n)
operasjoner,
for en eller annen konstant C
.
For insertion sort må denne settes minst så høyt som C = 1/2
.
En operasjon i insertion sort er å sammenligne to tall, bytte plass på dem hvis nødvendig, og lagre resultatet tilbake til minnet. I en idealisert modell er dette 4 CPU-instruksjoner, der hver instruksjon fullfører på én CPU-klokkesyklus.
La oss se hvordan dette går for insertion sort av en liste med n=100 000
elementer:
4 * 1/2 * 100 000^2 = 2*10^10
En moderne CPU har gjerne en klokkehastighet på 2 – 4 GHz, som betyr 2 – 4 milliarder sykler per sekund.
Det er altså ingen kjangs, selv med en svært idealisert CPU-modell, at listen vår vil være sortert på under ett sekund.
I mer kompliserte algoritmer er det vanskelig å finne en nedre grense for C
og telle antall klokkesykluser
per operasjon, men oftest fungerer tabellen under.
Den sier hva slags kjøretider du burde tenke på å sikte etter ved ulike input-størrelser n
.
n |
Kjøretid |
---|---|
10^6 | O(n) |
10^5 | O(n log n) |
1000 | O(n^2) |
200 | O(n^3) |
20 | O(2^n) |
10 | O(n!) |
Tabellen er laget ut ifra en antagelse om at konstanten C
ganget med antall CPU-sykler per operasjon
ikke er stort mer enn 1000.
Som regel vil dette produktet ligge godt under 1000, men hvis du f.eks. skriver i Python kan det øke mengden klokkesykluser med 10-100x. Hvis du gjør mye minneaksess på uavhenige deler av RAM, kan det alene ta 100 klokkesykler.
Hvis du skriver C++, og gjør svært lite arbeid per operasjon, f.eks. en kort for
-løkke
uten noen if
-setninger eller funksjonskall, som leser og skriver lineært til en sammenhengende blokk med minne,
kan den løkken godt kjøre 100 000 000 ganger.
Anbefalte bøker
-
Accelerated C++: Practical Programming by Example
Andrew Koenig og Barbara E. Moo – MIT Press
En god bok om C++-programmering som går rett på sak. -
Algoritmer og datastrukturer med eksempler i C og Java
Helge Hafting og Mildrid Ljosland – Gyldendal Akademisk / Stiftelsen Tisip
En fin innføring som dekker mye på relativt få sider, og som er ganske lettlest. -
Competitive Programming 2: This increases the lower bound of Programming Contests. Again.
Steven Halim og Felix Halim
Dekker alle nødvendige forkunnskaper til NIO/IOI og mer til fra et konkurranseperspektiv.
FAQ / Feilsøking
Under følger en liste med tips til hvordan du kan fikse feil som oppstår. Det vanligste er at konkurranseserveren kjører programmet ditt på testcasene i hver gruppe helt til en av dem feiler. Feilmeldingene du får er fra den første testcasen som mislyktes i sin gruppe.
Jeg får Time Limit Exceeded
Programmet brukte for lang tid uten å fullføre. Det er vanskelig å si nøyaktig hvilken del av programmet som er for treg.
Konkurranseserveren gir deg ofte kjøretiden til alle testene som ble kjørt. Her kan du se hvor fort andre testcases kjørte. Testcasen som ble tidsavbrutt kan også ha oppgitt kjøretid, trolig noen millisekunder over tidsbegrensningen. Dette er ikke fordi programmet ditt neste klarte testen, men fordi programmet ble avbrutt.
Det kan være lesing av input eller skriving av output som er for tregt.
I C++ kan det gå litt fortere å bruke kun printf()
og scanf()
eller kun cout
og cin
.
Dersom du vet at du kun bruker cout
og cin
bør du ta med disse linjne.
I Java bør du unngå Scanner
om du skal lese inn mye input.
Hvis det ikke er input og output er det nok algoritmen din som er for treg. Husk at de som lager testcases aktivt prøver å lage vriene cases, så tenk på algoritmen sin kjøretid i verste tilfelle.
Dersom du lager flere tråder blir kjøretidene til trådene lagt sammen, så det lønner seg som regel aldri å lage tråder.
Jeg får Execution failed because the return code was nonzero
Prosesser på linux returnerer 0 hvis de var vellykkede. Dersom en prosess i Python eller Java dør på grunn av en Error/Exception, vil prosessen avslutte med noe annet enn 0.
I C++ er returkode det tallet som returneres fra int main()
.
Det bør altså stå return 0;
i bunnen av main()
.
Jeg får Runtime error
eller Execution killed
Denne feilen tyder på at prosessen prøvde å gjøre noe ulovlig. I Java og Python er det vanskelig å få denne feilen, siden ulovlige handlinger blir til Exceptions og Errors.
I C++ derimot, er det ingenting som hindrer deg fra å lese vilkårlige minneaddresser, langt utenfor tabellen du egentlig prøver å lese fra.
Noen ganger leser man inn søppel, andre ganger forsøker man å lese fra et sted operativsystemet nekter, og man får denne feilen.
Andre feil, slik som å forsøke å dele på 0, kan også gi denne feilmeldingen.
Jeg får Compilation error
Koden du leverte kompilerer ikke på konkurranseserveren. Det står i menyen på konkurranseserveren hvilke parametere som brukes under kompilering, så pass på versjon av språket, og ikke bruk biblioteker som ikke er inkludert.
Jeg får Memory Limit Exceeded
Programmet forsøkte å allokere mer minne enn tillatt. Oppgavene har oppgitt en minne-grense, sammen med tidsbegrensing. En typisk grense er 512MB.
I C++ er det veldig lett å regne ut nøyaktig hvor mye minne
en tabell trenger. En int
er f.eks. 4 bytes, så en million ints blir 4MB.
I Python og Java er det overhead knyttet til verdier, så det er vanskeligere å beregne eksakt minnebruk.
-
Å bruke
Scanner
kan være veldig kjekt, særlig når man skal hente ut heltall mednextInt()
. Desverre erScanner
ganske treg, så hvis det er mye input (>100 000 tall) er det lurt å brukeBufferedReader
og manuelt kjøreInteger.parseInt()
ogFloat.parseFloat()
osv. ↩︎ -
Før du bruker
getline()
, Pass på at cin befinner seg på starten av linjen, og ikke på\n
-tegnet på linjen over. For å hoppe over ett tegn, brukcin.ignore()
. ↩︎ -
Du kan bruke
cerr
for å printe debug-output som blir ignorert, men pass på at det uansett bruker mye CPU å printe ting. ↩︎