### ir5's blog

By ir5, 9 years ago, , 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

## A. Bus Game(writer:  rng_58 )

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.

## C. Beaver (writer:  ir5)

We can regard a substring that is equal to one of boring strings as an interval.  The number of such intervals are at most |sn, and the required time to determine whether each of them is a boring string is |b i|, so all intervals can be calculated in O(|sn· |b i|) 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(|sn· |b i|) runtime.

Define an array b 0, b 1, ..., b n as follows: If the states of i-th panel and (i + 1)-th panel are same, b i = 0. If the states of i-th panel and (i + 1)-th panel are different, b i = 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 b x and b x + 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 b 0, b 1, ..., b n. At most 20 (=2k) of them are 1. In each move, you can change the values of b x and b x + 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. b x = 1, you must change b x at least once, so you can assume that the next move is performed on x. Assume that when you change the values of b x and b x + 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 v 1 and vertex v 2 if and only if |v 1 - v 2| 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 = {s 0, s 1, ..., s m - 1} is nonempty, dp[S] = min{dp[S\{s 0, s i}] + dist(s 0, s i)} 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 f x, y(u). If we fix Ciel's path, the total decrease of each sensor is expressed as the summation of f x, y(u), where x, y is one of the path. Because f x, 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 T 1, T 2, T 3, T 4.

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 D 1 and D 2. Then following holds:
D 1 + D 2 = const.

The smallest value for D 1 is the total decrease when Ciel moves upward then moves rightward, and the smallest value for D 2 is in the same way (moves rightward  →  upward).
So we can calculate the minimal value and the maximal value of D 1. And actually, D 1 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). Tutorial of Codeforces Beta Round #71  Comments (14)
 Problem D is really nice!But it's too difficult for me, at least now... Each of the three steps to solve the problem is worth learning~
•  Surprisingly or not, he first suggested that problem for C problem, not D.
•  Surprisingly =)))
 Thanks for editorial! And at most for solution of problem D!
 Now I got AC on Problem E!It was tough and interesting very much. Thanks for these nice problems!
•  Congrats + Thanks!!
 Problem D is very cool.Keep up the good work! :D
 Cant get your explaination of problem C ....:((.... Could anyone please make it a liitle bit clear . please
 Thx for statistics. It's very good to see them.
 Problem D & E are cool , but quite difficult for me .Thanks for these problems .
 » 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)
 » Can anyone problem C in details plz??
 » 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).