Ö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. Här är en prioriterad lista av rekommenderade uppgifter för att öva inför kvalen. Inom varje kategori är problemen 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++ |
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å tidskomplexiteten. Läs först problemet Biosalong nedan och 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. Lösning A har en loop inuti en annan loop, vilket leder till att koden i innerloopen kör $N \cdot N$ gånger. I lösning B finns det bara en loop, så koden körs $N$ gånger.
Tumregel: Moderna datorer klarar av ca $10^6$ operationer per sekund i Python (ca $3 \cdot 10^9$ i C++). Lösning B utför $O(N)=10^6$ operationer (snabbt nog), medan lösning A utför $O(N^2)=10^{12}$ operationer (för långsamt).
Giriga algoritmer
Giriga algoritmer fattar alltid beslutet som är "bäst" just nu, utan att betrakta om det blir problem i framtiden. Det är väldigt vanligt att man sorterar datan först i giriga algoritmer för att snabba upp processen.
Du har $N$ siffror mellan 1-9 (t.ex. [1, 4, 4, 2, 7]). Sätt ihop dessa för att få ett så stort tal som möjligt.
Bygg upp talet en siffra åt gången. Ta alltid den största siffran (detta är det "giriga" valet):
- Välj största av
[1, 4, 4, 2, 7]→ 7 - Välj största av
[1, 4, 4, 2]→ 74 - Och så vidare tills du får → 74421
Istället för att söka igenom listan varje gång ($O(N^2)$), kan vi sortera siffrorna först ($O(N \log N)$) och bara skriva ut dem!
| Problem | Lösningar | ||
|---|---|---|---|
| Stad i ljus | Editorial | Python | C++ |
| Lavapaddling | Editorial | Python | C++ |
| Tv-tittande | Editorial | Python | C++ |
Rekursion & Bruteforce
Ibland kräver ett problem att du systematiskt testar alla alternativ. 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. Det lättaste sättet att systematiskt testa alla möjligheter är med hjälp av rekursion. Målet på många av problemen nedan är att plocka dessa delpoäng, inte att lösa dom fullt.
| Problem | Mål | Lösningar | ||
|---|---|---|---|---|
| Plocka äpplen | Lös fullt | Editorial | Python | C++ |
| Kodlås | 40 poäng | Python | C++ | |
| Bergskedja | 40 poäng | Python | C++ | |
| Christians piano | 20 poäng | Python | C++ | |
| Sifferkryptot | Lös fullt | Python | C++ | |
| Sista moroten | 40 poäng | Python | C++ | |
| Pickle clicker | 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å absolut landslagsnivå.
Till LandslagsarkivetVi har inga bra lösningsförslag redo för dessa, men du kan fråga Matistjati på discord om hjälp.