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 Errors og Exceptions 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¹ 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)². Printing av output gjøres via printf() eller std::cout << x. Merk at alt som printes til std::cerr ignoreres³.

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.

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.