Overview

In DIV 1, there are 4 interesting problems together with a normal one. We think it is reasonable because we can't have a round fullly with intelligence. Problem A, C have weak pretests while others intended to be strong. About more then 200 participants solve A in the early 45mins, then a few of them start from C while most of the other start from B.

Problem B is a rather standard problem, but if you're unfamiliar with the algorithm, it can be very hard. Problem C is a more intersting problem. As the name implies, there was a similar version in the previous round before, but this time it has a brand new constrains.(So here we have a psychology experiment: could different constrains make people thinking in a slightly different way?ww)

The standard solution of problem C is O((b - a) + nlogn). The first expected correct solution was written by zeliboba. http://codeforces.me/contest/346/submission/4512654

After that, some people start to solve problem D. Problem D looks like a hard dp problem on a graph at the first glance, the key point is how to avoid the circle in the transfer equation. It turn out to be elegant after you could found a right order of the evaluation. Problem E is challenging which you need find a way to transform the original question into a smaller scale, and cut off many many corner cases ... And in the very end, you find a way like binary search to get O(logn) as the time complexity. No one manage to solve problem E during the contest, maybe Petr is the man who closest to it.

The winner comes to cgy4ever, because he found the draw-black in his previous C submission during the very beginning even when there is nobody hack him! He resubmit it decisively and get back when finished problem D. After that, he use the same trick which made him failed before to hack others and got a handsomely rewards. The second place went to rng_58, because of the combination of decent speed in A, B, C, D.

Problem B belongs to me, problem C belongs to CMHJT and others belong to UESTC_Nocturne. The illustrator of problem C is Chairman Miao(貓主席).

Editorial

Problem A. Alice and Bob

Brief description:

Alice and Bob play a game, the rules are as follows: First, they will get a set of n distinct numbers. And then they take turns to do the following operations. During each operation, either Alice or Bob can choose two different numbers x and y from the set, as long as |x - y| is not in the set, then they add it to the set. The person who can not choose two numbers successfully will lose the game. The question is who will finally win the game if both of them do operations optimally. Remember that Alice always goes first.

Analysis:

First, no matter what happend, the number set we get at the very endding will be same all the time. Let's say d = gcd{x_i}. Then the set in the endding will be some things like {d, 2d, 3d, ... max{x_i}}. So there is always max{x_i} / d — n rounds. And what we should do rest is to check the parity of this value.

Problem B. Lucky Common Subsequence

Brief description:

You have been given two strings s₁, s₂ and virus, and you have to find the longest common subsequence of s₁ and s₂ without virus as a substring.

Analysis:

This is a rather classical problem, let's say if there is no virus, then it is the classical **LCS ** problem. You can solve this by a O(n²) dynamic programing.

When consider about the virus, we should add 1 more dimension on the state to trace the growth of the virus. It can be done by wheather Aho-Corasick automation, or KMP when there is only one virus in this case. The overall time complexity is O(n³).

Problem C. Number Transformation II

Brief description:

You have a number b, and want to minus it to a, what you can do in each step is weather subtract 1 or b mod x_i from b. And we ask what is the minimum number of steps you need.

Analysis:

I bet there is a few people know the greedy method even if he/she have solved the early version before.

Codeforces #153 Div 1. Problem C. Number Transformation

Let dp[k] denotes the minimum number of steps to transform b+k to b. In each step, you could only choose i which makes b+k-(b+k) mod x[i] minimal to calc dp[k]. It works bacause dp[0..k-1] is a monotone increasing function. Proof: - Say dp[k]=dp[k-t]+1.If t==1, then dp[0..k] is monotone increasing obviously.Otherwise dp[k-1]<=dp[k-t]+1=dp[k] (there must exist a x[i] makes b+k-1 also transform to b+k-t,and it is not necessarily the optimal decision of dp[k-1]). So dp[k] is a monotone increasing function, we can greedily calc dp[a-b].

In the first glance, it looks like something which will run in square complexity. But actually is linear. That is because, we could cut exactly max{x_i} in each 2 step. It can be proof by induction.

So the remians work is to delete those same x_i, and watch out some situation could cause degeneration. Many of us failed in this last step and got TLE

Problem D. Robot Control

Let's dp from t to s.

dp[u] = min(min(dp[v]) + 1 , max(dp[v])) | u->v

