183.md (18375B)
1 Source: https://codeforces.com/blog/entry/4419 2 3 This is the editorial for [Croc Champ 2012 - Final](/contest/183 "Croc Champ 2012 - Final") 4 5 ### Remarks 6 7 One day, I applied to write another round in Codeforces. To my surprise, I was offered to write CROC instead. I'm quite surprised they offer me (an unknown programmer from a notorious country) to write for such an important match! So I happily oblige — kudos for the open culture nurtured by Codeforces! 8 9 I like most the problems of this final round. I think all of them are beautiful in some aspects :). Oh, and all of them emits such concise solutions ;). 10 11 ### [Problem A](//codeforces.com/contest/183/problem/A) 12 13 Author: [dolphinigle](/profile/dolphinigle "Grandmaster dolphinigle") 14 Ad Hoc I supppose... 15 16 This problem is equivalent to calculating the number of reachable locations from point (0, 0) by doing the allowed moves. 17 18 The naive solution is to process the information one by one from first to last, and to keep track on all the reachable positions. 19 20 Claim: At any moment in time, all reachable locations as described above forms a "diamond". 21 22 An extremely informal proof is by induction: 23 24 For instance, let's use the first example: 25 26 ``` 27 UR UL ULDR 28 ``` 29 30 Initially, there's only one possible location (namely, (0, 0)). It forms the basis of our induction: a diamond with width=1 and height=1. 31  32 33 "UR" (and also "DL") extends the width of the diamond into a 2x1 diamond: 34  35 36 Then, "UL" (and also "DR") extends the height of the diamond into a 2x2 diamond: 37  38 39 Finally, "ULDR" extends both the height and the width of the diamond into a 3x3 diamond: 40  41 42 And so there's 9 possible locations. 43 44 To see that this claim is true, suppose by induction our locations so far forms a diamond. By symmetry we only need to see that in the "UR" case, its width is increased by one (I'll omit the similarly seen "ULDR" case). The idea is the new possible locations = the previous diamond shifted one step up UNION that diamond shifted one step right. Indeed, the union of these two diamonds accounts for both the "U" and the "R" moves. 45  46 47 It's not hard to proof that the union of two diamonds with equal dimension that is displaced by vector (1, 1) forms the same diamond with its width increased by 1. 48 49 So, the solution is to keep track the dimension of the diamond, starting from a 1x1 diamond. Then, simply return width * height. 50 51 Reference: See [1631223](/contest/183/submission/1631223 "Submission 1631223 by Endagorion") by [Endagorion](/profile/Endagorion "Master Endagorion") (my favorite CF author! :) ). 52 53 ### [Problem B](//codeforces.com/contest/183/problem/B) 54 55 Author: [dolphinigle](/profile/dolphinigle "Grandmaster dolphinigle") 56 Geometry 57 58 Since there are at least one flamingo, all binoculars will be able to see at least one flamingo. When a binocular is able to see more than one flamingos, then those two flamingos and the binocular must form a line. How many such lines are there? 59 60 Instead of iterating for each pair of binocular and flamingo, we iterate over each pair of flamingos. These two pair of flamingos completely determine the line as described above. If there does not exists a binocular in this line, we can ignore this pair and continue. Otherwise, calculate the number of flamingos in this line, and let it be one of the possible number of flamingos visible from that binocular. 61 62 After this is done, simply sum the maximum number of flamingos of each binocular. This works in O(M^3). Note that this problem can be made to run in O(M^2 log M), but coding that solution is sort of... boring ;3. 63 64 For instance, see [vepifanov](/profile/vepifanov "International Master vepifanov")'s [1631294](/contest/183/submission/1631294 "Submission 1631294 by vepifanov") 65 66 **Remarks** 67 68 Actually [havaliza](/profile/havaliza "Candidate Master havaliza") prepared a much nicer B problem. Unfortunately, we found out at the last moments that the problem may be too similar to a problem (that is used a looooooooong time ago), so we decided to switch that problem with something else. And that's why this problem is here. 69 70 It's too bad, the problem proposed by [havaliza](/profile/havaliza "Candidate Master havaliza") is actually very nice. Perhaps we will see it in one of the upcoming rounds :) 71 72 ### [Problem C](//codeforces.com/contest/183/problem/C) 73 74 Author: [dolphinigle](/profile/dolphinigle "Grandmaster dolphinigle") 75 DFS 76 77 Let's drop the (modulo K). That is, the rule becomes: 78 79 * X->Y implies that Y = X+1 80 * Y->X implies that Y = X-1 81 82 Notice that this problem is then equivalent to finding the maximum possible K such that the above equation holds for all edges, modulo K. 83 84 While we still dropping the "modulo K" thingy, we try to calculate the values of each node. We iterate over each node, and if we haven't processed the node: 85 86 * Number the node 0 (or any other number you like). let's denote this by no[i] = 0. 87 * DFS the node: 88 + DFS(X): if there exists X->Y, then no[Y] = no[X]+1. This follows from the first rule. 89 + DFS(X): if there exists Y->X, then no[Y] = no[X]-1. This follows from the second rule. 90 + If Y is renumbered (that is, the algorithm has renumber it in the past and we renumber it again), consider the difference between the two numbers. We claim that this difference, if not zero, must be a multiple of K. To see this, suppose the two numbers are A and B. By the way our algorithm works, that node must be able to be numbered A or B. Hence, A == B (mod K) must holds. But then, A-B == 0 (mod K) implies that (A-B) is a multiple of K. 91 * If a non-empty multiple of K (let's say it's CYCLEN) is not found in the step above, we claim that the answer is the maximum possible answer: N. Indeed if no such value is found, it means that renumbering the nodes into no[i] % N be correct, since every edge is already consistent with no[i]. 92 * Otherwise, we can simply brute force all divisors of CYCLEN and try each of them. Since "trying" uses O(E) time (that is, by setting each number into no[i] % K and checking whether the two rules holds for all edges) , we have a O(number_of_divisors * E) algorithm, which with the given constraints is less than O(E * sqrt(N)). 93 94 For instance, [sexyprincess91](/profile/sexyprincess91 "Master sexyprincess91") implemented this. [1632321](/contest/183/submission/1632321 "Submission 1632321 by sexyprincess91") 95 96 ### [Problem D](//codeforces.com/contest/183/problem/D) 97 98 Author: [dolphinigle](/profile/dolphinigle "Grandmaster dolphinigle") 99 Dynamic Programming, Probabilities, and a little Greedy 100 101 Suppose we have decided to bring N1 T-shirts of size 1, N2 T-shirts of size 2, ... NM T-shirts of size M. By the linearity of expectation, the expected number of engineers that will receive a T-shirt is equal to the sum of the expected number of engineers that will receive a T-shirt of size K, for all K. 102 103 Suppose we bring Ni T-shirts of size i. Define a random variable Xij as the number of engineer that will receive the j-th T-shirt of size Ni that we bring. Hence, the expected number of engineers that will receive the Ni T-shirts of size i that we bring is equal to the sum of Xij over all j. Since Xij is either 0 or 1, Xij is equal to Pij, the probability that there will be an engineer that will receive the j-th T-shirt of size i that we bring. This is equal to the probability that there will be at least j engineers that fits inside T-shirt of size i. 104 105 As a result of our discussion, to maximize the expectation, it boils to maximizing the sum over Xij. Hence, we receive our first solution: Calculate the value of all Xij, and pick the N largest value. A DP implementation allows us to accumulate all Xij value in O(N*N*M) time, yielding an O(N*N*M) solution. 106 107 We will now reduce the time limit to O(N*N + N*M). Notice that the algorithm above only need us to find the N largest values of Xij. Denote by f(n, i, j) the probability that, amongst engineers numbere 1 through n, at least j of them fits inside T-shirt of size i. f(n, i, j) can be computed with the following recurrence: f(n, i, j) = f(n-1, i, j-1) * fit_chance(n, i) + f(n-1, i, j) * (1.0 — fit_change(n, i)) Where fit_chance(t-shirt, engineer) is the probability that engineer fits inside the t-shirt size. 108 109 The formula above can be inferred from simple logic: if the n-th engineer fits inside t-shirt of size i (with fit_change(n, i) probability), then f(n, i, j) is obviously equal to f(n-1, i, j-1). Otherwise, it'll equal f(n-1, i, j). 110 111 Now, observe that Xij = f(N, i, j). Indeed, this is one of the possible DPs that can lead to the O(N*N*M) solution. However, we will show that we do not need to compute f(n, i, j) for all possible inputs if we're asked to find only the N largest values of Xij. 112 113 The key observation is the following obvious fact. If Xij is included in the N largest values, then Xi(j-1) must also be included there. Inductively, Xik for k < j must also be included in the N largest values. Indeed, it's obvious that Xij must be non-increasing with respect to j. 114 115 Hence the algorithm works as follows. First, we create a pool of numbers Xi1, for all i, totalling M numbers. Then, we iterate N times. In each iteration, we pick the largest number in the pool, say, Xij. Then, we add Xij as one of the K largest values. Then, we take out Xij from the pool, and insert Xi(j+1) as its replacement. That it correctly picks the N largest Xij values follows immediately from our argument in the paragraph preceeding this. 116 117 Now, if we use the recurrence f(n, i, j) above to compute each Xij, what is the complexity of this algorithm? If we memoize f(n, i, j), we claim that it's O(N*N + N*M). To see this, we notice that the only values required to compute f(n, i, j) using the recurrence above are the values f(m, i, l) such that m <= n and l <= j. However, we notice that due to how our algorithm works, when we need to compute Xij, we must have already computed Xi(j-1) before, so that all values f(m, i, l) for m <= n and l <= j-1 are already available. So the only NEW values that we need to compute are f(m, i, j), m <= n. There are n such values. 118 119 Since we need to compute at most O(N) values of Xij, the total complexity this part contributes is O(N*N). Depending on how you implement the "pick largest from pool" algorithm, the total complexity can be either O(N*N + N*M) or O(N*N + N*log M). 120 121 Yes, somebody did this in the contest :). [Dmitry_Egorov](/profile/Dmitry_Egorov "Candidate Master Dmitry_Egorov") [1632270](/contest/183/submission/1632270 "Submission 1632270 by Dmitry_Egorov") saved my problem from loneliness :) 122 123 Bonus Section: Now here's an extremely interesting solution shown by the following Python pseudocode: 124 125 ``` 126 values = [] 127 for size in range(M): 128 i = 1 129 while (val = f(N, size, i)) > epsilon: 130 values.append(val) 131 ++i 132 end 133 end 134 Print the sum of the largest N values in array values. 135 ``` 136 137 Its correctness is immediate as long as epsilon is reasonably small (since f(N, size, i) is non-increasing with respect to i). What is the complexity of this very simple algorithm? 138 139 I am unable to come up with a hard, solid proof, but since f(N, size, i) exponentially falls (except if some probabilities are 1, in which case some other T-shirt must have less value to worry on), the complexity is somewhere near O(N * N). Indeed for the current set of test cases, its speed exceeds that of the intended solution. 140 141 Although [rng_58](/profile/rng_58 "International Grandmaster rng_58") do not implement this exact algorithm, he used the <EPS ignore idea in his solution [1631960](/contest/183/submission/1631960 "Submission 1631960 by rng_58") 142 143 **Remarks** 144 145 I really really wanted to link [Gerald](/profile/Gerald "Master Gerald")'s handle in the statement :). Too bad Codeforces doesn't support it. 146 147 ### [Problem E](//codeforces.com/contest/183/problem/E) 148 149 Author: [dolphinigle](/profile/dolphinigle "Grandmaster dolphinigle") 150 Very greedy 151 152 Brute force P: the number of Packages each kid will have at the end. There are at most N/M possible such value. We will assume that P is fixed during our discussion. 153 154 If we know P, we know that if kid i purchases a total of X candies, then kid i+1 must purchase at least X+P candies (1 more than each package purchased by kid i). Hence, assume that money[i] <= money[i+1] — P. 155 156 Two consecutive packages purchased by the SAME kid must differ by at least M. Indeed, otherwise there are less than M-1 packages for the other M-1 kids to buy from (Pigeonhole rocks by the way). 157 158 For the sake of our discussions below, we refer to the following example with N=8, and M=3 kids. The allowances of the kids are 7, 10, and 14. 159 160  161 162 Suppose we know all candies kid 0 purchased (red bags denote the packages kid 0 purchased). 163 164  165 166 We claim that the optimal solution can be computed rather... easily with the following greedy algorithm: (assume that the candy packages kid 0 purchase is sorted in an ascending order). We iterate over the remaining kids, starting from kid 1. First, let the kid purchase the minimum possible candies: 167 168  169 170 Next, if the allowance is still greater than the sum of candies, and if one of his package(s) can still be shifted to the right while maintaining the condition that a possible solution exists, do so. If there are multiple package(s) that can be shifted, shifting any of them does not change the optimal answer. 171 172  173 174 Note: since we've assumed that money[i] <= money[i+1]-P, the only condition is that between the package purchased by kid 1 an the next package purchased by kid 0, there exists at least N-2 packages. For instance, this is illegal, since there is no package that kid 2 will be able to purchase between 4 and 5. 175 176  177 178 We iterate this once more for kid 2, obtaining: 179 180  181 182 And we're done. It's arguably the maximum possible value, since there is no reason why we shouldn't shift a package for a kid to the right if we can (formal proof by contradiction). 183 184 Claim: If we know the packages for kid 0, the maximum total candies purchased can be computed in O(M), where M is the number of kids. 185 186 The algorithm simulates our discussion above. However it is not obvious how to do that in O(M). So, suppose kid 0 purchase the candies like this: 187 188  189 190 Now, try putting the other P-1 packages into the minimum possible locations: 191 192  193 194 The packages inside the yellow boxes denote what we will call [FREEDOM](http://gundam.wikia.com/wiki/ZGMF-X10A_Freedom_Gundam). Basically FREEDOM is the count on how many times we can at most shift a package to the right as in our discussion above. 195 196 Now, consider kid 1. First, as in our discussion, kid 1 takes the minimum amount of packages, which is equal to sum[kid 0] + P. Next, he will attempt to shift the packages if possible. Notice that the only thing that affects the overall sum of the candy is only the number of shifts performed, not which package actually got shifted. So, this means that, the amount of shift can be easily calculated by min(money[1] — (sum[kid 0] + P), FREEDOM). And then, FREEDOM is deducted from this value, while the amount of candies purchased by kid 1 is incremented by this value. 197 198 Hence, simulating the algorithm in our discussion if we're only to output the total amount of candies can be done in O(M). 199 200 The result of our discussion so far is this. Notice that the last algorithm only depends on how many candies kid 0 purchased, and FREEDOM. 201 202 Now we will remove the assumption that we know which packages kid 0 decides to purchase. 203 204 Claim: It is optimal for kid 0 to purchase as many candies as possible. 205 206 Suppose kid 0 does not purchase the maximum possible of candies he can purchase. Now, consider whether or not kid 1 "shifted" his candies. 207 208 * If he shifted any of them, say package X, then instead of purchasing package X-1, kid 0 should purchase package X, improving the overall amount of candies. That is, instead of 209  210 It's better to 211  212 * If kid 1 did not "shift" his candies because the amount of money he spent is already equal to his allowance, then the amount of candies purchased by kid 0 must be maximum since money[i] <= money[i+1] — P. 213 * Otherwise, we can apply this inductively to kid 2 and so forth. That is, instead of 214  215 It's better to 216  217 218 Okay, now we know the sum of candies that we should give to kid 1. Since the performance of our algorithm increase with FREEDOM, we should next try to maximize FREEDOM. 219 220 Claim: FREEDOM depends only on the position of the FIRST candy package purchased by kid 0. 221 222 This can be shown by simple computation, and its equal to N — pos — M*P (or something like that). 223 224 Hence, we should try to minimize the first candy package purchased by kid 0, while keeping the sum maximum. This can be done in O(1) using a bunch of N*(N+1)/M * P formulas. 225 226 Hence, since there are N/M package numbers to be brute forced, and each iteration uses O(M) time, the total complexity is O(N/M) * O(M) = O(N). 227 228 For instance, see [1632210](/contest/183/submission/1632210 "Submission 1632210 by rng_58") by [rng_58](/profile/rng_58 "International Grandmaster rng_58") (again :) ). 229 230 **Epilogue** 231 232 Thank you for participating in the match! 233 234  235 236 Hope to see you again!