# Ö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](https://progolymp.se/intro/).
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](https://docs.google.com/document/d/1JEfHGaxCCZ9pkayjQmvPIzWA7yOikPNDhUyMT_x76kg/edit?usp=sharing) 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!](https://po.kattis.com/problems/helloworld) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/helloworld.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/helloworld.cpp) |
| [Äpplen och päron](https://po.kattis.com/problems/applenparon) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/applenparon.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/applenparon.cpp) |
| [Addition och subtraktion](https://po.kattis.com/problems/additionochsubtraktion) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/additionochsubtraktion.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/additionochsubtraktion.cpp) |
| [Udda tal](https://po.kattis.com/problems/uddatal) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/uddatal.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/uddatal.cpp) |

## Loopar

| Problem | Lösningar | |
|-------|---------|---------|
| [Pelles armhävningar](https://po.kattis.com/problems/pellesarmhavningar) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/pellesarmhavningar.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/pellesarmhavningar.cpp) |
| [N-summa](https://po.kattis.com/problems/nsum) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/nsum.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/nsum.cpp) |

## 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](https://po.kattis.com/problems/reverse) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/reverse.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/reverse.cpp) |

## 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](https://po.kattis.com/problems/lagomvinklade) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/lagomvinklade.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/lagomvinklade.cpp) |
| [Kylskåpstransport](https://po.kattis.com/problems/kylskap) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/kylskap.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/kylskap.cpp) |
| [Ramsan](https://po.kattis.com/problems/ramsan)| [Python](https://github.com/Kodsport/po-solutions/blob/main/python/ramsan.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/ramsan.cpp) |

## 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](https://po.kattis.com/problems/biosalong). Jämför sedan dessa två lösningar:

- [Lösning **A**](https://github.com/Kodsport/po-solutions/blob/main/python/biosalong_slow.py)
- [Lösning **B**](https://github.com/Kodsport/po-solutions/blob/main/python/biosalong.py)

Ä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 \cdot 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^6$ operationer per sekund i Python. I C++ klarar de ca $3 \cdot 10^9$ operationer.

- Lösning **B** utför då $O(N)=O(10^6)=10^6$ operationer, vilket är snabbt nog
- Lösningar **A** utför $O(N^2)=O((10^6)^2)=10^{12}$ 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^3)$, 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](https://po.kattis.com/problems/biosalong) | [Editorial](https://github.com/Kodsport/po-solutions/blob/main/editorial/biosalong.pdf) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/biosalong.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/biosalong.cpp) |
| [Lagomvinklade trianglar (svårare)](https://po.kattis.com/problems/lagomvinkladehard) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/lagomvinkladehard.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/lagomvinkladehard.cpp) |

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

<div class="alert alert-info">

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

<details>
<summary>Lösning</summary>

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^2)$ 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 \cdot N=N^2$.

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.

</details>

| Problem | Lösningar | | |
|-------|---------|---------|---------|
| [Stad i ljus](https://open.kattis.com/problems/stadiljus) | [Editorial](https://github.com/Kodsport/po-solutions/blob/main/editorial/stadiljus.pdf) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/stadiljus.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/stadiljus.cpp) |
| [Lavapaddling](https://po.kattis.com/problems/lavapaddling) | [Editorial](https://github.com/Kodsport/po-solutions/blob/main/editorial/lavapaddling.pdf) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/lavapaddling.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/lavapaddling.cpp) |
| [Tv-tittande](https://po.kattis.com/problems/tvtittande2) | [Editorial](https://github.com/Kodsport/po-solutions/blob/main/editorial/tvtittande.pdf) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/tvtittande2.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/tvtittande2.cpp) |

## 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](https://po.kattis.com/problems/apples) | Lös fullt | [Editorial](https://github.com/Kodsport/po-solutions/blob/main/editorial/apples.pdf) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/apples.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/apples.cpp) |
| [Kodlås](https://po.kattis.com/problems/kodlas) | Lös för 40 poäng | [Editorial](https://github.com/Kodsport/po-solutions/blob/main/editorial/kodlas.pdf) | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/kodlas-40p.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/kodlas-40p.cpp) |
| [Bergskedja](https://po2punkt0.kattis.com/problems/bergskedja2) | Lös för 40 poäng | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/bergskedja2-40p.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/bergskedja2-40p.cpp) |
| [Christians piano](https://po2punkt0.kattis.com/problems/pianot) | Lös för 20 poäng | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/pianot-20p.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/pianot-20p.cpp) |
| [Sifferkryptot](https://po2punkt0.kattis.com/problems/poskola23.sifferkryptot) | Lös fullt | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/sifferkryptot.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/sifferkryptot.cpp) |
| [Sista moroten](https://po2punkt0.kattis.com/problems/poskola23.sistamoroten) | Lös för 40 poäng | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/sistamoroten-40p.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/sistamoroten-40p.cpp) |
| [Pickle clicker](https://po2punkt0.kattis.com/problems/pickleclicker) | Lös $T \leq 10$ | [Python](https://github.com/Kodsport/po-solutions/blob/main/python/pickleclicker-20p.py) | [C++](https://github.com/Kodsport/po-solutions/blob/main/cpp/pickleclicker-20p.cpp) |

# Avancerade tekniker

Om du vill lära dig om mer avancerade tekniker finns det ett flertal övningsproblem på [Joshuas onlinedomare](https://judge.progolymp.se/archive/practice). 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.

<style>
table {
width: 100%;
border-collapse: collapse;
margin: 20px 0;
font-family: Arial, sans-serif;
font-size: 16px;
text-align: left;
}

thead {
background-color: #4CAF50;
color: white;
}

th, td {
padding: 12px 15px;
border-bottom: 1px solid #ddd;
}

tbody tr:nth-child(even) {
background-color: #f2f2f2;
}

tbody tr:hover {
background-color: #f5f5f5;
}

a {
color: #007BFF;
text-decoration: none;
}

a:hover {
text-decoration: underline;
}

details {
background-color: #d1ecf1;
border-radius: 5px;
padding: 10px;
margin-bottom: 15px;
}

details p {
font-size: 16px;
line-height: 1.6;
color: #333;
}

summary {
font-size: 18px;
font-weight: bold;
cursor: pointer;
color: #00796b;
padding: 5px;
transition: color 0.3s ease;
}

summary:hover {
color: #004d40;
}

details ul {
list-style-type: disc;
margin-left: 20px;
color: #555;
}

details ul li {
margin-bottom: 8px;
font-size: 16px;
}

</style>

<!--Make it so that all links in main content open in new tab. Doesn't work currently-->
<script>
window.onload = function() {
var links = document.querySelectorAll('.container.page-content a.new-tab');

links.forEach(function(link) {
link.setAttribute('target', '_blank');
});
};
</script>