Statistics
| Problem | #Submission | #Passed Pretest | #Passed Finaltest | Average Score |
| A | 858 | 767 | 660 | 433.36 |
| B | 749 | 655 | 600 | 813.28 |
| C | 467 | 352 | 229 | 1093.07 |
| D | 28 | 14 | 4 | 1315.00 |
| E | 2 | 2 | 1 | 1620.00 |
Brute force simulation works in this problem. In Ciel's turn, if she has at least 2 100-yen coins and at least 2 10-yen coins, pay those coins. Otherwise, if she has at least 1 100-yen coins and at least 12 10-yen coins, pay those coins. Otherwise, if she has at least 22 10-yen coins, pay those coins. Otherwise, she loses. In Hanako's turn, do similar simulation in reverse order. The complexity of this solution is O(x + y).
B. Colorful Field (writer: ir5)
A solution that uses an array of N × M will absolutely get (Time|Memory)LimitExceeded, so we cannot simulate it naively.
Both the number of queries and the number of waste cells K are not more than 1,000, so it is enough to answer each queries in O(K) runtime.
Let (a, b) be a query cell. Whether (a, b) is waste or not is determined by simple iteration.
So let's consider about the case (a, b) is not waste. Let I be the number of cells including waste ones that will be sweeped before (a, b), and J be the number of waste cells that will be sweeped before (a, b). Then, the answer is classified by the value of (I - J) mod 3 (for example, if the value = 0, the answer = "Carrots", and so on).
By simple calculation, I = (a - 1)M + (b - 1), and J is calculated by O(K) iteration.
Overall, this problem can be solved in O(KT) runtime, where T is the number of queries.
We can regard a substring that is equal to one of boring strings as an interval. The number of such intervals are at most |s|· n, and the required time to determine whether each of them is a boring string is |bi|, so all intervals can be calculated in O(|s|· n· |bi|) runtime, by naive way. (Yes, no special string algorithm is required here.)
The original problem can be rewritten as follows: you are given at most 106 intervals on [0, 105], determine the longest interval that does not contain any given interval.
To solve this rewritten problem, define right[i] be the leftest position of an interval whose left-endpoint is equal to i. If there is no interval whose left-endpoint is i, define right[i] is ∞.
Now we will calculate the optimal interval whose left-endpoint is i, in the order of i = |s|, |s| - 1, |s| - 2, ... 0. When i = |s|, corresponding right-endpoint is only |s|. Let's think the case when corresponding right-endpoint to i + 1 is j. If right[i] > j, then corresponding right-point to i remains j. Otherwise, that right-point is updated to right[i] - 1.
This iteration will be done in O(|s|).
Overall, O(|s|· n· |bi|) runtime.
D. Password (writer: rng_58)
Define an array b0, b1, ..., bn as follows: If the states of i-th panel and (i + 1)-th panel are same, bi = 0. If the states of i-th panel and (i + 1)-th panel are different, bi = 1. (The states of 0-th panel and (n + 1)-th panel are considered to be OFF.) If Ciel flips panels between x-th and (x + a - 1)-th, inclusive, the values of bx and bx + a are changed and other elements of b aren't changed. We can rewrite the problem:
<Problem D'>
You are given an 0-1 array b0, b1, ..., bn. At most 20 (=2k) of them are 1. In each move, you can change the values of bx and bx + a, where a is an element of the given array and 0 ≤ x ≤ n - a. Determine the minimal number of moves required to change all elements in b to 0.
The order of moves is not important. If there is an index x s.t. bx = 1, you must change bx at least once, so you can assume that the next move is performed on x. Assume that when you change the values of bx and bx + a, at least one of them is 1.
<Problem D''>
Let V be the graph with (n + 1) vertices. Vertices are numbered 0 to n. There is an edge between vertex v1 and vertex v2 if and only if |v1 - v2| is an element of array a. Initially at most 20 vertices contain tokens. In each move, you can move a token along an edge. When two tokens meet, they disappear. Determine the minimal number of moves required to erase all tokens.
First, calculate the distances between all pair of tokens by doing bfs 2k times. Next, do DP with bitmasks: Let dp[S] (where S is a set of tokens) be the minimal number of moves required to erase all tokens. If S is empty, dp[S] = 0. If S = {s0, s1, ..., sm - 1} is nonempty, dp[S] = min{dp[S\{s0, si}] + dist(s0, si)} where 1 ≤ i ≤ m - 1.
The complexity of this solution is O(knl + k· 22k).
E. Security System (writer: ir5)
Lemma. The sensors we should consider are only four sensors at the corner.
proof: Let's think about sensors at a fixed row v. As the definition, when Ciel entered to (x, y), a sensor at (u, v) decreases its count by |x - u| + |y - v|. Let this value be fx, y(u). If we fix Ciel's path, the total decrease of each sensor is expressed as the summation of fx, y(u), where x, y is one of the path. Because fx, y(u) is a convex function about variable u and the fact that "the summation of convex functions is also a convex function", we can ignore sensors at center points: i.e. a < u < a + c - 1.
The same thing holds true for vertical direction, so it is enough to consider only four sensors at corner: (a, b), (a + c - 1, b), (a, b + c - 1), (a + c - 1, b + c - 1). ■
Because we need the lexicographically first solution, we want to use 'R' rather than 'U' in each step. Thus, it is enough if we can determine whether a feasible path exists with constraints that Ciel is at (x, y) and the rest counts of four corners are T1, T2, T3, T4.
Lemma. Optimal step is following (except sensors region):
proof: A following figure shows that if a blue path is good a brown path is also good. (Here, the blue path means arbitrary one, and the brown path means optimal one.) ■
The problem is sensors region. In sensors region, it is possible to assume that the optimal path always passes a right-top sensor.
While Ciel moves in sensors region to right-top sensor, the total decrease of both left-bottom and right-top sensor is constant. So we should think about only two sensors: left-top and right-bottom.
In addition, let the total decrease of left-top and right-bottom be D1 and D2. Then following holds: D1 + D2 = const.
The smallest value for D1 is the total decrease when Ciel moves upward then moves rightward, and the smallest value for D2 is in the same way (moves rightward → upward).
So we can calculate the minimal value and the maximal value of D1. And actually, D1 can be an arbitrary value between them with interval of 2. A following picture shows it.
Complexity at a simulation part is O(1). Overall, the complexity is O(N).
proof: Let's think about sensors at a fixed row v. As the definition, when Ciel entered to (x, y), a sensor at (u, v) decreases its count by |x - u| + |y - v|. Let this value be fx, y(u). If we fix Ciel's path, the total decrease of each sensor is expressed as the summation of fx, y(u), where x, y is one of the path. Because fx, y(u) is a convex function about variable u and the fact that "the summation of convex functions is also a convex function", we can ignore sensors at center points: i.e. a < u < a + c - 1.
The same thing holds true for vertical direction, so it is enough to consider only four sensors at corner: (a, b), (a + c - 1, b), (a, b + c - 1), (a + c - 1, b + c - 1). ■
Because we need the lexicographically first solution, we want to use 'R' rather than 'U' in each step. Thus, it is enough if we can determine whether a feasible path exists with constraints that Ciel is at (x, y) and the rest counts of four corners are T1, T2, T3, T4.
Lemma. Optimal step is following (except sensors region):
proof: A following figure shows that if a blue path is good a brown path is also good. (Here, the blue path means arbitrary one, and the brown path means optimal one.) ■
The problem is sensors region. In sensors region, it is possible to assume that the optimal path always passes a right-top sensor.
While Ciel moves in sensors region to right-top sensor, the total decrease of both left-bottom and right-top sensor is constant. So we should think about only two sensors: left-top and right-bottom.
In addition, let the total decrease of left-top and right-bottom be D1 and D2. Then following holds: D1 + D2 = const.
The smallest value for D1 is the total decrease when Ciel moves upward then moves rightward, and the smallest value for D2 is in the same way (moves rightward → upward).
So we can calculate the minimal value and the maximal value of D1. And actually, D1 can be an arbitrary value between them with interval of 2. A following picture shows it.
Complexity at a simulation part is O(1). Overall, the complexity is O(N).
For problem B, Colorful Field you can also use a binary search to answer queries if you sort the waste patches at the beginning. It speeds it up to O(log(k)*T).
it is O( (T + K) log K ) sorting is O(K log K)
for problem B there also exists a solution with time complexity O( (K+T) log K ). we can sort the waste cells and for each query using lower_bound is O(log K).