Here dp[u] means, the minimum number of orders mzry1992 needs to send in the worst case. The left-hand-side is sending order while the right-hand side is not. At the beginning, we have dp[t] = 1, and dp[s] will be the answer.

We can see there is circular dependence in this equation, in this situation, one standard method is using Bellman-Ford algorithm to evaluate the dp function.

But it is not appropriate for this problem.

(In fact, we add a part of targeted datas in pretest, these datas are enough to block most of our Bellman-Ford algorithm, although there is still a few participator can get accepted by Bellman-Ford algorithm during the contest.

Check rares.buhai's solution

dp[u] = min(min(dp[v]) + 1 , max(dp[v])) | u->v

The expected solution is evaluating the dp function as the increased value of dp[u] itself. Further analysis shows, wheather we decided sending order or not in u can be judged as the out-degree of u.

while (!Q.empty()) {
    u = Q.front(), Q.pop_front()
    for each edge from v to u
        --out_degree[v]
	if (out_degree[v] == 0) {
           relax dp[v] by dp[u]
           if success, add v to the front of Q
	}
	else{
	   relax dp[v] by dp[u] + 1
	   if success, add v to the back of Q
        }	
  }

Check Ra16bit's solution to see how it works.

Problem E. Doodle Jump

Brief description:

You have been give a, p, n, h (gcd(a, p) = 1), For each ai mod p, (i∈[1, n]), check weather the maximum distance in neighborhood after sorting is <= h.

Analysis:

Take a =5, p =23 for example ... Divided the numbers in group.

0  5  10  15  20
2  7  12  17  22
4  9  14  19
1  6  11  16  21
3  8  13  18

We start a new group when the number > P

We found the difference between the elements of the first group is 5, The subsequent is filling some gap between the them ...

After some observation we could found that we should only consider into one gap ...(e.g. [0, 5] or [15, 20] or [20, 25] ... )

0  5  10  15  20
2  7  12  17  22
4  9  14  19
1  6  11  16

That says .. a =5, p =23 is roughly equal to some things in small scale?

So let's check it in detail. Lemma 1. In any case, the gap after 20 won't better than any gap before it.

0  5  10  15  20 
2  7  12  17  22
4  9  14  19
1  6  11  16

For example, in this case, the gap after 20 is: 20, 22 And it has 16 in [15, 17] but no 21.

Is there any chance that [20, 23] is better than [15, 20]?

No, that is because, when there is no 21, then (19+5)%23 = 1, go to next floor. and there is no corresponding gap after 20 ([22, 24]) for this gap ([17, 19])

So we only need to consider [15, 20] ... and we found [15, 20] is roughly equal to [0, 5]

e.g. :    15 20 17 19 16 18 
equal:     0  5  2  4  1  3

we say 'roughly' because we havn't check some boundary case like there is 3 but on 18 ...

0  5  10  15  20 
2  7  12  17  22
4  9  14  19
1  6  11  16  21
3  8  13 

If it happend, we should remove the number 3. .. If we can remove the element 5, then we can from a=5, p=23 to a'=2, p'=5 ...(n' = an/p, a' = a-p%a, if there is 3 but no 18, n'=n'-1)

The rest things is to discuss wheather 5 is necessary or not.

Let's we have:

0 2 4
1 3

If the 2*n'<5, then there is only one floor, the answer is max(2, 5-2*n'). If there is more than one floor, we could conclude that 5 is useless.

Proof: Elemets in 1st floor is:

0 a 2a 3a ...

Let's say the maximum elements in 1st floor is x, then the minimum element in the 2nd floor is b0 = x+a-p, because b0 — a = x-p, so the difference between b0 and a is equal to the difference between x and p. That is, we can consider [b0, a] rather than [x, p], when there is a element insert in [b0, a], there must be some element insert in [x, p] in the same position.

So we have have succeeded to transform our original problem into a small one. Of couse, this problem havn't been solved, we haven't consider the time complexity. Says a' = a — p%a, when p = a+1, then a' = a-1, but we have a equal to 10^9, it won't work.

But, let's we have A1, A2, ... An ... and we subtract d from all of them, the answer won't be changed. So we can use p%a substitute for a-p%a, this is equivalent to we subtract %p% from all of them ...

So we set a' = min(a-p%a, p%a), so a'<=a/2, therefore, the final time complexity is O(logn).

You can check Petr 's solution for detail.