Lösningar 2025
Lösningsförslag
Hair Dyeing
By: Joshua Andersson
Problem
Given array with N elements, each less than 10, determine number of subarrays where no two adjacent elements are equal.
Also handle Q queries, printing the number of such subarrays after each one.
Subtask 1
There are 2^N subarrays. Try each one in O(N).
O(N*2^N)
Subtask 2
Do a DP: for each item, either include it or don’t include it. To know if we can add a certain item, keep track of the index of the last item we included. O(N^2)
Subtask 3
Do a DP: for each item, either include it or don’t include it. To know if we can add a certain item, keep track of the value of the last item we included. O(10N)
Subtask 4
Write previous DP bottom-up.
DP[i]=1 + DP[j], over all j < i where arr[i]!=arr[j]
Subtask 4
Write previous DP bottom-up.
DP[i]=1 + DP[j], over all j < i where arr[i]!=arr[j]
From this, we can let CNT[x] = sum of all DP[i] where arr[i]=x
Then, we can rewrite the transition as
CNT[x]+=1+CNT[j] for each 0 <= j <= 9 where j != x
Subtask 4
Write previous DP bottom-up.
DP[i]=1 + DP[j], over all j < i where arr[i]!=arr[j]
From this, we can let CNT[x] = sum of all DP[i] where arr[i]=x
Then, we can rewrite the transition as
CNT[x]+=1+CNT[j] for each 0 <= j <= 9 where j != x
or
CNT[x]+=1+sum(CNT[j])-CNT[x] for each 0 <= j <= 9
=>
CNT[x]=1+sum(CNT[j]) for each 0 <= j <= 9
Subtask 4
If we maintain the sum of all CNT, we can do each transition in O(1).
O(N) total for each update
Pretty tight time limit to distinguish between O(10N) and O(N)�
Python? womp womp
Subtask 5
Big jump in difficulty. We likely want to place our DP in a segment tree. Right now, we can add one element to our DP in O(1). What do we need to be able to “merge” two DP:s?
Somehow, we need to express “if the DP had these values,
how will it change the DP
after processing this
interval?”
Subtask 5
Let’s focus on an example:
0 1 0
0: DP[0]+=1+DP[1]. Let a=1+DP[1]
1: DP[1]+=1+DP[0]+a=2+DP[0]+DP[1]. Let b=2+DP[0]+DP[1]
0: DP[1]+=1+DP[1]+b=3+DP[0]+2*DP[1].
Adding all of these up, we get
DP[0]+=1+DP[1]+3+DP[0]+2*DP[1]=4+DP[0]+3*DP[1]
DP[1]+=2+DP[0]+DP[1]
Subtask 5
As long as we expand, the DP changes will always be of the form
DP[0]+=a+b*DP[0]+c*DP[1]
DP[1]+=d+e*DP[0]+f*DP[1]
This doesn’t work with segment trees. However, we can do a sqrt decomposition!
For each block, store a,b,c,d,e,f
Let b=block size. We can update one block in O(b)
We can then compute the answer in O(n/b).
Letting b=sqrt(N), we solve the subtask
Subtask 6
Generalize the previous solution
Subtask 7/8
Optimize the previous solution.
Let V be the max value. Current times:
updates: O(b*V^2)
calculating answer: O(n/bV^2)
We can speed up updates. The idea is similar to the O(10N) -> O(N) by keeping track of the sum of each row.
By optimizing b, we get O(sqrt(n)*v^1.5) per update
Lots of room for constant-factor optimization
Alternate solution
Previously, we assumed that we could only add one element to the DP matrix. What if we could merge two? Likely candidate is matrix multiplication. Then, we could do a segment tree of matrices.
Alternate solution
Requires a lot of intuition for matrix multiplication. We need to do point-wise addition, which is a little difficult with matrix multiplication.
Alternate solution
Barely…
(although memory could be reduced by a factor of almost 16 at the cost of performance)
Which one is “better”?
original slide said: “… you have no reason to good enough at matrix multiplication to come up with solution 2 in reasonable time”
Seems that the easiest one is matrix multiplication!
O(log(N)*V^3) vs O(sqrt(N)V^1.5)
I prefer the sqrt solution. Easier to implement and IMO better complexity
Weird, evil trick to make it slightly faster
Precompute the answer for every possible array of size 4. Then, build segment tree over this array of size N/4. Method of four russians
(The judges have not implemented this)
Open question
Can we do better than a segment tree when maintaining
a op b op c op d ….
under point updates? Assume that op is associative, but not commutative
We can’t use fenwick trees, since op is not invertible
If op is cheap, then high branching factor segment trees are probably better, but this is not the case for this problem
Quicksand
By: Nils Gustafsson
Problem
Given distances in a grid where some cells have quicksand, answer queries about which cells have quicksand and update distances.
Insight 1
-1
-1
-1
-1
6
6
5
6
7
6
5
4
5
6
5
4
3
4
3
4
3
2
1
2
3
2
1
0
1
2
Let’s understand which cells must have quicksand.
Insight 1
-1
-1
-1
-1
6
6
5
6
7
6
5
4
5
6
5
4
3
4
3
4
3
2
1
2
3
2
1
0
1
2
Let’s understand which cells must have quicksand.
If two cells with distances x and y are adjacent, and x < y+1, then the cell with x must have quicksand!
Subtask 2
It turns out that the sand we found is the only necessary sand.
Slow solution: place the necessary sand and run a BFS to see if you get the correct distances, for each query.
Full solution
The main theme of this problem is:
“Finding shortest distances requires BFS which is O(N), but checking if some given distances are correct is a lot simpler.”
The given distances will have some constraints that need to be satisfied, but these are “local” in a way that will allow us to handle updates in O(poly(max_degree))
Full solution
To see when a placement of sand is valid, draw the shortest path DAG and see when it is valid.
Draw a directed edge from i to j if
di < dj
0
1
1
2
3
3
Full solution
A shortest path DAG is valid if
0
1
1
2
3
3
Full solution
0
1
1
2
3
3
1
If there is a reachable vertex that does not have a parent in the shortest path DAG, then it is impossible (print “fel”).
Full solution
0
1
1
2
3
3
Vertices that have children that only have one parent would cause the DAG to become invalid if sanded. They are the nej-vertices.
Full solution
Summary:
Full solution
When an update happens at vertex v, all of this data only changes locally around v. sand[i] only changes for v and its neighbours, and BAD[i] only changes for vertices within distance 2 of v, since they only depend on sand[i] and D[i].
Full solution
When an update happens at vertex v, all of this data only changes locally around v. sand[i] only changes for v and its neighbours, and BAD[i] only changes for vertices within distance 2 of v, since they only depend on sand[i] and D[i].
Just make sure to update everything in the right order.
Train Mania
By: Joshua Andersson
Problem
You are given a tree. Each edge takes some time to cross. K times, trains will depart from a node at time t. Taking it takes you to some other (arbitrary) node d seconds later.
For each starting position, find the maximum number of trains you could take.
Subtask 1
All times are small. Do a DP, where we keep track of node and time.
DP[u][t] = max number of trains
Check which trains that you can get on
Either O(NT) or O(NTK), doesn’t really matter
Subtask 2
Times are no longer small. We will still do a DP, but we need to characterize how we move in the tree. We only need to consider movements between starts/ends of train journeys. For each starting node, we will do a DP:
Sort all trains by their departing in ascending order time, process them in this order. Before every train leaves, check the best way to have to come to this node.
Subtask 2
For example: say we are node u, a train is departing at time t. We want to check “what is the most number of trains we could have taken to come to node u at time t (or earlier)”? Insight: we only need to check previous train arrivals. For each one, compute distance between it and u, check if we could have made it.
Each start node: O(N)
For each train: O(K)�For each previous train: O(K)
Distance: O(N)
Total: O(N^2K^2)
Subtask 3
Many opportunities to optimize. Easiest (?): precompute distances between all pairs of nodes. We can now check distances between nodes in O(1)
O(N^2+NK^2)
Subtask 4
Could we do just one DP for all trains? Yes! First, precompute all distances in O(N^2)
Then, simulate the DP backwards. Then, we can use the DP information to find the info for each starting point in O(K)
O(N^2) precomp
O(K^2) DP
O(NK) answer all nodes
N,K small => AC
Subtask 5
What does the “the smallest t is larger than the sum of all s” mean?�The answer is the same for all nodes
O(N^2) precomp
O(K) answer all nodes
O(K^2) dp
Let’s do less precomp. We can get distances between two nodes in a tree in log(N) time by using LCA+depth
Subtask 5
O(NlogN) precomp
O(KlogN) find answer for one node
O(K^2log(N)) do DP
Since K is small, we solve the subtask
https://cses.fi/alon/task/1135
https://usaco.guide/plat/binary-jump?lang=cpp#explanation-4
Subtask 6
For full solutions implemented with bad constant factor (or cheese?)
Subtask 7
Two solutions: you can either have full solutions that run in�~O((N+K)log(N)log(K)*degree(U)) (all nodes have degree <=2)
Or you can solve the problem using a segment tree
Details left as an exercise to the reader (pretty much as hard as intended solution. Fun exercise in segment trees!)
Subtask 8
Make sure to understand exactly what the solution to subtask 4 is doing. We are going to speed it up. We basically have the problem “I am the final station of a train at time T. Which is the best train I can “attach” to?”
More formally, consider all trains departing after T.
For each one, we know that it departs from node U at time D, and if we can get to it at time D (or earlier), we can travel along P trains.
So our DP then basically asks: over all (U,D,P), what is largest P we can reach?
Subtask 8
So our DP then basically asks: over all (U,D,P), what is largest P we can reach?
Suppose we are at node V at time T. Then, we want the largest P over all pairs where
dist(U,V)+T<=D
We are going to solve this using centroid decomposition.
Subtask 8
Make sure to understand how to use centroid decomposition to do path queries and updates. Here is a tutorial:
https://robert1003.github.io/2020/01/16/centroid-decomposition.html
And here are some practice problems:
https://judge.progolymp.se/contests/centroid/problems
Xenia and tree is classical. Feel free to search for more info yourself on how it works. I won’t be explaining centroid decomp in detail here
Subtask 8
We are at node V at time T. over all (U,D,P), what is largest P we can reach?
max(P) where
dist(U,V)+T<=D
We decompose this path into 2 parts for every centroid parent C:
U->C and V->C
Then, we get
dist(U,C)+dist(V,C)+T<=D
Equivalently,
dist(U,C)+T<=D-dist(V,C)
Subtask 8
dist(U,C)+T<=D-dist(V,C)
Notice that we don’t need to exclude the centroid subtree we came from, as double counting is always suboptimal
So when we insert some dp-value into a centroid, it is sufficient to only insert
(D-dist(V,C),P)
And then when we query, we compare with the distance dist(U,C)+T
Now, we have the subproblem of “Given lots of pairs (A,P), what is the max P where A >=B”? (A=dist(V,C), B=dist(U,C)+T)
Subtask 8
“Given lots of pairs (A,P), what is the max P where A >=B”? (A=dist(V,C), B=dist(U,C)+T)
Multiple solutions. The judge solutions uses coordinate compression+fenwick trees. Can also use set + lower bound (stalin sort) or treaps
We don’t need binary lifting: each centroid can precompute distances to all nodes in its subtree during centroid decomposition. O((N+K)log(N)log(K))
Subtask 8
When we have this, when doing DP, we can find the optimal transition train in O(log(N)log(K)), update in O(log(N)log(K))�Then we can find the answer for each starting point with a query in O(log(N)log(K))
Subtask 8
O((N+K)log(K)) binary searches
O((N+K)log(K)) fenwick tree operations
binary searches can all be done offline. So the bottleneck becomes fenwick tree operations (which are *very* fast)
Difficult to get AC in python, but we think it’s possible. Binary searches are the bottleneck, so if we do them offline, it might be possible. Might need fast centroid decomposition too. (Just finding the decomposition is slow..)
Resultat!
Resultat!