Övning inför kvalen

Kul att du är taggad på att öva! Om du är helt ny rekommenderar vi att du börjar med introt.
Det enda sättet att bli bra på tävlingsprogrammering är att lösa väldigt många problem. Tyvärr har vi dock inte oändligt med tid, så man måste prioritera lite. Här är en lista av rekommenderade uppgifter för att öva inför kvalen. Vi ger inga garantier att dessa uppgifter kommer gå igenom alla tekniker som behövs för att kvala, eller ens är på nivån som krävs för att kvala. Det är dock en väldigt bra start!

Här finns ett gammalt dokument med problem. Det är inte jättefint, men innehåller mer än vad som finns på den här sidan.

Inom varje kategori kommer problemen vara i svårighetsordning.

Lätt

Läsa in och skriva ut data

Problem Lösningar
Hello World! Python C++
Äpplen och päron Python C++
Addition och subtraktion Python C++
Udda tal Python C++

Loopar

Problem Lösningar
Pelles armhävningar Python C++
N-summa Python C++

Standardfunktioner i programmeringsspråk

Det finns många problem som är väldigt vanliga, såsom “sortera en lista”. Det är vanligt att lösningarna för dessa problemen finns inbyggda som funktioner i programmeringsspråket. Att känna till och använda dessa funktioner sparar väldigt mycket tid.

Problem Lösningar
Omvändning Python C++

Brute force/simulering

Ibland handlar det helt enkelt om att testa alla alternativ eller att implementera det som problemet ber dig om. Dessa problem kännetecknas av lägre indatagränser. De flesta problemen här går att lösa mycket snabbare än vad som behövs. Försök inte skapa en bättre lösning än vad som efterfrågas!

Problem Lösningar
Lagomvinklade trianglar Python C++
Kylskåpstransport Python C++
Ramsan Python C++

Tidskomplexitet

Vad är det egentligen som gör att viss kod kör snabbt, och viss kör långsamt? Inom tävlingsprogrammering fokuserar vi främst på den så-kallade tidskomplexiteten av koden. För att förklara tidskomplexitet kommer vi att använda ett exempel. Läs först problemet Biosalong. Jämför sedan dessa två lösningar:

Även om båda har lika många rader kod, så är lösning B betydligt snabbare. Varför? Detta beror på att lösning A har en loop i en annan. Detta kommer leda till att koden i innerloopen kör N ⋅ N gånger. I lösning B finns det bara en loop, så koden i där inne kommer köras N gånger.
Som en tumregel klarar moderna datorer av 106 operationer per sekund i Python. I C++ klarar de ca 3 ⋅ 109 operationer.

För lätta algoritmer kan man alltså räkna hur många loopar man har i varandra för att få komplexiteten. Om man har 3 loopar i varandra blir det O(N3), och så vidare.
Att förstå tidskomplexitet är extremt viktigt, eftersom de flesta problemen i Programmeringsolympiaden går ut på att lösa problemet med bra komplexitet.

Problem Lösningar
Biosalong Python C++
Lagomvinklade trianglar (svårare) Python C++

Giriga algoritmer

Låt säga att vår algoritm måste fatta flera beslut. Giria algoritmer fattar alltid beslutet som är “bäst” just nu, utan att betrakta om det blir problem i framtiden. I vissa problem funkar det, men inte alla.
Exempel på ett problem där det funkar:

Du har N siffror mellan 1-9. Sätt ihop dessa för att få ett så stort tal som möjligt.
Exempelvis: du har siffrorna [1, 4, 4, 2, 7]. Största talet du kan få genom att sätta ihop de är 74421.

Lösning

Lösningen är att bygga upp vårt tal en siffra åt gången. Vi vill alltid ta den största siffran. Att alltid ta den största möjliga är den giriga delen av vår lösning. Så i exempelfallet, steg för steg:

  • Vi kan välja en av [1, 4, 4, 2, 7]. Vi väljer 7 eftersom den är störst.
  • Vi har nu talet 7 och kan välja mellan [1, 4, 4, 2]. Vi väljer 4 eftersom den är störst.
  • Vi har 74 och kan välja mellan [1, 4, 2]. Vi väljer 4.
  • Vi har 744 och kan välja mellan [1, 2]. Vi väljer 2.
  • Vi har 7442 och kan välja mellan [1]. Vi väljer 1.
  • Till slut får vi talet 74421.

Om det finns N siffror kommer vi att utföra O(N2) operationer: varje gång vi lägger till en siffra till vårat tal kollar vi igenom alla siffror. Vi lägger till N siffror, och för varje loopar vi igenom alla icke-tillagda: N ⋅ N = N2.

För att snabba upp det kan vi istället sortera alla sifrorna. Då behöver vi inte leta längre, utan bara skriva ut alla siffrorna! Sortering kör i O(Nlog(N)), en komplexitet som nästan alltid är snabb nog. Det är väldigt vanligt att sortera i giriga algoritmer.

Problem Lösningar
Stad i ljus Python C++
Lavapaddling Python C++
Tv-tittande Python C++

Rekursion

Ibland kräver ett problem att du systematiskt testar alla alternativ, men det är lite jobbigt att göra det. Det är väldigt vanligt att man kan plocka delpoäng genom att endast göra en ointelligent bruteforce! Det är extremt viktigt att kunna detta om du försöker satsa på att kvala genom skolkvalet, där “bruteforce-poängen” ofta är vad som skiljer finalister och icke-finalister.
Därför kommer målet på många av problemen nedan vara att plocka dessa delpoäng, inte att lösa dom fullt.

Kanske det lättaste sättet att systematiskt testa alla möjligheter är med hjälp av rekursion. TODO: länka till resurs.
Alla dessa problemen är gamla skolkvalsproblem.

Problem Kommentar Lösningar
Plocka äpplen Lös fullt Python C++
Kodlås Lös för 40 poäng Python C++
Bergskedja Lös för 40 poäng Python C++
Christians piano Lös för 20 poäng Python C++
Sifferkryptot Lös fullt Python C++
Sista moroten Lös för 40 poäng Python C++
Pickle clicker Lös T ≤ 10 Python C++

Avancerade tekniker

Om du vill lära dig om mer avancerade tekniker finns det ett flertal övningsproblem på Joshuas onlinedomare. Dessa är på landslagsnivå. Vi har inga bra lösningsförslag redo för dessa, men du kan fråga Matistjati på discord om hjälp.