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

Hvis det er første gang du deltar i programmeringkonkurranser der du leverer programmer, har vi en egen side for min første runde 2-oppgave.

Resten av denne siden inneholder en oversikt over tillatte språk, anbefalte læringsressurser for konkurranseprogrammering i nio og videre, samt en liten FAQ med spørsmål, og vanlige feil som kan oppstå.

Innhold

Programmeringsspråk

Fra runde 2 og oppover må man kunne programmere i enten C, C++, Python, Java eller Rust.

Python

Python er språket som er lettest å lære. Det er enkel syntaks, og behagelig å jobbe med lister. All kode sjekkes mens den kjøres, så mange bugs vil bli fanget opp og stanse programmet. Når du tester programmet ditt lokalt får du feilmeldinger som forteller hvor og hvorfor programmet krasjet. Det ferdige programmet blir til gjengjeld mye tregere, enn tilsvarende programmer skrevet i andre språk.

Java

Java er raskere enn Python, men krever litt mer skriving. 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. Når du tester programmet lokalt vil en Exception fortelle hvor i programmet problemet oppsto.

C/C++

Når vi sier C/C++ mener vi i praksis C++, siden det har et mye større standardbibliotek, med innebygd funksjonalitet for å jobbe med lister, mengder, køer osv.

På IOI er det kun C++ som er tillatt, som er det desidert mest populære språket. Ved å skrive i C++ blir programmet kompilert til maskinkode, så den samme algoritmen vil kjøre raskere i C++ enn i Python og Java. 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.

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 om 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, lenket til under, går gjennom mange av C++ sine innebygde datastrukturer.

Rust

Det er nå også mulig å bruke Rust i runde 2 og finalen, for de som ønsker det. Rust er et kompilert språk, slik som C og C++, og vil derfor kunne være like raskt. I tillegg vil kompilatoren utføre sjekker som gir visse garantier om minnesikkerhet, som reduserer mulighetene for bugs.

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 (også kjent som liste eller 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.

Siden min første runde 2-oppgave viser en gjennomgang av en oppgave, inkludert håndtering av input og output. Resten av denne seksjonen har noen tips for ulike språk.

Python

Les inn linjer med input(). Husk å ikke inkludere noe tekst, slik som input("Skriv inn N: "), siden det vil printes ut som output. Husk at input() gir strenger og ikke tall, så bruk int(input()) for å lese inn tall.

Merk videre at input() leser en hel linje av gangen, så hvis oppgaven spesifiserer at flere tall kommer på samme linje må man gjøre noe à la

# Leser inn én linje med to heltall N og M
N, M = map(int, input().split())

Noen ganger får du derimot oppgitt at det kommer N antall tall på én linje, hvor du får N fra input. Da kan du lese input slik:

# Leser først inn N, og så én linje med N tall
N = int(input())
liste = [int(i) for i in input().split()]

Du kan også bli bedt om å lese N linjer med tall, da kan du bruke en for-loop som dette:

# Leser inn N, og så leser N linjer med ett tall på hver
N = int(input())
tall = [0]*N # Lager en liste av lengde N fylt med 0

for i in range(N):
  tall[i] = int(input()) # Setter inn input i lista i rekkefølgen det kom

Hvis du blir bedt om å skrive ut et desimaltall med minst 6 desimaler, kan du bruke

print(f"{tall:.6f}")

Java

Les inn input fra System.in, for eksempel med Scanner[^scanner] eller BufferedReader. Skriv ut output med System.out.println() og lignende.

Å bruke Scanner kan være veldig kjekt, særlig når man skal hente ut heltall med nextInt(). Desverre er Scanner ganske treg, så hvis det er mye input (> 100 000 tall) er det lurt å bruke BufferedReader og manuelt kjøre Integer.parseInt() og Float.parseFloat() osv.

C++

For å lese input kan du bruke <iostream> sin std::cin >> x og std::getline(cin, x)¹. Printing av output gjøres via std::cout << x. Merk at alt som printes til std::cerr ignoreres².

Du kan også bruke C sine IO-funksjoner ved å inkludere <cstdlib>. Da bruker du scanf() for å lese inn tekst og tall fra input, og printf() for å printe.

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

Et enkelt program 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 Output isn't correct

Programmet ditt printet ut en output som ikke samsvarer med fasit.

Pass først av alt på at output faktisk printes ut, og at ingenting er feilstavet.

Hvis du skal printe ut desimaltall, pass på at du tar med nok desimaler i output, og at svaret ikke rundes av for deg.

Hvis ingenting slikt ser feil ut, er det sannsynlig at du enten har en bug i koden, eller at algoritmen du har tenkt ut ikke svarer på oppgaven.

Dersom du skal printe ut tall, pass på at variablene du har brukt i programmet ditt har plass til å lagre tallene du jobber med, også når testinput blir veldig stor. En vanlig tabbe i C++ og Java er å bruke int et sted der tall kan bli høyere enn 2^31, og da får man problemer. Bruk long long i C++, og long i Java, hvis svar eller mellomregninger kan bli større enn 2^31.

Det er generelt et godt råd å prøve å lage sin egen testinput, og se om programmet printer slik man forventer.

Jeg får Execution timed out / Time limit exceeded

Programmet ditt 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 linjene.

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.

Eksempler på ting som kan få denne feilmeldingen:

• Å bruke indekser utenfor størrelsen på en liste.
• Å hente ut nøkler som ikke finnes i en dict.
• Å bruker variabler som ikke er definert enda.
• Å dele på 0.
• Å importere noe du ikke har lov til.
• Å nå maksgrensen for rekursjon³.

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.

For å debugge C++ har vi skrevet litt om de verktøyene du har til rådighet under finalen, og under internasjonale konkurranser. Eksempler på bruk står nevnt under finalemaskiner

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.