# Lösningar blandat

Jag valde lite svårare problem eftersom ni hade jullov, men verkade som att det blev lite för svårt...

# Rhyme Power
Det finns flera lösningar på det här problemet, men jag tycker följande är mest elegant:\
Först vänder vi på alla strängarna. Problemet är nu att hitta största gemensamma prefixen mellan ett par av strängar. Genom att lägga in strängarna i ett så-kallat trie (googla det) är problemet bara att hitta djupaste noden som har > 1 lövnod i sitt subträd. Ett sätt är att ta +1 på en counter på varje nod man går igenom när man insertar ett ord och leta efter djupaste noden med counter > 1. Notera att denna lösning generaliserar till "de k strängarna med längst lcp (longest common prefix)" (i detta problemet är k=2).

# Arriving on time
Det går att binärsöka över svaret. Därefter kan vi göra en djikstra för att hitta kortaste vägen om vi väntar $t$ sekunder.
Det kan vara lite pilligt att få till en funktion "om jag är vid tid x, vid vilken tidpunkt kan jag korsa den här kanten?". Det här var min lösning

int timetillcross(int x, int t, int p)
{
    if (x <= t)
    {
        return t - x;
    }
    int k = x - t;
    k %= p;
    k += p;
    k %= p;
    if (k == 0) return 0;
    return p - k;
}

En nackdel med den här lösningen är att den är ganska långsam eftersom det krävs 2 logfaktorer, vilket precis klarar sig. Det finns en smartare lösning som går baklänges från målet.

# Berry battle
Klassiskt Nils ad-hoc problem :)
Det mest frustrerande med det är att det finns så många möjliga strategier. Den simplaste lösningen är troligtvis att betrakta ett par av myror som är bredvid varandra. Om man aldrig väljer en nod som en av de två befinner sig på kommer de klara sig till slutet.
Alltså är lösningen: välj ett löv och dess granne (varför kan vi dö annars?), ät upp lövet, ät sedan upp grannen. Därefter kan dessa två myrorna äta upp resten av trädet i DFS-preorder ordning.
Specialfallet är träd med diameter <= 3. Dessa är omöjliga.

# Trick and treat
Det här är ett lite konstigt problem. Det verkar först jättesvårt, men sen kan man läsa att "varje grupp barn ber om 1-10 godisar". Detta innebär att antalet godis vi vill köpa alltid är väldigt nära $M$.
Detta beror på följande: den enda enda gången man vill köpa mycket mindre godis än $M$ är om det låter dig undvika följande situation:
Du har 100 godisar och barnen ber om
100 1 1 1 1 1 1 1 1 1 1.
I detta fallet är det bäst att ta ett tal mindre än 100.
Notera dock att vi aldrig vill ta mindre än $M-maxA_i$.
Det vill säga, lösningen är att testa att köpa $M,M-1,M-2,\dots,M-10$ godisar, simulera processen i $O(N)$ och ta den bästa.

# Emergency exit
Kör först en BFS från utgången till alla rutor. Om vi betraktar kantera BFS:en använda kommer detta bilda ett så kallat kortaste vägen-träd. Det visar sig att om vi girigt får folk att promenera uppåt i det här trädet (de som är högst upp går först osv. Om man är blockerad från att gå uppåt väntar man) är detta optimalt.
Varför funkar detta? Insikten är att enda gången två personer "krockar" (dvs, en rör sig uppåt och blockerar en annan) är när de är på samma djup. Men om de är de på samma djup kan de ändå inte komma i mål samtidigt (alla kommer i mål vid olika tidpunkter), så det är meningslöst att en av de skulle ta en kant som inte tillhör trädet för att komma närmare mål.

Om det finns flera utgångar blir det svårare: [Room Evacuation](https://open.kattis.com/problems/roomevacuation) (kräver max flow).

# Collusion on two wheels
Intuitivt vill vi placera personer som är långt ifrån varandra i olika grupper. Vår lösning bygger på att göra en sekvens val av formen "personerna i och j är i olika grupper". Det vill säga, vi lägger in avstånden mellan alla par punkter i en stor lista, sorterar den så störst kommer först och går sedan igenom den. När måste vi sluta? Vi kan tolka detta som att lägga till kanter i en graf. Att kunna dela in en graf i två disjunkta mängder noder utan att det finns kanter inom vardera grupp (kant=vi är olika grupper, så detta är vad som krävs för giltiga grupper) är ekvivalent med att grafen är bipartit. Alltså har vi reducerat problemet till att lägga till kanter och sluta så fort grafen inte är bipartit. Detta går att lösa med en [modifierad union-find](https://cp-algorithms.com/data_structures/disjoint_set_union.html#support-the-parity-of-the-path-length-checking-bipartiteness-online).

En annan lösning är att första binärsöka över svaret. Vi har nu subproblemet "kan vi få svaret $m$?". Hitta paret av punkter som är längst ifrån varandra. Låt en av dessa punkter vara $P$. Placera alla punkter $U$ där $dist(U,P)>m$ i grupp 2 (detta är forcerat). Resten börjar i grupp 1. Det visar sig att denna uppdelningen inte räcker. Vi tar därför och flyttar alla från grupp 1 till grupp 2 som det går och kollar seda n om det är en giltig uppedlning. Oklart om det fakiskt är korrekt, men det får AC. Borde kunna optimeras till $O(nlogn)$, då det enda kvadratiska är att "hitta parent punkter i en mängd med störst avstånd". Borde finnas linjärtidsalgoritmer för det.