3 of 22

Testfallsgrupp 1 (Q=1, N<=100)

Det är bara för en enda person P vi undrar när den får sitt vaccin.

Gå igenom alla dagar och håll koll på antal personer kvar tills P får sitt vaccin.

När antal personer kvar går ner till 0 har vi kommit till rätt dag, och skriver ut den.

4 of 22

Testfallsgrupp 2 (Q<=100 000, N<=100 000)

Här hinner vi inte svara för varje person i taget som i grupp 1, det skulle ta O(QN) tid.

Istället skapar vi en lista S[x] som är dagen personen på position x i kön får sitt vaccin.

Vi kan skapa listan genom att gå igenom alla dagar i ordning, och för varje dag j lägga till personerna som får vaccin den dagen till listan S genom att lägga till talet j k_j gånger. För att hitta svaret för en person bara tar man S[p_i].

Tex för sample 1: k = [1,3,5], S = [1,2,2,2,3,3,3,3,3]

Detta tar tid O(len(S)) = O(15*N)

5 of 22

Ekorren i trädet

Av: Fredrik Ekholm

6 of 22

Första insikter

Ifall ett subträd inte innehåller någon nöt kan vi ignorera det.

Annars måste vi någon gång gå ner i subträdet, och sen gå ut från det. Då går vi längst kanten som leder ned i subträdet två gånger, vilket bidrar med 2 till totala avståndet.

Kalla alla kanter kanter som leder ned till subträd med nöt i för “viktiga”.

Alltså är svaret 2*(antal viktiga kanter)

7 of 22

Testgrupp 2 (K <= N <= 1000)

Insikt: För varje nöt är alla kanter från roten till nöten viktiga.

Vi kan börja att hitta föräldern till varje nod genom en traversering av trädet, rekursiv DFS är nog enklast.

Sedan går vi igenom varje nöt och för varje nöt stegar vi upp till roten genom att iterativt gå till föräldern. Vi markerar alla kanter längs vägen som “viktiga”.

Sist räknar vi hur många kanter som är viktiga.

O(NK)

8 of 22

Testgrupp 3 (K <= N<=100 000)

Vi kan räkna ut hela svaret rekursivt istället.

Vi har en funktion dfs(V, P) som:

lägger till alla viktiga kanter i V’s subträd till en global variabel
returnerar en boolean som säger om det finns en nöt i V’s subträd.

dfs(V, P) kan räknas ut rekursivt genom att anropa alla grannar till V (som inte är P). V’s subträd har en nöt om några av barnens subträd har nöt eller om V har en nöt, och för varje barn är kanten till barnet viktig om barnets subträd har nöt.

9 of 22

Social distansering

Av: Fredrik Ekholm

10 of 22

Lösning...

Observation: Det är svårt att direkt räkna ut största avståndet, men det är lätt att testa om svaret är minst något tal X: Lägg personerna girigt så långt till vänster som möjligt!

11 of 22

Lösning...

Observation: Det är svårt att direkt räkna ut största avståndet, men det är lätt att testa om svaret är minst något tal X: Lägg personerna girigt så långt till vänster som möjligt!

12 of 22

Lösning för 76 poäng

Sortera listan med intervall.
Binärsök efter svaret X.
Gå igenom personerna och placera ut dem så långt vänster som möjligt.
Om du lyckades placera ut alla N personer är svaret >= X, annars är det < X.

Komplexitet: O((N+M)log(K)).

13 of 22

Lösning för 100 poäng

Om vi har ett segment med P platser, och vi testar om svaret är >= X, så kan vi klämma in ceil(P/X) personer där. Dessa personer kommer då blockera (X-P%X)%X platser framför.

Vi kan då lösa problemet i O(MlogK).

14 of 22

Minigolf

Av: Joakim Blikstad

15 of 22

Lösning

Kör BFS,

håll koll på rutorna du inte besökt med hjälp av ett set för varje rad och ett set för varje kolumn så kan du snabbt

17 of 22

Flyga drönare

Av: Ivar Källström

18 of 22

Testgrupp 1 (N<=20)

Här kan vi testa de 2^N olika delmängderna av batterier och se vilken delmängd (av de vi har råd med) som ger störst E_tot/W_tot.

O(N*2^N)

19 of 22

Testgrupp 2 (w_i=0)

Om inga batterier väger något vet vi redan att W_tot bara beror på drönarens vikt.

För att maximera E_tot/W_tot räcker det nu att maximera E_tot.

Knapsack:

dp[i][b] = (bästa summan av energier för de i första batterierna med budgeten b).

= max(dp[i-1][b - c_i] + e_i, dp[i-1][b])

20 of 22

Testgrupp 3 (Alla batterier kostar lika mycket)

Antalet batterier vi ska ta är mindre än eller lika med B / c_0, inga övriga begränsningar finns. Vi vill maximera E_tot / W_tot.

Testa om det finns batterier så att:

E_tot / W_tot > t ⇔ E_tot > t * W_tot ⇔ E_tot - W_batteri * t > t * W.

Maximera E_tot - W_batteri * t genom att sortera batterierna i minskande ordning efter e_i - w_i * t och ta de första k batterierna (eller avbryt om talen blir negativa).

Hitta största t, binärsökning.

O(log(t_max)*N*log(N))

21 of 22

Testgrupp 4

Kombinera lösning för grupp 2 och 3. Binärsök först efter L.