# Brains
Istället för att försöka gå från 0 till $b$ (target), så börjar vi på $b$ och vill subtrahera till vi kommer till $0$ exakt. Huvudidén är följande: vi kommer att subtrahera shipping container 0 tills vår target är mindre än $c \cdot 10^5$ ($10^5$ eftersom det är maxvikten). Sen kan vi betrakta följande sortens drag: addera shipping container 0 (ångra en av de första subtraktionerna vi gjorde) eller subtrahera en shipping container som inte är nr 0. Det går att visa att man kan ordna en sådan sekvens av drag så att man först kommer ner till $<10^5$ och sedan aldrig går över $2 \cdot 10^5$ (tror jag, kanske blir pyttite mer). Vi kan då beräkna vilka värden $< 2\cdot 10^5$ som kan ta sig till $0$ med den sortens drag. Detta funkar nästan. Problemet är att man kan råka ångra "subtrahera 0" fler gånger än vi gjorde det. Vi gör då en djikstra, där vi beräknar minsta antalet gånger vi ångrar oss för att komma till 0. Slutgiltiga komplexiteten blir $O(N \cdot s_{i_{max}}+Q)$ (man kan använda ett trick för att spara logfaktor. Tror den kallas dials algoritm?).

# Max loot
Antingen är $N$ eller totala profiten liten. Vi kommer att skapa en algoritm för varje fall och välja den som är snabbast för den givna instansen.

* $N$ är litet. Om $N$ är $< \approx 23$ funkar $2^N$ finfint. I detta problemet räcker inte det. Det går att lösa i $O(2^{N/2}log(2^{N/2}))$. Dela upp inputen i två delar som är ungefär $N/2$ stora var. Generera sedan alla delmängder av vardera halva. Sortera de sedan på vikt och ta bort alla delmängder som är strikt sämre än föregående (det finns någon med lägre vikt och mer profit). Sedan gör du tvåpekare.
* Om profit är litet kan vi använda ett vanligt DP-trick: vanligtvis gör vi $dp[i][vikt]$=max profit om vi betraktat de $i$ första sakerna. Vikt är stort i det här problemet, men profit litet. Så vi byter plats på de: $dp[i][profit]=min vikt$.

Om man alltid väljer algoritmen av dessa som kommer köra snabbast är problemet löst.

# Moving pianos
Finns en simpel girig lösning. Den hamnade i svår för att löste den i kontexten av "flow-övningsproblem" och tänkte inte ens på simplare lösningar.

Det intressanta med den är som ett flödesproblem: försök lösa den med flöde där du har en nod per piano, en per arbetare och en per veckodag. Jag är väldigt säker på att det inte går, och bygger stark intuition för vad max flow kan och inte kan göra.

# Among ourselves
Problemet kan reduceras till "kan vi ta bort ett intervall kanter av storlek $k$ så att det finns en väg från nod $a$ till $b$ (och hitta den vänstraste sådana)". Vi kommer (surprise surprise) använda en modifierad union-find för det här. Vi vill ha en union-find som kan göra allt en vanlig union-find kan, men också följande operation: ångra senaste mergen som gjordes.
Så exempelvis:
* Merge 1,2
* Merge 3,4
* Merge 2,3
* 1 och 4 är i samma komponent
* Undo last (merge 2,3)
* 1 och 4 är inte i samma komponent
* Merge 4,1
* 1 och är 4 i samma komponent
Detta implementeras väldigt simpelt: varje gång du gör en merge förändras O(1) värden (parent och size-array). Håll koll på värdena av de påverkade noderna innan mergen. Använd inte path compression, men smaller-to-larger, vilket ger $O(log(N))$ per operation.

Vi kommer nu använda denna struktur tillsammans med divide and conquer för att testa varje intervall av storlek $k$. Låt säga att vi är på intervallet $[0,n-1]$.
* Låt $l,r$ vara intervallets ändpunkter. Då vill vi att kantera $[0,l-1]$ och $[r+k, n-1]$ ska finnas i vår union-find (dessa kanter är en del av varje startpunkt av ett k-intervall i $[l,r]$)-
* Låt $mid=(l+r)/2$.
* För vänster del av rekursionen (nytt intervall $[l,mid]$) lägger vi till kantera $[mid+k,r+k]$. Sedan undoar vi dessa
* För vänster del av rekursionen (nytt intervall $[mid+1,r]$) lägger vi till kantera $[l,mid]$. Sedan undoar vi dessa

För varje $[l,r]$ lägger vi till och tar bort $O(r-l)$ kanter, varje tar $O(log(N))$. Så för varje par $[l,r]$ får vi $O((r-l)log(N))$ arbete. Vi får rekursionen

$T(n)=2T(\frac{N}{2})+O(nlog(N))$. Enligt master theorem ger detta total komplexitet $O(Nlog(N)^2)$ (googla gärna! Man kan också komma fram till ungefär samma geometriskt: rita först ett block av storlek $1 \times N$, två stycken av storlek $N/2$ osv. Det ser ut såhär: 
Totalt finns det $log(N)$ rader och vi göra $O(Nlog(N))$ arbete per rad, vilket ger $O(Nlog(N)^2)$ arbete totalt.

Svårare variant, jättebra övning: [joker](https://oj.uz/problem/view/BOI20_joker).

# Language survey
En riktig Nils-klassiker. Innan du läser [writeupen](https://github.com/icpc/ncpc-web/releases/download/ncpc2023-data/ncpc23slides.pdf), försök lösa den själv. Hint: om någon av sidorna är större än $1$ går det alltid. Försök hitta en konstruktion, inte en algoritm.