# Konsonantkoll Det är inte så mycket problemlösning i den här, utan snarare att implementera den. Här är enkel lösning: ```python consonants = "bcdfghjklmnpqrstvwxz" line=input() ans = "" for c in line: if len(ans)<2 or not (c==ans[-1] and c==ans[-2] and c in consonants): ans += c print(ans) ``` # Godishalsbandet Låt oss formulera om problemet lite så det blir lättare att tänka på. Gör om strängen till en array $A$ av $N$ heltal, där alla **B** blir ettor, och **V** nollor. För att slippa oroa oss om cirkulära arrayer kan vi bara lägga till en kopia av $A$ till slutet av $A$. Det är jobbigt att tänka på klippningar, så efter lite tänk kan vi insé att varje klippningar motsvarar "om vi börjar på index i får vi $A[i]+A[i+1]+\dots+A[i+\frac{N}{2}-1]$ stycken godisar". Så om vi testar varje $0 \leq i \leq N-1$ får vi rätt svar, men detta tar ju $O(N^2)$ tid. För att optimera lösningen kan vi försöka återanvända arbete. Låt $S_i=A[i]+A[i+1]+\dots+A[i+\frac{N}{2}-1]$. Vad är skillnaden mellan $S_0$ och $S_1$? $$S_0=A[0]+A[1]+\dots+A[\frac{N}{2}-1]$$ $$S_1=A[1]+\dots+A[\frac{N}{2}]$$ Vad är skillnaden mellan de? $$S_1-S_0=-A[0]+A[\frac{N}{2}]$$ Så vad vi kan göra är att beräkna $S_0$, och sen beräkna varje $S_1$, $S_2$ osv genom att ta bort och lägga till ett tal. Denna tekniken brukar kallas sliding window. ```python halsband=input() godis = [c == 'B' for c in halsband]+[c == 'B' for c in halsband] ans = 0 n = len(halsband) num_candies = sum(i for i in godis[:n//2]) for i in range(n): ans = max(ans, num_candies) num_candies -= godis[i] num_candies += godis[i+n//2] print(ans) ``` # Tv-tittande Om vi befinner oss på en viss dag är det ganska svårt att avgöra vilken tv-serie som är bäst att titta på. Istället vi att bygga upp en bank av *extratid*. Extratid är dagar där vi hade kunnat kollat på tv, men vi inte vad vi ska kolla på, så vi sparar den. När vi väl kommer till en födelsedag vet vi vilka serier vi måste kolla på. Då kan vi helt enkelt kolla om vi har nog med extratid för att kolla på alla tv-serierna som behövs. Så ett sätt man kan tänka på det är att när vi väl är på en födelsedagsfest så tidsreser vi tillbaka och bestämmer vad vi skulle ha kollat på. ```python n,k=[int(i) for i in input().split()] watchtime_left = [int(i) for i in input().split()] extra_time = 0 curr_day = 0 for i in range(n): line = [int(i) for i in input().split()] date = line[0] shows = line[2:] extra_time += (date-curr_day)*10 for show in shows: show-=1 if watchtime_left[show]>0: if watchtime_left[show]>extra_time: print("Nej") quit() extra_time-=watchtime_left[show] watchtime_left[show]=0 curr_day = date+1 print("Ja") ``` # Rullband Som tur är så är korridoren ganska kort! Detta låter oss modellera problemet som en graf: varje meter är en nod. Hur ser kanterna ut? - Varje nod har en kant till båda noderna precis till vänster och höger om den med vikt $g$. Detta representerar att vi kan ett steg till höger eller vänster på $g$ sekunder. Kanten till vänster är nödvändig eftersom man ibland vill ta ett rullband och sen gå baklänges. - För varje rullband som går från $a$ till $b$ drar vi en kant $a \rightarrow b$ med vikt lika med hur lång tid det tar att använda rullbandet. Nu vill vi helt enkelt hitta snabbaste sättet att ta oss från början till slutet i en viktad graf. Djikstra är perfekt för detta! Notera att denna implementation av djikstra är suboptimal, eftersom vi pushar saker i kön när vi kanske inte egentligen behöver göra det. Snabbare är att hålla koll på kortaste vägen hittills till varje nod och bara pusha om det förbättrar avståndet. Jag är ganska säker på att det finns testdata som gör att den är lika långsam som min, men i praktiken har ingen såna, så det blir snabbare. Det är i alla fall lite lättare att koda det såhär. ```python from heapq import heappop, heappush n,m,g=[int(i) for i in input().split()] rullband = [[] for i in range(m+1)] for i in range(n): s,e,d=[int(i) for i in input().split()] rullband[s].append((e,d)) pq = [] heappush(pq, (0, 0)) vis = [0 for i in range(m+1)] while True: d, u = heappop(pq) if u==m: print(d) quit() if vis[u]: continue vis[u]=1 if u>0: heappush(pq, (d+g, u-1)) heappush(pq, (d+g, u+1)) for dest,dist in rullband[u]: heappush(pq, (d+dist, dest)) ``` Notera att problemet går att lösa även för långa korridorer- dom enda platserna som egentligen spelar roll är början och slut av korridoren och början och slutet av varje rullband, vilket ger $O(N)$ noder och kanter. Detta är dock pilligare, så vi gör inte det eftersom det inte behövs. # Pariserhjulet För dom första 50 poängen så funkar det fint att bara simulera problemet precis så som dom efterfrågar. För subtask 3/4 ger det problem eftersom folk stannar så länge i pariserhjulet. För att få mer poäng behöver vi byta perspektiv lite. Istället för att simulera hela hjulet kan vi representera hjulet på följande form: för varje person i det, när kommer dom hoppa av? Vi vet då att gruppen med minst tidpunkt att hoppa av kommer hoppa av först, så vi kan spola fram i tiden tills dess. Sen stiger ett nytt lag på, och så lägger vi in tiden när dom kommer hoppa av osv osv. Så vi behöver alltså en datastruktur som kan: - Ge oss minsta värdet i den - Ta bort minsta värdet - Lägga till ett värde Vilket heaps är perfekta för! ```python import heapq n, m = [int(i) for i in input().split()] vagnar = [] queue = [int(i) for i in input().split()] for i in range(n): if len(vagnar)==m: # Kicka av någon time = vagnar[0] # tiden av dom som kickades heapq.heappop(vagnar) else: # om den inte är full än går det på en person per sekund # så i råkar också vara tiden lag i går på! time = i leave_time = time + queue[i] * m heapq.heappush(vagnar, leave_time) print(max(vagnar)) # Simulera inte dom sista; när alla väl är på, # så räcker det att skriva den långsammaste ``` # Bonsai Det finns en relativt simpel lösning för alla grupper förutom den sista. Låt oss börja bygga trädet från nod $u$ (i delgrupper 1-4 räcker det med $u=0$, i delgrupp 5 kan vi testa alla $N$ möjliga $u$). Låt oss definiera $t(u,p)$ = minsta möjliga tiden att växa subträdet rotat vid $u$. Det vill säga, vi tar bort komponenten som förälderkanten kopplar ihop oss med. För att kunna beräkna $t(u,p)$ kan vi först insé att tiden det tar att växa ut varje barns subträd är oberoende. Så det första vi gör är att beräkna $t(e,u)$ för varje barn, det vill säga tiden för att växa ut varje subträd bland $u$'s barn. Så det enda vi behöver göra nu är att bestämma i vilken ordning vi ska växa ut kanter till våra barn. Hur långd tid tar det att växa ut en given ordning av barn? Det tar: $$max(t(e_1,u)+1,t(e_2,u)+2,\dots,t(e_n,u)+n)$$ Det vill säga, för första barnet tar det en sekund att växa kanten till barnet, och sen tar det $t(e_1,u)$ sekunder att växa klart subträdet. Vi behöver dock inte sitta still och vänta; vi kan direkt efter växa en kant till barn nr 2, osv. Utifrån denna formeln borde det går det att inse att det är optimalt att växa ut den största $t(e,u)$ först, näst största därefter osv. Följande lösning ger därmed 72 poäng: ```python import sys sys.setrecursionlimit(int(1e5)) n=int(input()) adj = [[int(i) for i in input().split()][1:] for j in range(n)] def t(u, p): child_times = [] for e in adj[u]: if e==p: continue child_times.append(t(e,u)) child_times.sort(reverse=True) ret = 0 for i in range(len(child_times)): ret = max(ret, child_times[i]+i+1) return ret if n <= 250: print(min(t(i,i) for i in range(n))) else: print(t(0,0)) ``` Härifrån kan du antingen snabba upp den med smått pillig tree reroot dp, vilket du kan läsa mer om [här](https://hackmd.io/@Matistjati/Sk3WrJwlkx). Eller så kan du helt tänka om lösningen. Ett vanligt trick kan ibland vara att göra problemet "baklänges". Så vad händer om vi börjar med det fulla trädet och försöker göra processen baklänges? Jo, varje nod som är granne med ett löv får ta bort exakt ett löv. Detta kan sedan producera nya löv, vilket fortsätter tills trädet är borta. Med detta perspektivet är det ganska uppenbart att det inte spelar roll vad vi gör om vi löser problemet baklänges, så länge vi poppar så många löv som möjligt samtidigt. Koden blir lite smått pillig. Går kanske att förenkla den smått. ```python n=int(input()) adj = [[int(i) for i in input().split()][1:] for j in range(n)] degree = [len(adj[i]) for i in range(n)] adjacent_leafs = [[] for i in range(n)] adjacent_to_leaf = set() for i in range(n): adjacent = False for e in adj[i]: if degree[e]==1: adjacent_leafs[i].append(e) adjacent=True if adjacent: adjacent_to_leaf.add(i) # Make set adjacency list so we can remove edges adj_set = [set(adj[i]) for i in range(n)] # Do rounds of popping one leaf from node adjacent to leafs # until tree is destroyed rounds = 0 while len(adjacent_to_leaf): rounds += 1 new_adjacent_to_leaf = set() for u in adjacent_to_leaf: l = adjacent_leafs[u][-1] del adjacent_leafs[u][-1] adj_set[u].remove(l) degree[u] = len(adj_set[u]) # We removed all of our edges, so we are now a leaf if degree[u] == 1: # next(iter(adj_set[u])) is basically: give us the only # element left in adj_set[u] new_adjacent_to_leaf.add(next(iter(adj_set[u]))) adjacent_leafs[next(iter(adj_set[u]))].append(u) # We must check this at the end, since the following may occur: # some node deletes its last leaf. Then, later, a non-leaf neighbour # becomes a leaf because it deleted a leaf for u in adjacent_to_leaf: if len(adjacent_leafs[u]): new_adjacent_to_leaf.add(u) adjacent_to_leaf = new_adjacent_to_leaf print(rounds) ``` # Glasspelet ## Subtask 1 När spelet väl börjat har varje spelare alltid 2 val: äta glassen till höger, eller äta glassen till vänster (så länge dom inte har förlorat). Därmed kan vi svara på varje query oberoende i $O(N2^N)$ genom att rekursivt testa alla möjligheter, och kolla i linjär tid om någon vunnit. ```python from sys import setrecursionlimit setrecursionlimit(int(1e5)) n,k,q=[int(i) for i in input().split()] icecreams = [int(i) for i in input().split()] def is_valid(l, r): if l>r or r<l: return False flavors = set() for i in range(l,r+1): flavors.add(icecreams[i]) return len(flavors)==k def rec(l, r): ret = 0 # 0=jag förlorar, 1=jag vinner # kan jag göra ett drag så att moståndaren # hamnar i en förlorande position? if is_valid(l+1,r) and rec(l+1,r)==0: ret = 1 if is_valid(l,r-1) and rec(l,r-1)==0: ret = 1 return ret for i in range(q): l,r=[int(i) for i in input().split()] l-=1 r-=1 if not is_valid(l,r): print(0) continue print("1" if rec(l,r) else "2") ``` Saker att notera om implementationen: det är väldigt vanligt att när folk implementerar rekursiva spel, så har dom en parameter "är jag spelare 1 eller 2". Om man tänker till dock så kan vi göra som här, och inte ha det. Det finns problem där denna pyttelilla optimering krävs. ## Subtask 2 Ta förra lösningen och dp:a rec. Notera att vi inte behöver återställa dp:n mellan varje query, utan vi kan lika gärna spara den. Varje state tar $O(N)$ att kolla på grund av is_valid, så vi får $O(N^3)$ sammanlagt. ## Subtask 3 Vi måste kunna kolla is_valid i $O(1)$ för att få ner det till $O(N^2)$. Lättaste sättet att göra detta är troligtvis att förberäkna alla giltiga intervall samtidigt i $O(N^2)$. ## is_valid i $O(N)$ Jag pallar inte gå igenom alla specialfall. Just nu har vi två långsamma delar- en DP med kvadratiskt mycket state, och förberäkning av is_valid i $O(N^2)$. För fullösning behöver vi optimera ner båda till $O(N)$. Vi börjar med att förberäkna is_valid i $O(N)$. Vi säger att en intervall $[l,r]$ är om is_valid($l,r$)=True. För att göra det behöver vi insé följande: om vi har ett intervall [l,r] som är bra, så kommer $[l,r+1]$ också vara True. Det vill säga, om ett intervall är bra kan vi utvidga det till höger, och det kommer fortsätta vara bra. Detta innebär att det räcker att beräkna för varje $l$: vilket är det första $r$ där $[l,r]$ är bra? Ett sätt att göra det är att för varje $l$ göra en binärsökning över $r$. Då reduceras problemet till att "i ett intervall, finns det $K$ unika värden"? Eller, ekvivalent "hur många unika värden finns i ett visst intervall"? Detta går att lösa, men kräver för avancerade datastrukturer (persistenta segmentträd). Men om ni stöter på denna sortens "först går det inte, sen går det" borde ni alltid tänkte på binärsökning först! För att lösa det måste vi insé nåt ännu starkare: låt f($l$)=minsta $r$ där is_valid($l,r$)=true. Då håller det att $f(l+1) \geq f(l)$ för alla $l$. Det vill säga, om vi har ett intervall som är bra och flyttar $l$ åt höger ett steg, så kommer vi behöva flytta $r$ åt höger för att göra intervallet bra. Detta låter oss lösa problemet med en tvåpekarslösning: 1. Börja med $l=r=0$ 2. Medan $[l,r]$ inte är bra, flytta $r$ åt höger ett steg 3. Nu har vi beräknat $f(l)$. Öka $l$ med 1 och gå tillbaka till steg om $l < N$ Hur håller vi snabbt koll på om intervallet är bra? Vi kan hålla koll på hur många vi har av varje smak i intervallet, och antalet unika smaker vi har. Att ändra detta tar $O(1)$. $l$ och $r$ rör sig $N$ gånger var sammanlagt, så vi får $O(N)$. Här är en lösning med $O(N)$ förberäkning och $O(N^2)$ dp: ```python from sys import setrecursionlimit setrecursionlimit(int(1e5)) n,k,q=[int(i) for i in input().split()] icecreams = [int(i) for i in input().split()] first_valid = [-1 for i in range(n)] num_unique = 0 how_many = [0 for i in range(k)] r = 0 for l in range(n): # Move r to the right while r < n and num_unique < k: if how_many[icecreams[r]]==0: num_unique += 1 how_many[icecreams[r]] += 1 r += 1 if num_unique==k: first_valid[l] = r-1 # move l to the right if how_many[icecreams[l]]==1: num_unique -= 1 how_many[icecreams[l]] -= 1 dp = [[-1 for i in range(n)] for j in range(n)] def is_valid(l, r): if l>r or r<l: return False if first_valid[l]==-1: return False return r >= first_valid[l] def rec(l, r): if dp[l][r]!=-1: return dp[l][r] ret = 0 # 0=jag förlorar, 1=jag vinner # kan jag göra ett drag så att moståndaren # hamnar i en förlorande position? if is_valid(l+1,r) and rec(l+1,r)==0: ret = 1 if is_valid(l,r-1) and rec(l,r-1)==0: ret = 1 dp[l][r] = ret return ret for i in range(q): l,r=[int(i) for i in input().split()] l-=1 r-=1 if not is_valid(l,r): print(0) continue print("1" if rec(l,r) else "2") ``` ## Spela spelet i $O(N)$ Nu kan vi beräkna is_valid i $O(1)$ för godtyckliga $l,r$. Men hur ska vi optimera vår DP? Vi har kvadratiskt mycket state och det känns väldigt svårt att bli av med det. Vi kommer använda en vanlig strategi för problem som handlar om att spela ett spel optimalt: printa ut svaret och försöka hitta ett mönster. Det känns då rimligt att printa en 2D-matris för varje $l,r$, som indikerar om svaret är 0,1,2 eller 2. Typiskt ser detta ut ungefär såhär: ```perl 000012112112121212112121212121 000021121121212121121212121212 000001211212121211212121212121 000002112121212112121212121212 000000021212121121212121212121 000000000000001212121212121212 000000000000002121212121212121 000000000000001212121212121212 000000000000002121212121212121 000000000000001212121212121212 000000000000002121212121212121 000000000000000000000212121212 000000000000000000000121212121 000000000000000000000212121212 000000000000000000000121212121 000000000000000000000212121212 000000000000000000000121212121 000000000000000000000212121212 000000000000000000000121212121 000000000000000000000212121212 000000000000000000000001212121 000000000000000000000002121212 000000000000000000000000012121 000000000000000000000000021212 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 ``` Vad kollar du på exakt? Första raden är $l=0$, andra raden $l=1$ osv. Första kolumnen är $r=0$, andra $r=1$ osv. För att göra det ännu mer lättläsligt ändrar vi noll till . och 2 till 0. ```ru ....10110110101010110101010101 ....01101101010101101010101010 .....1011010101011010101010101 .....0110101010110101010101010 .......01010101101010101010101 ..............1010101010101010 ..............0101010101010101 ..............1010101010101010 ..............0101010101010101 ..............1010101010101010 ..............0101010101010101 .....................010101010 .....................101010101 .....................010101010 .....................101010101 .....................010101010 .....................101010101 .....................010101010 .....................101010101 .....................010101010 .......................1010101 .......................0101010 .........................10101 .........................01010 .............................. .............................. .............................. .............................. .............................. .............................. ``` Har prickarna något att göra med $f(l)$? Dvs, första $r$ där $[l,r]$ är bra. Låt oss plotta # om $[l,r]$ är bra, annars punkt. ```javascript ####.......................... ####.......................... #####......................... #####......................... #######....................... ##############................ ##############................ ##############................ ##############................ ##############................ ##############................ #####################......... #####################......... #####################......... #####################......... #####################......... #####################......... #####################......... #####################......... #####################......... #######################....... #######################....... #########################..... #########################..... ############################## ############################## ############################## ############################## ############################## ############################## ``` Vi kan alltså märka att alla som var . i första bilden är exakt dom intervallen $[l,r]$ som är dåliga. Men vad händer bland alla 0/1or? Vi kan märka att för varje rad finns det ett första värde efter att intervallet blir bra. Detta värde kopieras sedan upp diagonalt! Alltså behöver vi bara hitta vem som vinner för states som ligger precis kanten bredvid ett intervall som inte är bra. DP:n kan bara kan röra sig $l+1$ eller $r-1$, vilket motsvarar ner eller åt vänster. Därför kan den bara besöka som mest som mest $O(N)$ tillstånd om vi bara beräknar dom precis på kanten. Notera att du egentligen behöver hitta den första som vinner i varje diagonal. Jag har markerat dessa med X: ```javascript ####X......................... ####XX........................ #####X........................ #####XXX...................... #######XXXXXXXX............... ##############X............... ##############X............... ##############X............... ##############X............... ##############X............... ##############XXXXXXXX........ #####################X........ #####################X........ #####################X........ #####################X........ #####################X........ #####################X........ #####################X........ #####################X........ #####################XXX...... #######################X...... #######################XXX.... #########################X.... #########################XXXXX ############################## ############################## ############################## ############################## ############################## ############################## ``` När du väl har beräknat dessa i $O(N)$ kan du svara på varje query i $O(1)$ genom att kolla på vilken diagonal queryn befinner sig på. Men varför stämmer detta mönstret? Låt $rec(l,r)$=den som vinner för $l,r$. Vad mönstret säger är egentligen att $rec(l,r)=rec(l-1,r+1)$ (övertyga dig själv om att detta är ekvivalent med diagonal-mönstret). Det vill säga, om vi utvidgar mönstret åt vänster och höger samtidigt vinner samma person. Detta beror på att spelare kan spegla drag. Låt säga att $(2,4)$ är en förlorande position att vara på. Om vi är vid $(1,5)$ och det är dags för spelare 2 att göra ett drag, så är spelare 1 vinnande: - Om spelare 2 gör $(1,5) \rightarrow (2,5)$ kan spelare 1 sen göra draget $(2,5) \rightarrow (2,4)$ och vinna. - Om spelare 2 gör $(1,5) \rightarrow (1,4)$ kan spelare 1 sen göra draget $(1,4) \rightarrow (2,4)$ och vinna. Jag lämnar implementationen av detta som en övning. Notera att du absolut inte kan försöka beräkna $rec(l,r)$ som inte är diagonalt bredvid ett # (intervall som inte är bra), för det är jättelätt att besöka hela rutnätet och få $O(N^2)$ isåfall.