Läger 2024

Lösningsförslag

Hårgalåten

Av: Nils Gustafsson

Problem

Du får givet en lista med startvärden X₁ X₂ … X_n och en funktion f(1), f(2), …, f(m).

Varje sekund ändras X_i till f(X_i+1). Hur lång tid tar det för varje index att ha varit alla värden?

1

2

3

4

5

Subtask 1

N = 1

​

X₀ , f(X₀), f(f(X₀)), …

​

Simulera tills du ser samma värde två gånger.

​

​

​

​

Subtask 2

f(i) = i

​

Håll koll på var första förekomsten av varje takt är, och på vilka index de andra förekomsterna är.

​

4 2 2 3 1 2 2 1

​

​

​

​

Subtask 2

f(i) = i

​

Håll koll på var första förekomsten av varje takt är, och på vilka index de andra förekomsterna är.

​

4 2 2 3 1 2 2 1 4 2 2 3 1 2 2 1

​

​

​

​

Subtask 2

f(i) = i

​

Håll koll på var första förekomsten av varje takt är, och på vilka index de andra förekomsterna är.

​

4 2 2 3 1 2 2 1 4 2 2 3 1 2 2 1

​

​

​

​

Subtask 3

​

Vi kommer hamna i en cykel efter nm steg. Simulera för varje person.

​

X₁ f(X₂) f²(X₃) f³(X₄) … f^n-1(X_n) fⁿ(X₁) fⁿ⁺¹(X₂) … f²ⁿ(X₁) …

​

​

​

Subtask 4 och 5

​

Låt oss undersöka för vilka funktioner f som svaret blir -1.

​

​

​

Subtask 4 och 5

​

Låt oss undersöka för vilka funktioner f som svaret blir -1.

​

​

​

Om >= 2 takter har ingrad 0, så är det omöjligt.

Subtask 4 och 5

​

Låt oss undersöka för vilka funktioner f som svaret blir -1.

​

​

​

Om en takt k har ingrad 0 så måste alla X_i = k. Simulera som i n = 1.

Subtask 4 och 5

​

Låt oss undersöka för vilka funktioner f som svaret blir -1.

​

​

​

Annars så är f en permutation!

Subtask 4 och 5

​

Simulera för att hitta svaret för i = 1: O(nm)

​

X₁ f(X₂) f²(X₃) f³(X₄) … f^n-1(X_n) fⁿ(X₁) fⁿ⁺¹(X₂) … f²ⁿ(X₁) …

​

​

​

​

​

Subtask 4 och 5

​

i = 2:

​

X₁ f(X₂) f²(X₃) f³(X₄) … f^n-1(X_n) fⁿ(X₁) fⁿ⁺¹(X₂) … f²ⁿ(X₁) …

​

​

​

​

​

​

​

​

Subtask 4 och 5

​

i = 2:

​

X₁ f(X₂) f²(X₃) f³(X₄) … f^n-1(X_n) fⁿ(X₁) fⁿ⁺¹(X₂) … f²ⁿ(X₁) …

​

Ta bort första elementet i 1:s taktsekvens. Detta ger 2:s taktsekvens, men där alla takter mappats om med f. Men tack vare att f är en permutation påverkar inte det svaret!

Problemet kan nu lösas som i Subtask 2.

​

​

​

​

​

​

Full poäng

​

X₁ f(X₂) f²(X₃) f³(X₄) … f^n-1(X_n) fⁿ(X₁) fⁿ⁺¹(X₂) … f²ⁿ(X₁) …

​

Låt Y_i = f^i-1(X_i). Låt g(i) = fⁿ(i).

​

Y₁ Y₂ Y₃ … g(Y₁) g(Y₂) g(Y₃) … g²(Y₁) g²(Y₂)...

​

​

​

​

​

​

​

Full poäng

​

Y₁ Y₂ Y₃ … g(Y₁) g(Y₂) g(Y₃) … g²(Y₁) g²(Y₂)...

​

Istället för att gå igenom hela taktsekvensen, så vill vi hitta första förekomsten av varje takt snabbt. Notera att g också är en permutation.

​

​

​

​

​

​

​

Full poäng

​

Y₁ Y₂ Y₃ … g(Y₁) g(Y₂) g(Y₃) … g²(Y₁) g²(Y₂)...

​

​

​

​

​

​

​

​

​

+n

+n

+n

+n

Full poäng

​

Y₁ Y₂ Y₃ … g(Y₁) g(Y₂) g(Y₃) … g²(Y₁) g²(Y₂)...

​

​

​

​

​

​

​

​

​

+n

+n

+n

+n

Full poäng

​

Y₁ Y₂ Y₃ … g(Y₁) g(Y₂) g(Y₃) … g²(Y₁) g²(Y₂)...

​

​

​

​

​

​

