Onlinekval 2024
Lösningsförslag
Kiki boba
Av: Harry Zhang
Gör vad statement säger
Fun fact: hur bilden skapades
Fun fact: hur bilden skapades
Fun fact: hur bilden skapades
Fun fact: hur bilden skapades
Stad i ljus
Av: John Hedin
Lösning
Sortera ljusstrimmorna på längd, ta de kortaste tills det inte går längre.
Naiv lösning: sortera i O(N^2) med bubble sort
O(NlogN) sortering med ditt språks “sort”-funktion
O(N) sortering med bucket sort- alla tal är små
Sverigekartan
Av: Joshua Andersson
81p
För första gången och varje uppdatering, gör en “floodfill”- antingen BFS eller DFS
Ha en stack på rutor att besöka. Ta bort rutor ur din stack, kolla bara varje ruta en gång genom att hålla koll på vilka du besökt. Lägg till grannar i de 4 riktningarna till din stack.
81p
100p
Vi gör samma arbete om och om igen-onödigt
När vi gör vår floodfill, sätt alla rutor du kan nå till ‘S’.
När en uppdatering sker, kolla om en av dina grannar är ‘S’. Isåfall, floodfilla alla rutor som inte är ‘S’.
Varje ruta kan bara besökas en gång, O(RC+U)
Segmentövervakning
Av: Harry Zhang
Kattis is watching
AI-Modell tränad på anime
genererade bäst katt…
Ville ha 1984, men var
rädda för copyright.
Kattis blev bättre :)
Alltid 1 eller -1
Vi bryr oss bara om de intervall som täcker hela intervallet. Ha en lista av dessa, låt oss kalla den u. Ha även en lista av storlek 10^6, active, där active[i]=är kamera med id i aktiv
När vi lägger till: om intervallet täcker allt, u.append(id). Active[id]=True
När vi tar bort:
Active[id]=False
Alltid 1 eller -1
När vi ska svara om det går:
while len(u)>0 and not active[u[-1]]:
del u[-1]
Om len(u)>0 efter den här processen går det, annars inte
Går också med dictionary, men det här implicita sättet att radera kommer hjälpa oss sen
O(Q^2)
Låt intervallet vi övervakar vara l,r
Vi vet hur vi löser att svaret är 1.
Om svaret är 2 vill vi aldrig välja ett intervall ql,qr
där ql>l och qr<r. Ignorera dessa intervall
O(Q^2)
Falluppdela
Fall 1: ql<=l. Ha en mängd med alla dessa intervall. Vi måste täcka vänstra ändpunkten, så vi måste välja en av dessa. Vad ql är spelar ingen roll så länge ql<l. Ta den med högst qr av dessa.
Fall 2: qr>=r. Ha en mängd med alla dessa. Samma argument, ta den med minst ql.
O(Q^2)
Alltså kan vi ta den bästa ur vardera mängd och kolla om dessa överlappar. Om de gör det är svaret 2 (kolla om svaret är 1 först). Annars -1
Tar O(Q) att kolla igenom vardera mängd dock…
O(Qlog(Q))
Den enda långsamma delen är vår datastruktur. Den behöver kunna:�Ge oss minsta (eller största) talet
Lägga till ett tal
Ta bort ett tal
Heap!
O(Qlog(Q))
Heaps kan:
Ge oss minsta talet O(1)
Lägga till ett tal O(log(Q))
Ta bort minsta talet O(log(Q))
Hur tar vi bort godtyckligt tal?
O(Qlog(Q))
Hur tar vi bort godtyckligt tal?
Återanvänder active-arrayen! Varje tal i heapen är ett par
(värde, id)
while len(heap)>0 and not active[heap.top()[1]]:
heap.removetop()
Efter detta, om heapen har element i sig, ta den i toppen
Utmaning
Hur kan vi lösa problemet om den frågar om “minsta antalet intervall för att täcka intervallet”, utan begränsingen att svaret inte får vara större än 2?
Brandpost
Av: Erik Hedin
O(WHN)
Insikt 1:
Vi vill bara röra oss upp eller höger.
Om vi går vänster eller ner kommer rutnätet se ungefär likadant ut, men vi är längre bort från målet
O(WHN)
Gör kortaste vägen med djikstra, besök varje ruta en gång O(WH). Räkna hur mycket vatten det är vid den tidpunkten, O(N)
Formel: vår position är (x,y), brandpost vi vill kolla är (a,b)
max(0,t-(abs(a-x)+abs(b-y)))�abs(a-x)+abs(b-y) är “manhattanavståndet” mellan (x,y)�och (a,b)
O(WH+min(W,H)N)
Eftersom vi bara rör oss höger eller upp kommer vi besöka varje ruta vid en viss tidpunkt
2345�1234�0123
Innan vi gör djikstra beräknar vi mängden vatten på varje ruta vid tidpunkten vi besöker den
O(WH+min(W,H)N)
För varje rad: börja på kolumn noll. Räkna hur mycket vatten det är på den i O(N).
När vi rör oss till en ruta höger bidrar varje brandpost med 0 eller 2. Det till vänster om oss bidrar med 0, de till höger om oss bidrar med ökning av 2.
Pillig implementation
Trafikverkets plan
Av: Joshua Andersson
O(N^2/64)
Grafen blir en DAG
“Reachability in DAG”, standardproblem. Går att göra med bitsets, bra att kunna.
https://cses.fi/problemset/task/2138
O((n+q)log(n))
Vi kan få väldigt mycket information genom att betrakta det oriktade trädet. Börja med att rota det vid godtycklig nod
–>
O((n+q)log(n))
Det finns en och endast en väg mellan�varje par av noder. Denna består av�a->lca(a,b) och lca(a,b)->b
där lca(a,b) är noden längst ner som är�har både a och b i sina subträd
O((n+q)log(n))
Finns två standardalgoritmer för LCA.
Vi kommer använda den härifrån
https://docs.google.com/presentation/d/1vCWbYg-cQ2BSwqYwa8HFlupbgcGhDdnptGkos4fncjI/edit?usp=sharing
O((n+q)log(n))
Vi vill nu snabbt kolla: pekar alla kanter från a->lca(a,b) mot roten och alla kanter från lca(a,b)->b bort från roten?
O((n+q)log(n))
För varje nod, förberäkna hur högt upp i trädet den kan komma genom kanter uppåt, respektive om vi hade vänt på kanterna.
Finns väg mellan a och b?�lca=computelca(a,b)
works=isancestor(up[a],lca) and isancestor(revup[b],lca)�Isancestor förklaras i min länkade powerpoint. Komplementera med google
Utmaning
Blandat med queries finns uppdateringar i formen “vänd på i”. Kan du fortfarande lösa effektivt?
Förfalskad snöflinga
Av: Olle Lapidus
Fall 1: N = 7
Experimentera med restriktionerna. Inse att det bara finns två möjliga snöflingor i det här fallet. Hårdkoda dessa och beräkna antalet pixlar du behöver ändra på för att komma till någon av dem.
Fall 2: N = 11
Att det är både spegel- och rotationssymmetri innebär att bilden kan delas upp i åtta regioner som alla kommer att se likadana ut.
Svarta pixlar sammanhängande�+ inga vita 2x2-kvadrater ger också�att de svarta pixlarna till höger�alltid måste vara svarta. �Mittenpixeln måste vara vit.
Fall 2: N = 11
Lösning: Testa alla 2^10 sätt att fylla i övriga pixlar.
Ha en funktion som kan testa om en viss bild är en �snöflinga�
Om det blir en snöflinga, jämför �med inputdatan.
Fall 2: N = 11
Lösning: Testa alla 2^10 sätt att fylla i övriga pixlar.
För att testa alla möjliga sätt att fylla i pixlarna kan vi iterera över alla s.k. bitsets = tal från 0 till 2^10-1
Tolka talet binärt: 412 = 110011100
Ge en ordning till pixlarna (någon pixel är nummer 1, etc)
Om siffra nummer k i bitsettet vi kollar på är 1 ska pixel nummer k vara vit, annars svart.
Fall 3: N = 15
Gör samma uppdelning i åtta mindra bitar som innan.
Lösningen bygger på att vi har kommit fram till att det finns ganska få möjliga snöflingor.
Vi kan förenkla kriterierna för snöflingar:
Vit och svart sammanhängande + inga vita 2x2
=> Snöflingan kommer att bilda ett träd (grafstruktur)�+ Hela ramen svart (pixlarna längst ut i bilden)
Fall 3: N = 15
=> Snöflingan kommer att bilda ett träd (grafstruktur)�+ Hela ramen svart (pixlarna längst ut i bilden)
Vi kan nu köra en dfs i åttondelsområdet som söker över vita pixlar, och breakar om något av våra kriterier bryts. Denna dfs kommer generera alla möjliga snöflingor.
Mycket pillig kod…
Fall 3: N = 15
ALTERNATIV:
Kör din kod från N = 11-fallet för att i förhand generera alla möjliga N = 15-snöflingor. (för långsamt för att skicka in men tar inte jättelång tid).
Spara alla dessa i en lista.
Skicka in kod med den listan och jämför alla med input.
Proteinsyntes
Av: Joshua Andersson
O(NK)
Låt K=totala längden av alla strängarna
Vi gör dp.
dp[i]=minsta kostnaden för att ha byggt fram till bokstav i av protein T
O(NK)
O(NM)
Vi vill optimera bort den�här loopen
Hashing
Jämföra strängar i O(1)?
String hashing! Gör om strängarna
a=1
b=2
…
abc->123
Hashing
Om hash(a)==hash(b)�är de nästan garanterat�samma sträng
1/10^9 att de är olika
Hashing
Varför funkar det?
låt b=konstant, typ 153. Hash evaluerar följande uttryck:
Tänk på hur vi skriver tal i bas 10:
Så vi skriver vår sträng i bas b, och tar modulo mod
Hashing
Går att bevisa att om ditt val av modulo är bra kommer varje sträng ge ett ungefär slumpmässiga tal=> sannolikheten att�hash(a)==hash(b) och a!=b är ~1/10^9
Hashing
Du får INTE beräkna hash mod 2^32, 2^64 eller 2^k.
Vad som sker automatiskt om du använder unsigned int/long long och det blir overflow.
Finns elaka tester, kallas thue-morse.
I python måste du modda, annars blir dina hashvärden stoora (typ lika stora som strängarna och det är långsamt)
Hashing
Men hur gör vi? Vi kan�hasha alla w i förväg,�men hur hashar vi�t[j,j+len(w)] snabbt?
Finns O(N^2) möjliga�substrängar…
Hashing
Vi vill alltså snabbt kunna beräkna
Förberäkna en array p:
p[0]=�p[1]=�p[2]=
Hashing
Låt säga att vi vill beräkna hash(s[5,7]) och strängen har längd 10
Vi vill ha
Kan vi subtrahera bort det sista?
Hashing
Vi vill ha
Kan vi subtrahera bort det sista?
Hashing
I kod:
(ej testad)
Hashing
Hashing är knepigt, om bara har mod 10^9+7 kan det ändå ske kollisioner p.g.a. birthday paradox
Kolla din hashing här: https://open.kattis.com/problems/hashing
Hashing
Kod som funkar:
https://github.com/Matistjati/CP-templates/blob/master/content/data%20structures/stringhashing.cpp (doublehash)
https://github.com/kth-competitive-programming/kactl/blob/main/content/strings/Hashing.h (snabbare)
https://github.com/cheran-senthil/PyRival/blob/master/pyrival/strings/hashing.py
O(NM)
Därmed, med hjälp av detta kan vi snabbt kolla om strängarna är samma i O(1) och vår dp kör nu i O(NM)
Hashing från pyrival
O(Nsqrt(K))
Insikt: det finns inte många strängar av olika längd. Vi försöker få så många olika som möjligt:
a�aa�aaa�….�Totala längd är k
O(Nsqrt(K))
1+2+3+4+5+...+l=k
l(l+1)/2=k
{l(l+1)/2~=l^2}
l^2=k
l=sqrt(k)
O(Nsqrt(K))
Skapa en dictionary:
strings[längd]=set med hash av alla strängar av den längden
Fun facts
Finns 2 andra sätt att lösa:�Använd aho corasick för att hitta alla nsqrtk matchningar i O(nsqrtk), sen bara göra dp https://github.com/kth-competitive-programming/kactl/blob/main/content/strings/AhoCorasick.h
Skapa ett trie av alla strängar du kan använda. Komprimera alla noder med bara ett barn. Höjden blir O(sqrt(k)) och du kan hitta alla matchningar för en viss position i O(sqrt(k))�Om du kombinerar med stränghashning
Fun facts
Beräkna modulo är långsamt i python…
C++ lösning kör på ca 2s på kattis servrar
Python kör på ca 16s om du inte är megasmart
Fun facts
Hög TL=>stor risk för�unintended lösningar
Vi skrev många lösningar,�försökte hitta och döda�alla lösningar som�egentligen ska vara för�långsamma
Fun facts
Väldigt många sorters�data, vi vände till och med på�alla strängar så man inte ska�kunna få en snabbare lösning�genom att att vända på indata
Fun facts
…i slutändan lyckas Arvid och Emil hitta fungerande cheeselösningar