This article was translated from my Japanese blog.
2709 Dark Room
Since only dark rooms matter, let’s consider finding the minimum value of the operation sequence with dynamic programming, representing the dark rooms we’ve visited with the bit sequences. - dp[i][S] = minimum length of the operation sequence by which we can reach a state S for i or less instructions.
Let S’ be a state that can be reached to with the operation k(1<=k<=K) from the state S, then we can obtain a recurrence: - dp[i+1][S] = dp[i][S’] + 1 for all S’
Also, dp[i][S] <= dp[j][S](i < j) holds for all state S. Finally, it is sufficient to compute the transition from each state once and the total runtime complexity is O(KM2^M).
Actually, you can just do the BFS instead of dynamic programming and it is easier and smarter :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). Just move the sun (circle) forward on the y-axis, keeping the maximum height of the building in each interval. Finally, you can use the hypot theorem to get the y-coordinate of the sun.
2170 Marked Ancestor
First, we reorder the vertices in in-order to reduce them to 2*N one-dimensional sequence A (in the example in the problem, A = {1, 2, 2, 4, 4, 2, 3, 3, 5, 5, 5, 6, 6, 6, 3, 1} ) (this method is called 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 column A,
- depth[u] = the depth of the node u on the tree,
- B[u] = Among the marked ancestors of node u, the number of nodes which has the largest depth (initially all the B elements are 1)
Then each operation corresponds to them:
- M v: For B[u] (id1[v]<= ∀u <=id2[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, you can solve it with Union Find in backward.
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 is a little difficult to understand) :
Let’s consider the next 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 the operation, keeping the conditoin 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 there are multiple possible operations, the order in which they are performed doesn’t matter. For example, in the state A[i], where the operations by Op1 and Op2 are possible, let A’‘[i] be the state after Op1 performed in A[i] and A’’‘[i] be the state after Op2 performed in A[i], then it is easy to see that max(A’‘[i]) == max(A’’’[i]). That means whichever operation you do first, you can transition to the same state. In other words, to get 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 by O(n log n) using BST(I just used std::set). The total runtime complexity is O(M * n log n) (M = ∑imi). In fact, we implemented the above operation in reverse (i.e., adding instead of subtracting).
Looking at the official solution, there seem to be smarter and better ways to find possible operations.
2298 Starting Line
Let’s consider moving by one meter at a time. It is clear that if acceleration is possible at each point, then it is better to accelerate, so we can simulate in O(L) with greedy strategy. Is the constraint a trick or there is another way to solve it?
2723 Surface Area of Cubes
Just add and subtract the surface area while removing cubes. Subtract from the answer if any adjacent blocks are excluded. Be careful about the boundaries. The complexity is O(N^2).
2534 Dictionary
Make directed graphs in the order of alphabets that can be determined from a given input. For example, create an edge k’ → k, if k < k’ for each character k and k’. If the graph has no cycle, we can say they are in lexicographic order. We can detect any cycle by DFS.
2320 Infinity Maze
Since the number of states is at most 4 * H * W, any move which took more than 4 * H * W includes a loop. So, we only have to simulate in O(HW).
2182 Eleven Lover
Digit DP:
- dp[i][j] = the total number of k such that S[k]…. S[i] mod 11 is equal to j ,
Be careful not to count the leading-zero digit numbers.
2157 Dial Lock
First, we can see that the difference between the initial state and the target state only matters. Then we see that we have to find 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) and we cannot find them in time. So let A[i] be Al, then any sequence of operations with A[l] which is the leftmost end of the interval 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 see that the operation of adding t (-9<=t<=-1) to the interval is replaced by adding 10 + t. Therefore, it is sufficient to find the minimum number of operations , repeating only the operation that makes the leftmost end of the array 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 the differences don’t matter. At first, I thought of enumerating half of the states, but the number of states is not less than O(10^k), so it was useless.