347.md (10870B)
1 Source: https://codeforces.com/blog/entry/8903 2 3  4 5 # Overview 6 7 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. 8 9 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](//codeforces.com/problemset/problem/251/C) 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) 10 11 The standard solution of problem C is *O*((*b* - *a*) + *nlogn*). The first expected correct solution was written by [zeliboba](/profile/zeliboba "International Master zeliboba"). [http://codeforces.com/contest/346/submission/4512654](//codeforces.com/contest/346/submission/4512654) 12 13 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](/profile/Petr "International Grandmaster Petr") is the man who closest to it. 14 15 The winner comes to [cgy4ever](/profile/cgy4ever "Grandmaster 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](/profile/rng_58 "International Grandmaster rng_58"), because of the combination of decent speed in A, B, C, D. 16 17 Problem B belongs to me, problem C belongs to [CMHJT](/profile/CMHJT "Candidate Master CMHJT") and others belong to [UESTC_Nocturne](/profile/UESTC_Nocturne "International Master UESTC_Nocturne"). The illustrator of problem C is [Chairman Miao(貓主席)](http://www.pixiv.net/member_illust.php?mode=medium&illust_id=38602657). 18 19 # Editorial 20 21 ### [Problem A. Alice and Bob](//codeforces.com/problemset/problem/346/A) 22 23 #### Brief description: 24 25 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. 26 27 #### Analysis: 28 29 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*, 2*d*, 3*d*, ... *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. 30 31 ### [Problem B. Lucky Common Subsequence](//codeforces.com/problemset/problem/346/B) 32 33 #### Brief description: 34 35 You have been given two strings *s*1, *s*2 and *virus*, and you have to find the longest common subsequence of *s*1 and *s*2 without *virus* as a substring. 36 37 #### Analysis: 38 39 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*2) dynamic programing. 40 41 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*3). 42 43 ### [Problem C. Number Transformation II](//codeforces.com/problemset/problem/346/C) 44 45 #### Brief description: 46 47 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. 48 49 #### Analysis: 50 51 I bet there is a few people know the greedy method even if he/she have solved the early version before. 52 53 [Codeforces #153 Div 1. Problem C. Number Transformation](//codeforces.com/problemset/problem/251/C) 54 55 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]. 56 57 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. 58 59 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** 60 61 ### [Problem D. Robot Control](//codeforces.com/problemset/problem/346/D) 62 63 Let's dp from t to s. 64 65 dp[u] = min(min(dp[v]) + 1 , max(dp[v])) | u->v 66 67 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. 68 69 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. 70 71 But it is not appropriate for this problem. 72 73 (In fact, we add a part of targeted datas in pretest, these datas are enough to block most of our [Bellman-Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm), although there is still a few participator can get accepted by Bellman-Ford algorithm during the contest. 74 75 Check [rares.buhai](/profile/rares.buhai "Candidate Master rares.buhai")'s [solution](//codeforces.com/contest/346/submission/4520171) 76 77 dp[u] = min(min(dp[v]) + 1 , max(dp[v])) | u->v 78 79 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. 80 81 ``` 82 while (!Q.empty()) { 83 u = Q.front(), Q.pop_front() 84 for each edge from v to u 85 --out_degree[v] 86 if (out_degree[v] == 0) { 87 relax dp[v] by dp[u] 88 if success, add v to the front of Q 89 } 90 else{ 91 relax dp[v] by dp[u] + 1 92 if success, add v to the back of Q 93 } 94 } 95 ``` 96 97 Check [Ra16bit](/profile/Ra16bit "International Master Ra16bit")'s [solution](//codeforces.com/contest/346/submission/4519668) to see how it works. 98 99 ### [Problem E. Doodle Jump](//codeforces.com/problemset/problem/346/E) 100 101 #### Brief description: 102 103 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*. 104 105 #### Analysis: 106 107 Take *a* =5, *p* =23 for example ... Divided the numbers in group. 108 109 ``` 110 0 5 10 15 20 111 2 7 12 17 22 112 4 9 14 19 113 1 6 11 16 21 114 3 8 13 18 115 ``` 116 117 We start a new group when the number > P 118 119 We found the difference between the elements of the first group is 5, The subsequent is filling some gap between the them ... 120 121 After some observation we could found that we should only consider into one gap ...(e.g. [0, 5] or [15, 20] or [20, 25] ... ) 122 123 ``` 124 0 5 10 15 20 125 2 7 12 17 22 126 4 9 14 19 127 1 6 11 16 128 ``` 129 130 That says .. *a* =5, *p* =23 is roughly equal to some things in small scale? 131 132 So let's check it in detail. Lemma 1. In any case, the gap after 20 won't better than any gap before it. 133 134 ``` 135 0 5 10 15 20 136 2 7 12 17 22 137 4 9 14 19 138 1 6 11 16 139 ``` 140 141 For example, in this case, the gap after 20 is: 20, 22 And it has 16 in [15, 17] but no 21. 142 143 Is there any chance that [20, 23] is better than [15, 20]? 144 145 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]) 146 147 So we only need to consider [15, 20] ... and we found [15, 20] is roughly equal to [0, 5] 148 149 ``` 150 e.g. : 15 20 17 19 16 18 151 equal: 0 5 2 4 1 3 152 ``` 153 154 we say 'roughly' because we havn't check some boundary case like there is 3 but on 18 ... 155 156 ``` 157 0 5 10 15 20 158 2 7 12 17 22 159 4 9 14 19 160 1 6 11 16 21 161 3 8 13 162 ``` 163 164 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) 165 166 The rest things is to discuss wheather 5 is necessary or not. 167 168 Let's we have: 169 170 ``` 171 0 2 4 172 1 3 173 ``` 174 175 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. 176 177 Proof: Elemets in 1st floor is: 178 179 ``` 180 0 a 2a 3a ... 181 ``` 182 183 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. 184 185 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. 186 187 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 ... 188 189 So we set a' = min(a-p%a, p%a), so a'<=a/2, therefore, the final time complexity is *O*(*logn*). 190 191 You can check [Petr](/profile/Petr "International Grandmaster Petr") ['s solution](//codeforces.com/contest/346/submission/4523388) for detail.