# Ask marilyn
Klassiska monty hall problem. Vår strategi kommer vara följande:
Välj en $\textit{random}$ låda. Om Marilyn avslöjar rätt väljer vi den. Annars byter vi till den som inte avslöjades eller vi valde. Expected 2/3 chans att vinna.

# Pizza Strings
Bygg upp svaret en bokstav åt gången. Testa att fråga efter P,I,Z,A i en slumpad ordning. Vi behöver aldrig fråga efter sista (uteslutningsmetoden).

# Crusaders of the lost mark
Problemet är förvånansvärt tight med antalet queries du får ställa. Jag känner till två lösningar, men kommer beskriva den som är mer generaliserbar: metoden kallas parallell binärsökning.

Vi kommer skapa en rekursiv funktion solve, som svarar på alla queries samtidigt:

def search(lo, hi, ponies)

Vi börjar med att calla den med search(1,c+1, all_ponies)
denna kommer sedan fråga (lo+hi)/2 och dela ponies i två delar baserat på om de är större eller mindre än mid och rekursera vidare. Väldigt viktigt att specialbehandla exakt likhet.

Denna strategi använder ca 1506 queries i värsta-fallet. För att få AC kan du antingen ställa dina queries lite konstigt så domaren inte har testfall emot dig, eller specialbehandla grupper av få ponies kvar.

# Going in circles
Huvudidén är att sätter de första $k$ vagnarna till ett förbestämt mönster. När vi gått ett varv kommer detta att repeteras och vi är klara. Vad ska detta mönstret vara? Det måste tillfredställa två saker: det måste vara långt nog och vara tillräckligt slumpat. Längden måste vara mer än $log_2(5000)$. I pratiken borde 16 eller 17 funka (de bruijin sequences tar alla av längd $\leq 15$). Sen får det inte innehålla ett mönster, det finns 200 testfall som tar en massa olika mönster.

Det verkar dock problematiskt om $n$ är mindre än längden av mönstret. Tydligen funkar detta i slutändan ändå, men är inte alls uppenbart.

Jag specialbehandlade istället små n. Du kan kolla om $n=t$ för ett givet $t$ genom att göra följande: gå $t$ steg åt höger, släck alla lampor på vägen. På sista positionen, tänd lampan. Gå $t$ steg åt vänster. Om lampan är tänd vet vi att $n=t$. Om man implementerar detta effektivt klarar man att kolla alla $t \in [3,20]$ på ca 450 queries, och sen kan man använda bitmönstret.

# Star wars movies
Detta problemet ber oss om en datastruktur som kan göra 2 saker: sätta in ett tal vid index $i$ och ge $k:te$ största talet.

Det finns vad som kallas [order statistics tree](https://codeforces.com/blog/entry/11080), vilket maintainar en sorterad lista sorterad på heltal, och kan svara på vad k:th största elementet är. Naivt kan man börja med att sätta in 2 element, ett med noll och ett med infinity. För att sätta in ett nytt element hittar du nästa och föregående till nya elementets position och tar medelvärdet av det. Med long double funkar detta säkert för $n$ runt 100, sedan kan det bli problem med att att dina index blir exponentiellt små.

Istället kommer vi lösa problemet offline. Vi vänder på ordningen av alla queries och börjar med en full lista av alla filmer. Därefter tar vi bort allting stegvis och kommer därmed få slutpositionen av elementet som tillhör varje query (dessa kommer vara heltal i $[0,6\cdot10^5]$. Vi kan sedan stoppa in dessa i vårt order statistics tree och svara på alla queries med find_by_order.

Om du vill lösa problemet online, läs om [treaps](https://cp-algorithms.com/data_structures/treap.html). Du kommer behöva en implicit treap, men läs hela artikeln för att förstå vad som händer.