Ö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:

• Lösning A
• Lösning B

Ä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 10⁶ operationer per sekund i Python. I C++ klarar de ca 3 ⋅ 10⁹ operationer.

• Lösning B utför då O(N) = O(10⁶) = 10⁶ operationer, vilket är snabbt nog
• Lösningar A utför O(N²) = O((10⁶)²) = 10¹² operationer, vilket är för långsamt

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(N³), 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	Editorial	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:

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(N²) 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 = N².

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	Editorial	Python	C++
Lavapaddling	Editorial	Python	C++
Tv-tittande	Editorial	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	Editorial	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.