# Ihopslängt lösningförslag problemset 4 # Hot springs Vi kan inse att ordningen av inputtalen är irrelevant, så vi sorterar inputen. Om vi bygger upp vår lösning iterativt baklänges kan vi inse att vi i princip tvingas ta största-minsta-största-minsta osv. Detta kan antingen implementeras med pekarpill, eller deque, som kan ta bort element både i slutet och början i $O(1)$. # Supercomputer Detta är i princip bara "implementera ett segmentträd". Det finns bra tutorials online. [Implementation i C++](https://github.com/Matistjati/CP-templates/blob/master/content/data%20structures/SegmentTree.cpp). Har för mig [Abdullahs föreläsning](https://www.youtube.com/watch?v=OGpbAAhf4E4) var bra, kommer dock inte ihåg om den hade introduktion. # Firetrucks are red Problemet blir "givet en massa cliques (delmängd noder där alla har kanter mellan sig parvis), finns det ett spännande träd?". Det går att inse att om det finns ett spännande träd i grafen, så finns det fortfarande ett om vi tar ett spännande träd av varje clique. Dvs, för varje clique skapar vi kanterna $(clique[0],clique[1]),(clique[0],clique[2]),\dots$. Därefter kan vi antingen använda DFS eller Union-find för att hitta det spännande trädet. # Wordle Det första du vill göra är att skapa en primitiv "givet ett visst resultat på en gissning, vilka ord kan vi utesluta?". Om det finns många ord är det svårt att göra mycket bättre än att ta en slumpmässig gissning och sedan filtrera ut alla förbjudna. När det finns färre ord kvar kan du testa varje gissning och varje möjligt svar och se vilken som leder till minst antal ord kvar i genomsnitt. # Bonbons Faktumet att constraintsen är så stora borde vara en hint att det finns en simpel konstruktion. Börja med att sortera typerna. Låt $a$ vara den med mest, $b$ näst mest osv. Om $a > r*c/2$ är det uppenbarligen omöjligt. Annars går det alltid med följande konstruktion: börja med att placera $a$ i ett kryssmönster: ``` a.a.a.a .a.a.a. a.a.a.. ....... ``` Därefter,placera $b$ för att fylla färdigt kryssen: ``` a.a.a.a .a.a.a. a.a.a.b .b.b.b. ``` Därefter,placera $b$ girigt där det går: ``` abababa baba.a. a.a.a.b .b.b.b. ``` Till sist, placera ut c: ``` abababa babacac acacacb cbcbcbc ``` Varför du behöver placera ut $b$ girigt "där det går" i steg 3: Steg 1: ``` a.a. .a.. ``` Steg 2: ``` a.a. .a.b ``` Steg 3: ``` abab .a.b ``` Jag är för dålig för att bevisa korrektheten😭