​

​

​

+n

+n

+n

+n

Problemet kan nu lösas på liknande sätt som subtask 2.

​

​

Full poäng

​

​

För att snabbt kunna hitta f^k(x) så är det bekvämt att hitta göra en lista av listor med alla cykler, så att vi kan hoppa hur som helst i O(1).

​

Tvåpotenshopp funkar också.

​

O(n+m)

​

​

​

​

​

​

​

​

Köpa fika

Av: Joshua Andersson

Problem

Du får n godispåsar som vardera har en smaskighet s och kostnad c.

Dessa är givna i en ordning. För varje suffix, beräkna vad följande algoritm ger för output om den börjar med budget C:

Köp sak i om du har råd. Annars gå vidare

Rinse and repeat

Subtask 1

O(N^2)

Utför algoritmen som statement beskriver

Subtask 2

O(NC)

DP

dp[i][c]=om jag simulerar lösningen från index i med c kronor kvar, vad får jag för svar?

​

Väldigt lätt att koda rekursivt

​

​

Subtask 3

Bygg en prefixsum. Om du inte kan köpa j kan du inte köpa j+1, j+2 etc (de är dyrare). Därmed kan du binärsöka över hur många du kan köpa för varje startposition

O(Nlog(N))

Subtask 4

Motsatsen av förra lösningen.

Visar sig att vi bara köper O(log(C)) godispåsar för varje startpunkt i denna subtask.

​

Varför? Om vi har K kronor kvar och köper något kommer dess pris att vara likformigt valt mellan 1 och K. Medelvärdet av detta är K/2

K-K/2=K/2�Detta innebär att i genomsnittliga fallet så halveras antalet pengar vi har kvar varje gång vi köper något. Antalet halveringar för att komma till noll är densamma som log2

Subtask 4

Vi är på position i och vill veta nästa vi ska köpa. Binärsök över minsta j så att min(i,j)<=K. (Det vill säga, binärsök fram positionen av nästa godispåse vi kan köpa) Range minimum query går att lösa i O(1) med sparse tables (Björn pratade om det igår). Går kanske med segmentträds-RMQ, men blir 3 logfaktorer då..

​

O(Nlog(N)log(C))

​

Subtask 4.5

Kombinera subtask 3 och 4? Vi köper långa intervall och skippar långa intervall. Känns bra?�Nej.

​

1 1000 1 1000 1 1000 1 1000

Alternerar mellan köp/inte köp

​

Går att vidareutveckla till en AC 100 (?) lösning. Mer detaljer sen

Subtask 5

Betrakta alternativ lösning: vi löser alla queries samtidigt offline. Håll alla queries i ett set sorterat på pengar kvar. För varje startposition i, lägg in en ny query (total smaskighet, pengar kvar,index i).

Låt sedan alla queries som kan köpa godispåsen i göra detta. Ger 38p, men går att optimera.

​

Insikt: (ganska uppenbarligen) kommer det alltid vara ett suffix av queries som har råd med godispåse i. Det jobbiga är att sedan mergea in suffixet i resten av settet. Går att visa att om vi mergear så stora intervall av suffixet som möjligt, så behöver vi amortiserat bara mergea log(C) olika intervall per godispåse.

Subtask 5

Detta ger vägen för treaps, då dessa kan representera arrayer som splittas i intervall och sedan mergeas. Tyvärr är detta jättesvårt att implementera….

​

Kan man använda insikten på annat sätt för att få en lösning? Oklart…

Subtask 5

Istället kommer vi bygga en väldigt fin datastruktur. Låt hibit(x) = indexet av högsta satta biten av ett tal. Exempelvis är hibit(1)=1, hibit(0)=0, hibit(7)=3

Skapa log(C) olika buckets. Varje query q ska alltid befinna i sig bucket hibit(q.pengar)

​

Vad händer när vi ska sälja en godispåse som kostar k kronor?

Alla buckets där hibit(bucket) < hibit(k) kan uppenbarligen inte köpa den.

I bucket där hibit(bucket) == hibit(k) kommer en delmängd köpa den, men därefter kommer deras hibit att sänkas. Alltså behöver vi inte ombalansera bucket med hibit(k), utan de hoppar ner en eller flera buckets

Subtask 5

För alla buckets där hibit(bucket) > hibit(k) så kommer alla queries köpa godispåsen. Därmed behöver vi inte fixa den interna ordningen, då den hålls samma. Några queries kan hoppa ner, men vi hittar enkelt dessa då de ligger i början av bucketen.

​

Det fina: varje item kan max hoppa ner log(C) gånger.

O(Nlog(N)log(C)) totalt

Subtask 5

Detalj: hur hanterar vi att alla i buckets med hibit(bucket)>hibit(k) köper en sak?

Ha en lazy tag för smaskighet och kronor spenderade.

