Onlinekval 2026
Lösningsförslag
Tvåpotensernas kraft
Av: Harry Zhang
Problem
Givet ett heltal N som inte är större än 10^18,
bestäm om talet är en tvåpotens eller inte.
Lösningsidé - O(log(N))
Det finns inte så många tvåpotenser. 60 stycken mindre än 10^18.
Så vi kan generera alla och kolla om någon är lika med indatan.
O(1)
Om man kollar på bitmönstret av tvåpotenser kan man komma fram till att ett tal x är en tvåpotens om
x&(x-1)==0
Där & är bitwise and.
T.ex:
8 = 1000 12= 1100
7 = 0111 11= 1011
7& 8 = 0000 11& 12= 1000
Absolut bio
Av: Harry Zhang
Problem
Winston hanterar en biosalong med N plats, där han snabbt måste avgöra om en plats är ledig eller upptagen när någon vill sätta sig eller flytta sig. ��Vid varje händelse ska han svara ”Ledig” om målplatsen är fri och uppdatera statusen, annars ”Upptagen”.
40 poäng, N <= 10^4
Indexen av sittplatserna är mellan 1 och 10^4
Vi kan skapa en lista av storlek 10^4, och markerar på varje index 1 ifall platsen är upptagen, annars 0.
Sen för varje händelse, uppdaterar vi listan enligt instruktionerna från uppgiften.
Minneskomplexitet: O(N)
Fullösning
Istället för en lista med N positioner, kan vi använda ett set.
�Vi lägger in indexen av de positioner som är upptagna i vårt set, och uppdaterar genom att radera och lägga till element till vårt set.
Minneskomplexitet: O(Q)
Kattparadiset
Av: Erik Hedin
Implementerad av: Harry Zhang
Problem
Givet N sängar av olika färger, hitta en placering av sängarna runt en cirkel så att inga två sängar bredvid varandra har samma färg.
Problem
Givet N sängar av olika färger, hitta en placering av sängarna runt en cirkel så att inga två sängar bredvid varandra har samma färg.
Lösning
När är det omöjligt?�
Om det finns någon färg med fler än N/2 sängar, går det inte att placera ut sängarna på ett giltigt sätt.
Vi kommer nu visa några olika sätt
att placera ut sängarna, så länge
alla färger dyker upp <= N/2 gånger.
Lösning 1 - Greedily välj den största
Håll koll på den färg som det finns mest av.
Vi använder den färg som det finns mest av, så länge det inte är samma färg som färgen innan.
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Lösning 1 - Greedily välj den största
Pitfall: Den sista sängen som används får inte vara samma som den första.
Lösning 1 - Greedily välj den största
Genom att antingen specialhantera och markera den första sängen, så att den tas först när det finns flera som har lika många sängar kvar är detta lösbart i O(NK). �
Detta görs genom att iterera igenom alla färger för varje säng man vill placera.
Lösning 1 - Greedily välj den största
Genom att antingen specialhantera och markera den första sängen, så att den tas först när det finns flera som har lika många sängar kvar är detta lösbart i O(NK). �
Detta görs genom att iterera igenom alla färger för varje säng man vill placera.
Lösning 1 - Greedily välj den största
För att göra lösningen snabbare, kan man använda en prioritetskö, eller max-heap.
Man kan lägga till och ta ut det största elementet från datastrukturen i O(log N) tid.
Detta ger en O(NlogN) lösning.
Lösning 2 - Linjär lösning
En annan lösning är att fylla i alla sittplatser med jämn index först, och sen alla index med udda index.
Alltså, fylla i ordningen 0,2,4,6,8,...�och sedan fylla i indexen 1,3,5,7,...
Lösning 2 - Linjär lösning
Denna lösning fungerar inte riktigt om man inte är försiktig.
Men om man börjar med att hantera den färg som det finns flest av, så kommer vi börja med att fylla i så många jämna index som möjligt. ��Vi vet att den största färgen inte kommer behöva fylla i på några udda index, eftersom det finns färre än N/2 av den största färgen.
Lösning 2 - Linjär lösning
För alla andra färger som inte är den största, kommer det alltid gå att fylla i cirkeln.
Detta går att implementera i O(N).
O(N) för att hitta den största färgen.
O(N) för att placera ut alla sängar.
Säker diktatorsortering
Av: Joshua Andersson
Problem:
Du får givet en lista med N heltal.
Definiera diktatorsortering av en lista:
Behåll en ökande sekvens, skicka resten till träningsläger.
Problem:
Du får givet en lista med N heltal.
Definiera diktatorsortering av en lista:
Behåll en ökande sekvens, skicka resten till träningsläger.
Problem:
Du får givet en lista med N heltal.
Definiera diktatorsortering av en lista:
Behåll en ökande sekvens, skicka resten till träningsläger.
Skriv ut den ökande listan och kör diktatorsortering på träningslägret. Vilka ökande listor får vi?
Subtask 1: N <= 100
Implementera algoritmen som beskriven, där vanlig diktatorsortering kör i O(N^2)
Diktatorsortering kan köra O(N) gånger, så vi får O(N^3)
Subtask 2: N <= 5000
Optimera vanlig diktatorsortering till O(N) för O(N^2) sammanlagt
Fullösning
Gör alla samtidigt. Håll koll på alla träningsläger. När du kollar på nästa tal, skapa antingen ett nytt träningsläger eller lägg till det i rätt träningsläger.
Fullösning
Fullösning
Fullösning
Fullösning
Fullösning
Fullösning
Fullösning
Notera: det enda som spelar roll för om man hamnar i ett visst träningsläger är sista talet i det.
Vi lägger in nya tal i första träningslägret vars sista tal är mindre.
Om det inte finns ett sådant skapar
vi ett nytt träningsläger.
Vi kan binärsöka för att hitta rätt
träningsläger!
Fullösning
O(NlogN)
Var försiktig så du lägger till
längst bak i listan och inte
i början. I början blir kvadratiskt
Hemlig vandring
Av: Harry Zhang
Problem
Det finns ett rutnät med NxN rutor, där alla rutor (x,y) med udda x och y är hus. Av dessa hus finns 2 hemliga hus.
Du får ställa frågor på formen “Om dessa rutor är blockerade, vad är längden på den kortaste vägen mellan dessa 2 hus?”.
Problem
Problem
Problem
dist = 4
Problem
Problem
dist = 6
Problem
dist = -1
5p - N = 5
Eftersom hus inte får vara på samma rad eller kolumn, finns det endast två möjliga svar.
5p - N = 5
För att skilja mellan dessa två fall kan vi omringa ett av husen med väggar.
5p - N = 5
För att skilja mellan dessa två fall kan vi omringa ett av husen med väggar.
d = -1
d = 4
9p - N <= 9
�När N <= 9 finns det som mest 36 par av lösningar.
En lösning är att hålla koll på alla möjliga lösningar, och göra random queries och filtrera ut alla lösningar som inte uppfyller svaret.
11p - Ett av husen är (1,1)
�Vi vet den exakta positionen av det ena huset.
Det finns ungefär 1300 möjliga lösningar.
Men om man gör en query utan några väggar, reduceras antal möjliga lösningar till som mest N//2 ≈ 37. Detta eftersom alla hus med distans d från (1,1) kommer vara på en diagonal.
Sedan kan man göra samma lösning som Subtask 2.
Subtask 4 - Minimera antal queries
En generell idé är att hålla koll på alla möjliga lösningar. ��Hur många lösningar kan det finnas?��(37*38/2)^2 = 494209
Att göra random queries och sedan filtrera ut kan fungera om man gör det på ett fiffigt sätt. Dock kan det ta för lång tid.
Subtask 4 - Minimera antal queries
Vi vänder oss istället mot några deterministiska lösningar.
Q = O(N)
Låt husen vara (x1,y1) och (x2,y2).
Vi kan börja med att hitta min(x1,x2) genom att blockera ett prefix av kolumner av rutor. Vid något prefix av kolumner kommer det vara omöjligt att ta sig emellan husen. Då vet vi vad min(x1,x2) är.
Det kan upprepas i alla 4 riktningar för att få information om alla x1,x2,y1,y2.
Q = O(N)
Q = O(N)
Q = O(N)
Q = O(N)
Q = O(N)
Q = O(N)
Med denna metod kan vi ta reda på värdena av
min(x1,x2)
max(x1,x2)
min(y1,y2)
max(y1,y2)
�Det ena huset måste då antingen vara (min(x1,x2), min(y1,y2))
eller (min(x1,x2), max(y1,y2).
Då husen inte delar kolumn eller rad, bestäms det andra huset unikt.
Q = O(N)
För att lista vilket av våra två lösningar som är svaret, kan vi om ringa ett av husen precis som i vår lösning för N=5.
Denna lösning använder som mest 4N + 1 <= 301 queries.
Med lite optimering på hur man gör linjärsökningen kan man få ner till som mest N <= 75 queries.
Detta ger ungefär 9 av 75 poäng.
Q = O(logN)
För att optimera det vidare, kan man istället binärsöka det minsta x sådan att svaret är -1 när man ska hitta min(x1,x2)
Samma kan göras i alla 4 riktningar.
Detta ger <= 4logN + 1 queries.
Man kan då få ungefär 34 av 75 poäng.
Q = 6
Det finns många olika konstruktioner för att lösa det på ett fåtal antal queries. ��En konstruktion är att skapa “kamm”-liknande queries.
Q = 6
Q = 6
-
=
Q = 6
-
=
Q = 6
Q = 6
Skillnaden i distansen kommer vara
2 * distans mellan max(x1,x2) till sista raden.
Liknande kan göras åt alla 4 sidor.
Med hjälp av 1 + 4 queries kan man ta reda på
min(x1,x2), max(x1,x2), min(y1,y2), max(y1,y2).
Sedan använder man 1 sista query för att särskilja de två möjliga svaren.
Ger 63 av 75 poäng.
Q = 5
Vi kan spara en query genom en liten insikt.
Låt k vara distansen mellan de två hemliga husen, om inga väggar finns. Vi kan då skriva k = |x1-x2| + |y1-y2|.
Vi studerar vad som händer när vi tar queryn som beräknar
min(x1,x2) och max(x1,x2).
Q = 5
Q = 5
Q = 5
Q = 5
Summan av dessa två queries är
exakt 2*(N-1) + 2*|y1-y2|.
Tillsammns med att
|y1-y2| = max(y1,y2) - min(y1,y2)
behöver man inte göra queryn för
t.ex. min(y1,y2).
Detta blir totalt 5 queries, och ger dig 100p på problemet.
Q < 5
Om man använder 2-3 queries filtrerar ett stort antal möjliga svar, och sedan gör 1 query som bestämmer det exakta svaret, borde man kunna få en lösning som är färre än 5 queries.
Bounty:
Den första som ger en lösning på färre än 5 queries får ett extra pris.
Byta delare
Av: Joshua Andersson
Implementerad av: Nils Gustafsson
Problem
Du får en lista med N heltal a[i].
Du kan byta talen på index i och j om a[i]%a[j]==0 eller a[j]%a[i]==0
Avgör om det går att sortera listan. Om det går, hitta en sekvens av byten med längd som mest 10^6 som sorterar den i ickeminskande ordning. N<=1000
Subtask 1: N <= 10
Det finns som mest N! permutationer, och från varje som mest N^2 swaps. Därmed hinner vi göra en BFS
O(N!N^2) om man använder sets som visitedlista
Subtask 2: Som mest 2 unika värden i listan
Först, kolla om listan redan är sorterad. Om den är det, skriv ut Ja och noll drag.
Subtask 2: Som mest 2 unika värden i listan
Först, kolla om listan redan är sorterad. Om den är det, skriv ut Ja och noll drag.
Annars, kolla om man kan byta talen. Om inte, skriv ut nej.
Subtask 2: Som mest 2 unika värden i listan
Först, kolla om listan redan är sorterad. Om den är det, skriv ut Ja och noll drag.
Annars, kolla om man kan byta talen. Om inte, skriv ut nej.
Om det går att byta på talen går det alltid.
Låt a vara den mindre och b den större
Ta första b och sista a och byt plats tills listan är sorterad
Subtask 5: det finns en etta
Ettan kan alltid bytas med vilket annat tal som helst.
Detta låter dig flytta godtyckliga tal till godtyckliga positioner med två byten
Använd detta för att sortera ett suffix
Subtask 4: X=0
Vi behöver endast skriva ut om det går eller inte.
Subtask 4: X=0
Vi behöver endast skriva ut om det går eller inte.
Betrakta grafen där varje tal är en nod, och vi drar en oriktad kant om man kan byta på två tal.
Subtask 4: X=0
Låt oss kalla varje grupp av tal som kan nå varandra en “komponent”. Hur vi än utför byten, så påverkas inte indexen som tillhör komponenterna.
Subtask 4: X=0
Vi kan för varje komponent utföra någon sekvens byten för att få vilken permutation som helst.
Alltså räcker det att bygga komponenterna, sortera varje och kolla om den slutgiltiga listan är sorterad.
Fullösning
Allt som är kvar nu är att hitta en sekvens drag som sorterar varje komponent
Det går inte alltid att använda en simpel regel som “flytta den minsta till första platsen, näst minsta till andra, etc…”
Då kan man fastna
Fullösning
Intuitivt söker vi en algoritm som placerar något tal på rätt plats och tar bort denna, på ett vis att vi aldrig kan fastna.
Notera att kanterna inte påverkas av byten. Därmed, så länge vi “tar bort” noder så att komponenten inte bryts i mindre delar, så kan vi aldrig fastna.
Fullösning
Intuitivt söker vi en algoritm som placerar något tal på rätt plats och tar bort denna, på ett vis att vi aldrig kan fastna.
Notera att kanterna inte påverkas av byten. Därmed, så länge vi “tar bort” noder så att komponenten inte bryts i mindre delar, så kan vi aldrig fastna.
Så vår algoritm blir: ta någon nod som inte särkopplar komponenten och flytta den till “rätt plats”.
Fullösning
Vi tar ett spännande träd av varje komponent!
Om vi tar bort löv, så kan dessa aldrig bryta komponenten i mindre delar.
Det blir dessutom lätt att hitta sekvensen drag som krävs för att ta ett visst tal till ett annat: ta helt enkelt den unika vägen i trädet till talet du vill komma till.
Fullösning
Eftersom vägar i träd är som längst N-1 kanter får vi N(N-1) < 10^6 drag, och algoritmen kör på O(N^2) så länge vi implementerar ordentligt
Löjtnant Slotto
Av: Joshua Andersson
Problem
Knapsack: du får upp till 2*10^5 saker, varje med en vikt och värde. Välj delmängden med störst totala värde, där summan av vikter är <= T, där T är upp till 10^6.
Vikt <= T
Värde <= 5 (VIKTIGT!!)
Subtask 2
Klassisk knapsack i O(NT) med dynamisk programmering.
https://cp-algorithms.com/dynamic_programming/knapsack.html
Subtask 3
“Klassiskt” dp-trick: byt dimensionerna i din DP.
Dynamisk programmering i O(N*max totala profit). Max totala profit är som mest N*max_l, så O(N^2*max_l).
DP[i][tot profit]=min weight
Subtask 1: l=1
Girigt: sortera på vikt. Ta billigaste tills du inte kan längre.
Subtask 4: l<=2
Girigt: per profit vill du ta ett prefix av de billigaste sakerna.
Loopa över hur många med profit 1 du vill ta. Binärsök över antalet du kan ta med profit 2. För att kunna kolla om det går snabbt, bygg en prefixsumma.
Subtask 5: l<=5
Girigt: per profit vill du ta ett prefix av de billigaste sakerna.
Låt oss betrakta att köra en girig algoritm: sortera alla saker på profit/weight och ta de största tills du inte kan längre.
Om du kunde dela upp items i mindre delar är denna optimal (fractional knapsack).
Därmed kommer du väldigt nära rätt svar: du kan skilja dig med som mest 1 sak, och därmed som mest 5 profit.
Subtask 5: l<=5
Vi kommer alltså nära rätt lösning.
Eftersom vi bara tar ett prefix av varje profit kan vi testa att öka eller minska antalet saker vi tar per profit med låt säga 20, och testa alla kombinationer av detta.
O(40^5)
Mer exakt kan man bevisa att 10 räcker. Beviset är ganska svårt tyvärr
https://arxiv.org/pdf/2105.04035
Subtask 5: l<=5
Finns fler lösningar:�D&C DP
Konvex min plus convolution
Uppskattningsvis konvex min plus convolution�Knapsack istället för brute force efter greedy
Simulated annealing
Komplicerade greedys (som inte funkar i allmänhet)..
Bergfester
Av: Arvid Kristoffersson
Implementerad av: Joshua Andersson
Problem
Du får ett träd där varje kant är riktad mot roten.
Varje person bor på en nod, kan flytta på sig.
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
För varje fest väljs först en värd ut.
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
För varje fest väljs först en värd ut.
Personerna bjudna är sedan ett
intervall till höger.
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
För varje fest väljs först en värd ut.
Personerna bjudna är sedan ett
intervall till höger.
Eller ett intervall åt vänster.
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
För varje fest väljs först en värd ut.
Intervallet måste ha värden som
ändpunkt. Ej tillåtet:
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
För varje fest väljs först en värd ut.
Intervallet måste ha värden som
ändpunkt. Ej tillåtet:
Problem
Person i känner person i+1 (mod M) och i-1 (mod M).
Vi vill hålla fester.
För varje fest väljs först en värd ut.
Intervallet måste ha värden som
ändpunkt. Tillåtet:
Problem
Anta att vi valt personer. Deras
hus är rödmarkerade.
Vi måste nu välja ett festhus.
Ett festhus är rimligt om och endast om
varje person inte behöver följa mer än
R kanter till festhuset.
Problem
Anta att vi valt personer. Deras
hus är rödmarkerade.
Vi måste nu välja ett festhus.
Ett festhus är rimligt om och endast om
varje person inte behöver följa mer än
R kanter till festhuset.
R=2: vi kan se att 2 är det enda möjliga
festhuset.
Problem
Givet en värd, hur många personer kan vi bjuda?
Subtask 1,2: N,M,Q <= 100
Vi har råd att vara långsamma.
För varje antal personer att bjuda O(M):
För varje möjligt festhus O(N):
Kolla att varje inbjuden person kan komma dit O(NM)
O(N^2M^2)
För subtask 2, flytta bara runt på personer
Subtask 3: N,M,Q <= 2000
Lösning: bitsets
För varje person, förberäkna vägen upp till roten.
[8,3,2,1]
För att kolla om en viss mängd personer
funkar, skär av den vid R.
Så om R=1 får vi
[8,3]
Subtask 3: N,M,Q <= 2000
Lösning: bitsets
Så om R=1 får vi
[8,3]
För att kolla om det går för ett intervall
personer, kolla om det finns någon nod
i alla personers R-listor.
Kan göras i O(N/64) med bitsets.
O(NMQ/64)
Subtask 5: M <= 100
Lösning: LCA
Intuitivt är bästa noden att hålla fest i den som är längst från roten, men som alla kan nå. Denna noden är känd som LCA, och är typ vad vi beräknade med bitsets. Kan beräknas i O(log(N)) för två noder. https://www.youtube.com/watch?v=dOAxrhAUIhA
För LCA håller det att LCA(a,b,c,d)=LCA(A,LCA(B,LCA(C,D)))
Så vi kan växa vårt intervall genom att beräkna LCA, och kolla om LCA-noden någonsin hamnar för långt bort.
O(Q(Mlog(M))
Subtask 4: grafen är en linje
I detta fallet är LCA lätt att beräkna: det är helt enkelt noden närmast roten. För att kolla om en viss LCA funkar behöver vi snabbt kunna avgöra om den ligger för långt bort från någon.
Vi binärsöker över hur många i cirkeln vi ska gå. LCA hittas med range minimum query över nod-djup, djupaste noden med range maximum query över nod-djup. Detta kan göras med segmentträd https://cp-algorithms.com/data_structures/segment_tree.html
Subtask 7,8
Låt oss generalisera linjelösningen. Det enda svåra är att ta LCA över ett intervall. Detta kan göras med ett segmentträd som håller på LCA av intervall.
Qlog(N)^3- en för binärsökning, en för segmentträd och en för LCA per nod
Qlog(N)^2- gör LCA i O(1) med sparse tables och euler tour
�Qlog(N)- gör “walk on segment tree” över ett LCA-segmentträd + O(1) LCA
Upsolving!
Coola klistermärken som du får om du löser problem
(NYA i år!)
Info om uttagning
Final (5-timmars tävling) (Chalmers)
16-18 januari 2026
Nordiska Juniormästerskapen (5-timmars tävling) (Onsite*)
19e mars, 2026
Läger (2 x 5-timmars tävlingar) (Chalmers)
4 dagar bland 22-31 mars, 2026
*onsite i Sverige. Inte en flerdagars olympiad, endast tävling
Resultat!
https://pokval26.kattis.com/contests/pokval26