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. Disse verktøyene vil være tilgjengelige på konkurransemaskiner, men du må bruke dem fra terminalen. Les litt om hvordan på siden finalemaskiner.

Kom i gang med C++

For å lære C++ er det lurt å ha et læreverk. For en god introduksjon til språket finnes C++ Made easy og C++ Langauge.

Kompendiet til CSES går gjennom mange av C++ sine innebygde datastrukturer.

Pensum

Fredrik Anfinsen har laget et glimrende kompendium som dekker mye av pensum til runde 2, finalen og internasjonale konkurranser. Den har også lenker til oppgaver du kan prøve på selv, i slutten av kapitlene.

En annen gratis pdf som går gjennom enda mer er CSES’s Competitive Programmer’s Handbook. Den er på engelsk, og betraktlig lengere, men inneholder blant annet introduksjoner til de ulike datastrukturene vi bruker i C++.

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

Du må også kunne representere grafer og rotfestede trær.

For en fin oversikt over hva det er lurt å kunne, vil vi anbefale å ta en titt på innholdsfortegnelsen til kompendiet til Fredrik Anfinsen. Hvis du har kontroll på alle dem, kan innholdsfortegnelsen til CSES være lur å kikke på.

Og husk: Øv ved å gjøre oppgaver!

Anbefalte bøker

Husk at de to kompendiene nevnt i Pensum er gratis, godt skrevet, og veldig lure å gå gjennom.

Hvis du heller vil ha en bok, kan vi anbefale:

• 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.

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 linjeskift-tegnet på slutten av 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 være flere tidels sekunder innenfor.

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øretiden 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. Dette kalles asymptotisk kjøretid.

Hvis en sorteringsalgorime har en kjøretid på O(n^2), betyr det følgende:

n er antall elementer i listen som skal sorteres. Vi ser bort ifra veldig små lister, siden vi vil at listens størrelse skal dominere kjøretiden. Antall operasjoner som brukes for å sortere listen er maks C ganget med n^2. Vi vet ikke hva C er, men vi vet at den ikke endrer seg for større verdier av n.

Dette forteller oss:

• Å sortere 1000 elementer tar maks C * 1000^2 = 1 000 000 * C operasjoner.
• Å sortere 2000 elementer tar maks C * 2000^2 = 4 000 000 * C operasjoner.

Med en dobbelt så lang liste kan vi altså risikere rundt 4 ganger så lang kjøretid. Vi sier at kjøretiden er kvadratisk. Sammenlign dette med O(n), der en dobbelt så lang liste vil ta omtrent dobbelt så lang tid, også kjent som lineær kjøretid.

Du kan lese mye mer om Store O-notasjon i kompendiene lenket til i pensum, men her følger en kjekk tabell som indikerer hva slags asymptotisk kjøretid du burde satse på, gitt oppgavetekstens opplysinger om maksimal inputstørrelse.

Tabellen er laget ut ifra en antagelse om at konstanten C ganget med antall CPU-sykler per operasjon ikke er stort mer enn 1000, og at tidsbegrensningen på oppgaven er 1 sekund. En moderne CPU kjører 2-4 milliarder CPU-sykler i sekundet.

Hvis du skriver i Python, eller gjør veldig mye arbeid per operasjon, er det ikke sikkert tabellen over virker, og programmet kan være for tregt.

Programmet kan også være overraskende raskt. 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 faktisk kjøre 100 000 000 ganger i sekundet.

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.