När vi accessar en sak:

query.kronor - lazykronor

När vi lägger in en ny sak:

query.kronor += lazykronor

Subtask 4.5

Låt oss uppgradera den kombinerade subtask 3 och 4- lösningen:

om vi har k kronor kvar filtrerar vi ut alla godispåsar med pris > k. Detta kan göras genom att betrakta godispåsar som en 2d-punkt (index, pris) och göra 2d range sum queries där x går mellan [i,j] och y går mellan [0,k]. 2d range sum queries kan göras effektivt med persistent segmentträd. O(log(N)) för varje

​

Binärsök över hur mycket vi kan köpa, köp detta, rinse and repeat

Subtask 4.5

Farlig testdata? Ja

​

​

Med denna köper den bara en godispåse per iteration >O(N^2). Tyvärr är den bara långsam för den första startpositionen. Så testfallet består av 10^5 oköpbara påsar, och sedan det fallet. Så om du komprimerar ihop det prefixet och sedan kör algoritmen går det snabbt nog.

​

Subtask 4.5

Kör troligtvis fortfarande på ca 7s. Optimera genom att istället för att binärsöka över hur långt höger vi kan gå, så vandrar vi i trädet. Snabbt nog

​

Öppen fråga: kan vi få denna att köra i >=O(N^2) om c_i <= C? (utan att använda godispåsar kostnad 0 eller som har kostnad större än C)

​

Upplega

Av: Harry Zhang

​

Problem:

Givet N träd med ett antal grenar som sticker åt vänster och höger, välj K så att du maximerar snön som stannar på träden ifall snön på alla andra träd faller ner.

​

​

Subtask 1

(5p) Alla grenar pekar endast åt höger

​

Mängden snö som faller ner på marken för alla träd är parvist disjunkta, eftersom snön på ena tärdet kan aldrig hamna på ett annat träd ifall alla grenar pekas åt höger.

Lösning: Räkna mängden snö som finns på varje träd, sortera och välj de bästa K träden.

​

O(NlogN + N*s)

​

​

​

​

Subtask 2

(5p) K = 1

Nu behöver vi vara försiktig med vilka grenar som är över vilka andra grenar.

​

Lite implementation, men man kan göra det på några snygga sätt. T.ex. dela in varje gren i vilken gap den tillhör, och sedan sorterar baserat på grenens höjd:

​

​

leftDrop = [0]*(n+1) #Amount of snow dropped in the i:th gap if the left tree gets shaken

rightDrop = [0]*(n+1) #Amount of snow dropped in the i:th gap if the right tree gets shaken

totalDrop = [0]*(n+1) #Amount of snow dropped in the i:th gap if the both trees gets shaken

Subtask 2

Genom att köra lite exklusion/inklusion så kan man på några niiice sätt beräkna hur mycket snö som faller ner ifall ett träd blir skakat.

​

(totalDrop[i] - leftDrop[i]) + (totalDrop[i+1]-rightDrop[i+1]) beräknar mängden snö som faller ner ifall man endast skakar på träd i.

​

(Att dela upp snön på det här viset hjälpte mig en del för implementera de senare subtasken.)

​

Du testar att ta varje träd och kollar vilket som ger dig det bästa svaret. O(N*s)

Subtask 3

(7p) N<= 15

​

Vi kan testa alla (N choose K) sätt att välja K träd, och sedan beräkna mängden snö som räddas genom att välja dessa K.

​

Vi kan inse att ifall vi vill beräkna hur mycket snö som vi räddar på högersida av träd i om vi rotar träd i, om dessutom träd i-1 har blivit rotat är: rightDrop[i]

​

Annars om det träd i-1 inte är rotat så är det bara: totalDrop[i]-leftDrop[i]

​

O((N choose K) * N)

Subtask 4 & 5

(11p + 23p) N<= 2000

​

Vi kan skapa en DP.

​

Vi definierar dp(i, k, previousPushed) = Maximala antalet snö som kan räddas från i och framåt ifall endast k till träd får räddas.

​

States: O(N*K*2) = O(N*K)

Transitions: Vi kan antingen rädda träd i, eller inte. O(2) = O(1)

Totalt: O(NK)

Subtask 6 & 7 (Fullpoäng)

(31p + 18p) N<= 10^5

​

​

Vi måste på något sätt få bort en faktor i vår DP, och vi inser då att vi kan använda oss av

Alien-tricket!

​

Vi kan använda Alien-tricket eftersom vi ser att DP(N,K) är konkav funktion beroende på K.

​

​

​

Vi kan introducera en “penalty” för varje gång man räddar ett träd. �Vi binärsöker efter det penalty som ger oss att antalet träd vi räddar blir exakt K.�Se Joshuas föreläsningsanteckningar om DP-optimeringar för mer info.