Блог пользователя ir5

Автор ir5, 13 лет назад, По-английски
Statistics
Problem#Submission#Passed Pretest#Passed FinaltestAverage Score
A858767660433.36
B749655600813.28
C4673522291093.07
D281441315.00
E2211620.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 |bi|, so all intervals can be calculated in O(|sn· |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, ... 0When 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· |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).
Разбор задач Codeforces Beta Round 71
  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
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~
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Thanks for editorial! And at most for solution of problem D!
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Now I got AC on Problem E!
It was tough and interesting very much.
Thanks for these nice problems!
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Problem D is very cool.
Keep up the good work! :D
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Thx for statistics. It's very good to see them.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hm... I coded almost the same solution for E as described above except for one thing: from current position I tried moving right and checked that from new location I can reach (n,n) without violating the security for each of four sensors separately. But the fact that there are four paths to (n,n) each of which is ok with one of four sensors doesn't mean that there is one path that will be ok with all of them? (Or does it? Because I didn't find a test and my solution passed the systests)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem D & E are cool , but quite difficult for me .
Thanks for these problems .
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

»
6 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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).

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Hello Codeforces community,

I have a theoretical question that I would like to discuss. It's not related to a specific problem, but rather a concept in programming or a general programming question.

The question I have in mind is: what is the maximum limit of array 2D and vector 2D in c++? . I've been studying this topic, but there are still some aspects I'm unclear about.

I would appreciate it if someone could help clarify this for me or provide some insights into this theoretical concept. Any resources, explanations, or examples would be very helpful.

Thank you in advance for your assistance!

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't know what exactly limit are but I think it's approximately 1e6. Limit between array 2D and vector 2D are the same but with vector, you can resize it freely while array you have to fix the limit from the beginning.