Tags: competitive-programming
This article was translated from my Japanese blog.
2709 Dark Room
Since only dark rooms matter, we can represent the visited dark rooms with a bitmask and find the shortest operation sequence by dynamic programming. - dp[i][S] = the minimum length of an operation sequence that reaches state S using at most the first i instructions.
Let S’ be a state that can reach S with operation k(1<=k<=K). Then we get the recurrence: - dp[i+1][S] = dp[i][S’] + 1 for all S’
Also, dp[i][S] <= dp[j][S] (i < j) holds for every state S. Finally, it is sufficient to compute the transition from each state once and the total runtime complexity is O(KM2^M).
Actually, a BFS is easier and smarter than this dynamic programming approach :cry:
1194 Vampire
Since the given integers are less than or equal to 20, we can consider the intervals [i,i+1] for each i (-r<=i<=r). Move the sun (circle) forward along the y-axis while keeping the maximum building height in each interval. Finally, use the Pythagorean theorem to get the y-coordinate of the sun.
2170 Marked Ancestor
First, we arrange the vertices as a one-dimensional sequence A of length 2*N using an Euler tour (in the sample from the problem statement, A = {1, 2, 2, 4, 4, 2, 3, 3, 5, 5, 5, 6, 6, 6, 3, 1}). This method is called the Euler tour technique. Let’s define some variables:
- id1[u] = the first index where node u appeared in sequence A,
- id2[u] = the last index where node u appeared in sequence A,
- depth[u] = the depth of the node u on the tree,
- B[u] = among the marked ancestors of node u, the node with the largest depth (initially all B elements are 1)
Then each operation is translated as follows:
- M v: For each u in the subtree of v, update B[u] with v if depth[u] < depth[v]
- Q v: Add B[id1[v]] to your answer
These operations can be done in O(log N) using a segment tree with lazy propagation. Since DFS only takes O(N), the total complexity is O((Q + N) log N). However, the above solution is a little bit heavy to implement. If you read the queries first and precompute the operations, you can solve it backward with Union Find.
1347 Shopping
Just DP in O(N^2) as follows.
- dp[i] = minimum distance when going all the way from store 1 to store i
2176 For the Peace
Problem (the original statement is a little difficult to understand):
Consider the following operation, where A[i] = ci, 1 + ... + ci, mi:
- For given i, subtract ci, j from A[i] (j is a constant satisfying 1 <= j <= mi)
Can all A[i] be set to 0 by repeating this operation while keeping the condition max(A[i]) − min(A[i]) ≤ D?
The operation can be divided into four cases:
- Op1. Only max(A[i]) and min(A[i]) decrease
- Op2. Only max(A[i]) decreases
- Op3. Only min(A[i]) decreases
- Op4. Neither max(A[i]) nor min(A[i]) decreases
In fact, when multiple operations are possible, their order does not matter. For example, suppose both Op1 and Op2 are possible in some state A. Let A’’ be the state after applying Op1 to A, and let A’’’ be the state after applying Op2 to A; then it is easy to see that max(A’‘) == max(A’’’). That means whichever operation is applied first, the process can still transition to the same state. In other words, to reduce all A[i] to zero, you only need to perform one of the operations that are possible in each state.
Conversely, if there are no possible operations in a state, it is impossible to set all A[i] to zero. Finding possible operations can be done in O(n log n) using a BST (I used std::set). The total runtime complexity is O(M * n log n) (M = ∑imi). In my implementation, I processed the operations in reverse (adding instead of subtracting).
Looking at the official solution, there seem to be smarter ways to find possible operations.
2298 Starting Line
Consider moving one meter at a time. It is clear that if acceleration is possible at a point, it is better to accelerate, so we can simulate the process in O(L) with a greedy strategy. Is the constraint a trick, or is there another way to solve it?
2723 Surface Area of Cubes
Just add and subtract the surface area while removing cubes. Subtract from the answer when adjacent blocks are removed. Be careful about the boundaries. The complexity is O(N^2).
2534 Dictionary
Build a directed graph from the alphabet order implied by the given input. For example, create an edge k’ → k if k < k’ for a pair of characters k and k’. If the graph has no cycle, the words can be in lexicographic order. We can detect cycles with DFS.
2320 Infinity Maze
Since the number of states is at most 4 * H * W, any walk longer than 4 * H * W steps contains a loop. So we only have to simulate O(HW) steps.
2182 Eleven Lover
Digit DP:
- dp[i][j] = the number of k such that S[k] … S[i] mod 11 is equal to j,
Be careful not to count numbers with leading zeros.
2157 Dial Lock
First, note that only the difference between the initial state and the target state matters. Then the task becomes finding the minimum number of operations for a sequence A[i] of length k consisting of numbers between 0 and 9, adding t (-9<=t<=9) to the consecutive intervals to obtain 0 mod 10. If we try to implement this in a straightforward way, the number of states is O(10^k), which is too large. Let A[l] (1 <= l <= k) be the leftmost non-zero element. Any sequence of operations whose interval starts at A[l] can be divided into
- set A[l] to 0
- an operation sequence for (A[l+1] … A[n])
For example, the operations: - adding a to [l,r] and adding b to [l, r’] (l <= r < r’ <= k)
correspond to
- adding a + b to [l, r] and adding b to [r + 1, r’]
We can also replace an operation that adds t (-9<=t<=-1) to an interval with an operation that adds 10 + t. Therefore, it is sufficient to find the minimum number of operations by repeatedly using only operations that make the leftmost non-zero element become 0. Since there are O(k - l) operations to set A[l] to 0 and each operation takes O(k), the total runtime complexity is O(k! * k).
The above solution is almost the same as the official solution.
Eventually, I realized that only the differences matter. At first, I tried meet-in-the-middle over the states, but the number of states was still O(10^k), so it was not useful.