DP II
IOI 2022 Training, Lecture 6
Agenda
DP on Tree
DP on DAG
Agenda
Subset DP
Profile DP
Agenda
Young Tableau DP
DP on Trees
DP on Trees
Usually
DP on Trees
Turns your world upside down.
DP on Trees
Usually
Coffee Shop (APIO Shortlist 2007)
Given a tree of N ≤ 106 vertices, find the minimum number of vertices you need to mark such that every vertex is at most K ≤ N distance from a marked vertex.
Construct such a set of vertices.
Coffee Shop (APIO Shortlist 2007)
Observation
If vertex u is the parent of vertex v, and not marking v will not cause something in the subtree at v to break, then it’s always better to mark u instead
Coffee Shop (APIO Shortlist 2007)
Observation
Root the tree first and process upwards
We need to determine for a node v, whether not marking it will result in some node below v being more than K hops away from any vertex
Coffee Shop (APIO Shortlist 2007)
Approach
Maintain two functions, define a “served” node to be one that is already K distance away from some marked vertex
C(v) = min depth of marked vertex below v
U(v) = max depth of unserved vertex below v
Coffee Shop (APIO Shortlist 2007)
Observation
C’(v) = 1+minw in child(v)C(w) to find min depth of marked vertex from v without marking v
An unserved child under some child wi may be served by a marked vertex in under another child wj through the nearest marked vertex as determined by C’(v)
Coffee Shop (APIO Shortlist 2007)
Observation
Hence, we can calculate the following values:
U’(w) = 0 if U(w)+1+C’(v) ≤ K
Otherwise, U’(w) = U(w)
Coffee Shop (APIO Shortlist 2007)
Observation
We only need to mark vertex v if for some child w, U’(w) = K - 1. If not, the unserved vertex below w would be K distance from v with no marked vertex
Otherwise, we will not mark, this can be shown to be optimal
Coffee Shop (APIO Shortlist 2007)
Observation
If we mark vertex v, then
C(v) = 0, U(v) = -∞
If not, then
C(v) = C’(v), U(v) = 1 + maxw child of vU’(w)
Coffee Shop (APIO Shortlist 2007)
Solution
Finally at the root, we will mark it if there are still any unserved vertices, or if the root itself is unserved.
Run the DP as a DFS from the root node.
Since at each point, we only need to check the children to determine the values, O(N).
Distribution DP
Key Idea
Distribution DP
To distribute x things over the subtree with root u:
dp(u, x) = auxu(children[u].size(), x)
where v ∊ [0, children[u].size()) in an arbitrary order (child index)
auxu(v, x) = minx’ {
auxu(v - 1, x - x’) + dp(children[u][v], x’)
} for x’ ≤ x
State: O(N2), Transition: O(N).
Distribution DP
Limit to sane values only!
Let w(u) = size of subtree rooted at u (vertex)
auxu(v, x) = minx’ auxu(v - 1, x - x’) + dp(children[u][v], x’)
for x’ ≤ w(children[u][v]),
x - x’ ≤ w(children[u][1]) + w(children[u][2]) + … + w(children[u][v - 1])
Distribution DP
Now each number of nodes x will only be compared to the other side of the tree x - x’ once. The number of comparisons amortizes to the number of pairs of nodes.
Summing on all nodes, we get a complexity of O(N2).
Distribution DP
We claim the sum of steps for calculating dp(u, -) (and all subtrees of u) with subtree at u having size S to be S2. This is true for the smallest case of 1 node only. Then induct upwards.
Then for some node, the number of steps is 1×a + (a+1)×b + (a+b+1)×c + a2 + b2 + c2 + 1 = (a+b+c+1)2 (red is steps from children)
a
b
c
Distribution DP
Rainbow Fish (Mock APIO 2015)
You have a tree with N ≤ 1000 nodes.
Each node is coloured black or white (given).
Answer Q ≤ N(N-1)/2 of these queries:
Does there exist a size X subgraph with exactly Y black nodes? → Yes/No
Rainbow Fish (Mock APIO 2015)
Instant DP
dp[i][x][y]:
Can I form a subgraph with X nodes and Y black nodes in the subtree of node i?
??? O(N4) TLE
Rainbow Fish (Mock APIO 2015)
Observation
If I can form a subgraph of size X with Y1 or Y2 black nodes, where Y1 < Y2:
Then I can form a subgraph with size X with K black nodes, where Y1 ≤ K ≤ Y2.
Rainbow Fish (Mock APIO 2015)
Observation
Consider I have a subgraph of size X with Y1 black nodes.
We can shift the subgraph along the tree.
Each time, we will add a node and remove another node to the subgraph.
(Maintain the size as X)
Rainbow Fish (Mock APIO 2015)
Observation
It must be possible to shift from the subgraph containing Y1 black nodes to the subgraph containing Y2 black nodes by a series of shifts along the tree.
In the process, we would have gained black nodes incrementally, from Y1 to Y2.
Rainbow Fish (Mock APIO 2015)
State Reduction
Instead of storing dp[i][x][y] = True/False,
We can have dp_min[i][x] = Ymin and dp_max[i][x] = Ymax, the lowest and largest number of black nodes we can have in the subtree of i with size x.
Rainbow Fish (Mock APIO 2015)
Approach
Distribution DP on Tree!
Distribute the size of the subgraph over all the childrens, keep the min and max number of black nodes for each size of subgraph!
DP on Trees
Key Idea
Breaking Good (Codeforces 507E)
You are given an undirected, unweighted graph of N ≤ 106 nodes and M ≤ 106 edges. Your goal is to move from vertex 1 to vertex N by a shortest path.
(To be continued…)
Breaking Good (Codeforces 507E)
However, some of the edges are marked. After selecting a path, you have to mark all the unmarked edges in your path and unmark all the marked edges not in your path.
Each of these marking/unmarking counts as one move. Find a shortest path that results in the minimum number of moves required.
Breaking Good (Codeforces 507E)
Observation
Let d be the length of the shortest path and y be the total number of marked edges.
If there are x marked edges along some shortest path, the total number of moves required is (d-x)+(y-x)=d+y-2*x
Breaking Good (Codeforces 507E)
Observation
Since the number of moves is d+y-2*x, and d+y is constant regardless of which path we choose, to minimise the number of moves we just have to maximise x!
Breaking Good (Codeforces 507E)
Instant DP!
dp(u) = maxv dp(v) + 1
for each edge (u, v)
Breaking Good (Codeforces 507E)
DP?
Isn’t this a undirected graph?
The dependencies are cyclical?
Basics
DP is formulaic
Basics
DP is creative
DP on DAGs
Because trees are not enough.
Breaking Good (Codeforces 507E)
DP!
You must take the shortest path possible, you can only take edges from nodes of distance d from 1 to nodes of distance d+1 from 1
Construct shortest-path DAG!
Breaking Good (Codeforces 507E)
DP!
Since graph is unweighted, BFS visits the shortest-path DAG.
You can use BFS to traverse the DP DAG.
Breaking Good (Codeforces 507E)
BFS
dp(all) = -∞
dp(1) = 0
Run BFS from 1.
Relax v from u:
Breaking Good (Codeforces 507E)
BFS
We must make sure not to relax to an already visited vertex, since that edge is not part of shortest-path DAG.
Answer is simply dp(N)
O(N + M).
Topological Order
DP
DP - DAG duality
If you have a DP problem, it can be transformed into a DAG and vice versa.
Subset DP
Subset DP
Key Idea
DNALAB (SPOJ)
There are N ≤ 15 strings, each of length up to 100. Find the shortest string that contains all the strings as substrings (not subsequences).
If there is more than one such string, find the lexicographically smallest of them.
DNALAB (SPOJ)
Observation
If a string is a substring of another string, it can be ignored.
DNALAB (SPOJ)
Observation
N ≤ 15.
An exponential algorithm will run in time!
DNALAB (SPOJ)
Observation
If I have two strings ab and bc, I can combine the common suffix and prefix to form abc.
DNALAB (SPOJ)
Graph modelling
Find all unique strings that are not substrings of another string. Add an edge between each pair of strings, weighted with the negated length of the common prefix/suffix. The problem reduces to finding the shortest Hamiltonian path.
DNALAB (SPOJ)
Hamiltonian Path DP
The goal is to visit all nodes.
Only the subset of the nodes already visited and the last node in the current path matter.
DNALAB (SPOJ)
Hamiltonian Path DP
dp(subset, i) = minimum of
dp(subset without i, j) + cost(j, i)
where j ≠ i is in the subset
DNALAB (SPOJ)
Hamiltonian Path DP
Bitmasks are great for representing subsets.
dp(mask, i) = minimum of
dp(mask ^ (1 << i), j) + cost(j, i)
where (1 << j) & (mask ^ (1 << i)) ≠ 0
O(2N·N2).
Traveling Salesman
N cities, one-way roads between them. Find a way to visit all the cities, starting at city 1, ending at city N, without visiting any city more than once.
Traveling Salesman
Bitset DP
dp(x, bitset) → minimum time needed to visit all the cities in bitset, ending at city x. Bitset can be represented as a 32-bit integer for small enough N, with the i-th bit being 1 if the city i is in the bitset
dp(x, bitset) = min(dp(y, bitset - y) + cost(y, x), for all y in bitset)
State: O(2N-3 x N)
Transition: O(N)
Problem
Given a set of integers S that sums to 0. What is the largest number of non-empty partitions that S can be divided into, such that every partition sums to 0?
|S| < 20
(goingdutch)
Solution
Instant DP
By precomputation, we can tell in O(2N) time which subsets of S sum to 0 and are hence ‘valid’
dp(s) = 1 + max(dp(s - c) , for all c that’s a valid subset of s)
State: O(2N) . Transition: O(2N)
Overall: O(22N)
Total transitions = NC0 × 20 + NC1 × 21 + NC2 × 22 + ... = (1+2)N
Solution
Answer a more general question:
If S is a set of integers, which may not sum to 0. Consider valid partitioning of S. Find the partitioning that gives the maximum number partitions that sum to 0.
dp(s) = max(dp(s - x) for all integers x in s) + (1 if s sums to 0, 0 otherwise)
Think about it this way: we are ordering the set, and counting the number of times the prefix sum was 0.
O(N2N)
Problem
There are N < 20 potatoes. You want to choose a subset of them to bring with you on your trip. The potatoes are all very unique and have different personalities which may clash with each other. A potato expert inspect the potatoes, and tells you the interaction score for every subset of the N potatoes, i.e. you’re given A[s], which maps each subset s to the interaction score A[s]
However, you notice a glaring mistake in the potato expert’s methodology. The correct interaction score F[s] should be the sum of all A[c] where c is a subset of s. Compute F[s] for all subsets s
Solution
Naive computation:�O(2N) × O(2N)
How can we DP without double counting?
Solution
Compute instead:
G(s, x) being the sum of all A[c] with c being a subset of s, such that:
Then we have:
F[s] = G(c, -1)
Solution
Computing G(c, x) requires just a few cases
Base case: G(c, N) = A[c]
If x+1 is in c:
G(c, x) = G(c, x+1) + G(c \ {x+1}, x+1)
Else:
G(c, x) = G(c, x+1)
Time: O(N2N) !
Twenty Questions (ICPC Regionals)
There are N ≤ 128 different objects and M ≤ 11 properties. Each object contains a different subset of these properties and you know which properties each object has.
(To be continued…)
Twenty Questions (ICPC Regionals)
One of the N objects is chosen without your knowledge. You can ask questions one by one about whether the object contains a specific property. You can choose what questions to ask based on the answers to previous questions.
What is the minimum number of questions you need to uniquely identify the object?
Twenty Questions (ICPC Regionals)
Guess?
Check all possible subset of questions to ask and find the one such that the answer is unique for every single object.
Does this work?
Twenty Questions (ICPC Regionals)
Wrong Guess
{000,001,100,110}
For any 2 properties, there exist at least 2 objects such that the answer is the same
Does that mean we have to ask 3 questions?
Twenty Questions (ICPC Regionals)
Wrong Guess
{000,001,100,110}
NO! We can ask about the 1st property first
If it is 0, we ask about the 3rd property, otherwise we ask about the 2nd property
We can always uniquely identify the object in 2 questions
Twenty Questions (ICPC Regionals)
Observation
We need to keep track of currently what is the subset of possible objects that we need to distinguish between
But there are 2N possible subsets!
Twenty Questions (ICPC Regionals)
Observation
We only need to know what questions have been asked and what are the answers to those questions.
That is 3M ≈ 180k possibilities.
Twenty Questions (ICPC Regionals)
Subset DP
Let dp(m, n) be the minimum number of questions we need to find out the object given the subset of questions we have asked m, and the answers to those questions n
Twenty Questions (ICPC Regionals)
Subset DP
dp(m, n) = 0 if there is at most 1 object with such a property
dp(m, n) = mini(max(dp(m^(1<<i), n),dp(m^(1<<i), n^(1<<i)))+1
Across all questions i that have not been asked
Coding note: To store the state efficiently, use a single number written in base 3. Let the digits 0 stand for “unasked”, 1 stand for “answered yes” and 2 stand for “answered no”.
Twenty Questions (ICPC Regionals)
Time Complexity
Number of states is O(3M) as we only need to care about answers to questions we have asked
Precomputation: O(N3M) (figure out what objects you have for each set of answered questions)
Transition: O(M)
Overall: O((M+N)3M)
Subset DP
Key Idea
Profile DP
Profile DP
Key Idea
Four Blocks (SRM 444)
There is an N·M grid some of which already have been filled with 1x1 squares. Fill the remaining grid with 1x1 and 2x2 squares to maximise score. Score is the sum of area2 of all the squares in the grid.
Constraints: 1 ≤ N ≤ 100, 1 ≤ M ≤ 8
Four Blocks (SRM 444)
Observation
To fill the current row, we only need to know the positions of the “half-filled” 2x2 squares from the previous row
We can freely fill the remaining squares
Four Blocks (SRM 444)
Profile DP
Let dp(r,m) be the maximum score attainable by filling r rows and the last row be encoded by a mask m which is 1 for each “half-filled” 2x2 square and 0 otherwise
Four Blocks (SRM 444)
Profile DP
The length of consecutive 1’s in m must be of even length and we only need to check dp(r-1,m2) for some combinations of m2
Total time: O(N22M) ≈ 25 million but actually much less because many combinations are invalid
Floor Boards (SRM 383)
There is an N·M grid where some of the grid square are covered. You need the cover the rest using a minimum number of 1 by K planks (K is up to you). Each square should be covered at most once. Planks can be rotated and you have infinite number of every size.
Constraints: 1 ≤ N ≤ 10, 1 ≤ M ≤ 10
Floor Boards (SRM 383)
Observation
Each square will either be covered by a horizontal floor board or vertical floor board
All 2RC possible settings of horizontal/vertical for each grid square form a possible covering :O
Floor Boards (SRM 383)
Profile DP
Let dp(r,m) be the minimum number of planks needed to cover the first r rows and the last row be encoded by a mask m which decides whether each square in row r is covered by a horizontal or vertical plank
Floor Boards (SRM 383)
Profile DP
For each dp(r-1,m2), the corresponding value is dp(r-1,m2) + (number of consecutive horizontals in m) + (number of verticals in m whose corresponding value in m2 is horizontal)
R-1: HHVVH (1 vertical interrupted)
R : VHHVH (consecutive H: 2)
Floor Boards (SRM 383)
Profile DP
We try all possible value of m2 and take the minimum across all values
Total time: O(N22M) ≈ 107
Painting Squares (SRM 532)
There is an N·M grid. Find the number of ways to colour some of the squares such that every coloured square is adjacent to an even number of coloured squares.
Constraints: 1 ≤ N ≤ 25, 1 ≤ M ≤ 10
Painting Squares (SRM 532)
Observation
If we know the colouring of the first N-1 rows, we can try all 2M possibilities for the last row
We need to know which squares are coloured in the previous row, and what the parity of the number of neighbours each coloured square was
Painting Squares (SRM 532)
Profile DP
Store the state of the previous row as a ternary number
Painting Squares (SRM 532)
Profile DP
dp(r, m) gives number of ways to colour r by M grid given that last row is encoded as mask m as described previously
Total time: O(N32M) ≈ 4 billion...TLE
Painting Squares (SRM 532)
Observation
We don’t need to check all pairs of 3M bitmasks
Given a last row of mask m, what are the possible masks of the second last row?
Painting Squares (SRM 532)
Prune
For each non-coloured square in the last row, second last row square in same column must have configuration 0 or 1
Painting Squares (SRM 532)
Prune
For each coloured square in the last row, given the configuration we know whether the square in the same column in the second last row must be coloured
If 2nd last row is colored, it must be a 1, if it is not then it is 0
Painting Squares (SRM 532)
Prune
Hence, for each dp(r,m) we only need to check dp(r - 1, m2) for f(m) possible values of m2 where f(m) is 2number of 0’s in ternary representation of m
Painting Squares (SRM 532)
Time Complexity
It can be shown that the sum of f(m) across all 0 ≤ m < 3M is 22M which means there are only 4M valid pairs of masks to check
(There are 4 possibilities for each column for a valid pair of masks.)
Total time: O(N4M) ≈ 6.5 million
Profile DP
Key Idea
Four Blocks _ex?
There is an N·M grid some of which already have been filled with 1x1 squares. Fill the remaining grid with 1x1 and 2x2 squares to maximise score. Score is the sum of area2 of all the squares in the grid.
Constraints: 1 ≤ N ≤ 100, 1 ≤ M ≤ 16
Four Blocks _ex?
Observation
To fill the current cell (x, y), we only need to know the positions of the “half-filled” 2x2 squares from the previous row from (x-1, y) to (x-1, M) and current row from (x, 0) to (x, y-1).
Broken Profile
Approach
We can fill it cell by cell and break our state up!
Transition: O(1)
Broken Profile (Left is state, right is tiling shape)
| | 1 | 1 | 1 |
1 | 0 | | | |
| | | | |
| | | | |
| | | | |
| | 1 | 1 | 1 |
1 | 0 | | | |
| | | | |
| | | | |
| | | | |
Broken Profile
Green is new state
| | | | |
| | | 0 | 0 |
0 | 1 | 1 | | |
| | | | |
| | | | |
| | | | |
| 0 | 0 | 0 | 0 |
0 | | | | |
| | | | |
| | | | |
| | | | |
| | 1 | 0 | 0 |
0 | 1 | | | |
| | | | |
| | | | |
Broken Profile
Key Idea
Young Tableau DP
Twofive (IOI ‘01)
A 25-letter word containing all letters A-Y is valid if the letters are increasing in all rows and columns when arranged in a 5·5 grid.
The word is written out row by row. Find the kth-lexicographical word and also the lexicographical index of a word.
Twofive (IOI ‘01)
ADJPTBEKQUCGLRVFINSWHMOXY is valid:
A | D | J | P | T |
B | E | K | Q | U |
C | G | L | R | V |
F | I | N | S | W |
H | M | O | X | Y |
Twofive (IOI ‘01)
Lexicographical DP!
We just need to count the number of such words with a given prefix. But how?
Twofive (IOI ‘01)
Prefix
A | D | J | P | T |
B | E | K | ? | ? |
? | ? | ? | ? | ? |
? | ? | ? | ? | ? |
? | ? | ? | ? | ? |
Twofive (IOI ‘01)
Candidate positions for next letter
A | D | J | P | T |
B | E | K | ? | ? |
C | ? | ? | ? | ? |
? | ? | ? | ? | ? |
? | ? | ? | ? | ? |
Twofive (IOI ‘01)
Select one position
A | D | J | P | T |
B | E | K | ? | ? |
C | ? | ? | ? | ? |
? | ? | ? | ? | ? |
? | ? | ? | ? | ? |
Twofive (IOI ‘01)
Some positions are fixed
A | D | J | P | T |
B | E | K | ? | ? |
C | ? | ? | ? | ? |
? | ? | ? | ? | ? |
? | ? | ? | ? | ? |
Twofive (IOI ‘01)
Candidate positions for next letter
A | D | J | P | T |
B | E | K | ? | ? |
C | F | ? | ? | ? |
F | ? | ? | ? | ? |
? | ? | ? | ? | ? |
Twofive (IOI ‘01)
The DP state forms a Young tableau.
Twofive (IOI ‘01)
Young Tableau DP
If we fix a particular prefix of the string, we can take that into account in the DP by building the tableau up letter by letter and handling the fixed letters separately.
Twofive (IOI ‘01)
Young Tableau DP
dp(tableau, letter) =
dp(tableau + letter at fixed position)
if letter is fixed.
dp(tableau + letter at all good positions)
otherwise.
Twofive (IOI ‘01)
Young Tableau DP
There is no need to store the entire tableau in the DP state, only the row lengths. The letters are added in a fixed order.
Amount of time to do the DP for one prefix: O(25·(5+1)5)
Number of prefixes to check: O(252)
Total time: O(253·(5+1)5)
Young Tableau DP
Key Idea
2005 AMAZING SLIDES
2012 AMAZING SLIDES
2014 AMAZING SLIDES
2015 AMAZING SLIDES
2016 AMAZING SLIDES
2017 AMAZING SLIDES
2018 AMAZING SLIDES
2019 AMAZING SLIDES
2020 AMAZING SLIDES
2021 AMAZING SLIDES
MERE THIEVES
Koh Zi Chun
Shen Chuanqi
Chin Zhan Xiong
Raymond Kang Seng Ing
Wu Xinyu
Hubert Teo Hua Kian
Gan Wei Liang
Ranald Lam Yun Shao
Lim Li
Feng Jiahai
Zhang Guangxuan
Huang Xing Chen
Clarence Chew Xuan Da
Jeffrey Lee Chun Hean
Teow Hua Jun