434.md (16685B)
1 Source: https://codeforces.com/blog/entry/12397 2 3 If you have any questions or suggestions, or if you have a solution different to ours that you want to share with us, feel free to comment below :) 4 5 **Author solutions are added.** 6 7 --- 8 9 ### [Div. 2 A — Kitahara Haruki's Gift](//codeforces.com/contest/433/problem/A) 10 11 Denote *G* as the sum of the weight of the apples. If *G* / 100 is not an even number, then the answer is obviously "NO". Otherwise, we need to check if there is a way of choosing apples, so that the sum of the weight of the chosen apples is exactly . 12 13 A simple *O*(*n*) approach would be to enumerate how many 200-gram apples do we choose, and check if we can fill the rest with 100-gram apples. We can also solve this problem using a classic knapsack DP. 14 15 **Solution:** [6712942](/contest/433/submission/6712942 "Посылка 6712942 от huzecong") 16 17 --- 18 19 ### [Div. 2 B — Kuriyama Mirai's Stones](//codeforces.com/contest/433/problem/B) 20 21 Sort sequence *v* to obtain sequence *u*. Sorting can be done in  using quicksort. Now we are interested in the sum of a interval of a given sequence. This can be done by calculating the prefix sum of the sequence beforehand. That is, let . The sum of numbers in the interval [*l*, *r*] would then be *sv**r* - *sv**l* - 1. We can deal with sequence *u* likewise. 22 23 Preprocessing takes *O*(*n*) time, and answering a query is only *O*(1). The total complexity would be . 24 25 **Solution:** [6713020](/contest/433/submission/6713020 "Посылка 6713020 от zhonghaoxi") 26 27 --- 28 29 ### [Div. 2 C](//codeforces.com/contest/433/problem/C) / [Div. 1 A — Ryouko's Memory Note](//codeforces.com/contest/434/problem/A) 30 31 Suppose we're merging page *x* to page *y*. Obviously page *x* should be an element of sequence *a*, otherwise merging would have no effect. Enumerate all possible values of *x*, and denote sequence *b* as the elements of *a* that are adjacent to an element with value *x*. If one element is adjacent to two elements with value *x*, it should appear twice in *b*. However, if one element itself is *x*, it should not appear in *b*. 32 33 For example, suppose we have *a* = {2, 2, 4, 1, 2, 1, 2, 3, 1}, then sequence *b* for *x* = 2 would be *b* = {4, 1, 1, 1, 3}, where the 6-th element appears twice. 34 35 Problem remains for finding a optimum value for *y*. Let *m* be the length of sequence *b*. When merging *x* to *y*, the change in answer would be 36 37  38 39 We only care about the left part, as the right part has nothing to do with *y*. We can change our problem to the following: 40 41 * *Given *n* numbers on the number axis, find a number *x* so that the sum of the distance between *x* and the *n* given numbers is minimum.* 42 43 This is, however, a classic problem. We have the following conclusion: 44 45 * *The number *x* in the problem should be the median of the *n* numbers.* 46 47 **Proof:** 48 49 * Consider the case where *n* is odd. Proof is similar for cases where *n* is even. 50 * We choose an arbitary number as *x*. Suppose there are *l* numbers on the left of *x*, and *r* numbers on the right of *x*. If *x* is the median, then *l* = *r*, so what we're going to prove is that optimal answer cannot be achieved when *l* ≠ *r*. 51 * Suppose *l* < *r*, consider what would happen to the answer if we add *d*(*d* > 0) to *x* (Here we assume that adding *d* to *x* does not affect the values of *l* and *r*). The distance between *x* and all the numbers on the right would decrease by *d*, while the distance between *x* and all numbers on the left would increase by *d*. So the answer would decrease by (*r* - *l*)*d*, which is a positive value, since *l* < *r*. 52 * So *x* would keep increasing until *l* = *r*, when optimal answer can be achieved. Thus *x* is the median of the *n* numbers. 53 54 This brings us to our solution. Simply sort sequence *b* and find its median, then calculate the answer. The final answer would be the optimal one from all possible values of *x*. The complexity is , as the sum of the length of all *b* sequences does not exceed 2*n*. 55 56 **About the pretests:** Pretests for this problem are deliberately made weak, in order to make hacking more fun. None of the pretests contains adjacent numbers with the same value. 57 58 **Solution:** [6712939](/contest/433/submission/6712939 "Посылка 6712939 от huzecong"), [6713018](/contest/433/submission/6713018 "Посылка 6713018 от zhonghaoxi") 59 60 --- 61 62 ### [Div. 2 D](//codeforces.com/contest/433/problem/D) / [Div. 1 B — Nanami's Digital Board](//codeforces.com/contest/434/problem/B) 63 64 Consider a similar problem: find the maximum light-block of the whole board. Constraints to this problem are the same as the original problem, but with no further operations. 65 66 A brute-force idea would be to enumerate all four edges of the block, checking can be done with two-dimensional prefix sums, so the time complexity is *O*(*n*4). Obviously it would receive a TLE verdict. 67 68 Why should we enumerate all four edges? Let's enumerate the lower- and upper-edge, and now our problem is only one-dimensional, which can be easily solved in *O*(*n*) time. Now our complexity is *O*(*n*3), still not fast enough. 69 70 Let's try to enumerate the lower-edge only, and now what we have is an array *up*[], denoting the maximum "height" of each column. To be specific, suppose the lower-edge is row *x*, then *up*[*i*] is the maximum value such that (*x*, *i*), (*x* - 1, *i*), ..., (*x* - *up*[*i*] + 1, *i*) are all light. If we choose columns *l* and *r* as the left- and right-edge, then the area of the maximum light-block with these three sides fixed would be 71 72  73 74 Let , what if we enumerate *h*, and find the leftmost *l* and the rightmost *r*? To be more specific, we enumerate a column *p*, and let the height of this column be the height of the block. Now we want to "stretch" the left and right sides of the block, so we're looking for the leftmost column *l* such that . Similarly look for the rightmost column *r*, then the maximum light block with its lower-edge and a point in the upper-edge fixed would be (*r* - *l* + 1)·*up*[*p*]. 75 76 This approach can be optimized with disjoint-set unions (abbr. DSU). Imagine that initially the *up*[] array is empty. Let's add the elements of *up*[] one by one, from the largest to the smallest. Maintain two DSUs, and denote them as *L* and *R*.When we add an element *up*[*i*], set the father of *i* as *i* + 1 in *R*, so that *i* will be "skipped" during the "find" operation of DSU. Similarly set the father of *i* as *i* - 1 in *L*. Simply find the root of *i* in *L* and *R*, and we would have *l* and *r*. 77 78 Now this problem can be solved in quasi-quadratic time. We can actually further optimize it to quadratic time using monotonic queues, but we'll not talk about it here. Let's go back to the original problem. 79 80 Suppose there are no modifications, operations only contain queries. Then we could simply maintain the *up*[] array of every row, and similarly maintain *down*[], *left*[] and *right*[] arrays. Use the approach described above to achieve quasi-linear time for the answering of a query. 81 82 Now consider modifications. Modification of a single pixel only changes the values of *O*(*n* + *m*) positions of the arrays. So modifications can be handled in linear time. 83 84 The total complexity for the algorithm is *O*(*n*2 + *qn*·α(*n*)), where α(*n*) is the inverse of the Ackermann function, which is often seen in the analysis of the time complexity of DSUs. 85 86 **Solution:** [6712937](/contest/433/submission/6712937 "Посылка 6712937 от huzecong"), [6713016](/contest/433/submission/6713016 "Посылка 6713016 от zhonghaoxi") 87 88 --- 89 90 ### [Div. 2 E](//codeforces.com/contest/433/problem/E) / [Div. 1 C — Tachibana Kanade's Tofu](//codeforces.com/contest/434/problem/C) 91 92 A straightforward brute-force idea would be to enumerate all numbers in the interval [*l*, *r*], and count how many of them have a value greater than *k*. This approach is way too slow, but nevertheless let's try optimizing it first. 93 94 The enumeration part seems hard to optimize, so let's consider what is the fastest way of calculating the value of a string. This is a classic problem that can be solved using an Aho-Corasick automaton (abbr. ACA). Build an ACA with the given number strings, and simply "walk" in the automaton according to the string to be calculated. 95 96 Consider a common method when dealing with digits — split the interval [*l*, *r*] into two, [1, *r*] minus [1, *l* - 1]. Then use DP to solve an interval, take [1, *r*] for instance. Consider filling in the numbers one by one, we need to record in the states of the DP the position in the string, and a flag denoting whether we're "walking on the edge of the upper bound", that is, whether the numbers we've filled are the prefix of the upper-bound *r*. 97 98 How can we use the approach above in this problem? Can we combine this approach with our ACA? The answer is yes, further record in the states of the DP the ID of the node we're currently "standing on" in the ACA. Consider the transfer of this DP, enumerate which number we're going to fill in, and check using our flag if the current number will be greater than the upper-bound. Appending a number to the end of our string would result in a change of the ID of the node in our ACA, so "walk" along the transferring edge in the ACA. 99 100 What about the limit of values? Simply record the current value in our DP state, during transfer, add the value stored in the ACA's node to the value stored in our state. 101 102 The tricky bit is the leading zeros. Numbers can't have leading zeros, but number strings can. How can we distinguish leading zeros from zeros in the middle of the number? We keep another flag, denoting whether we're still dealing with leading zeros. 103 104 So finally our state looks like *f*[*len*][*node*][*val*][*upper*_*bound*_*flag*][*leading*_*zero*_*flag*], where *len*, *node*, and *val* are current length of number, ID of current node in ACA, and current value of number respectively. Let *N* be the total length of all number string, and *L* be the length of *r*, the total complexity would be *O*(*NLkm*), since the number of states is *O*(*NLk*) and transfer takes *O*(*m*) time. 105 106 **Solution for the approach above:** [6712934](/contest/433/submission/6712934 "Посылка 6712934 от huzecong") **Solution for a different approach:** [6713013](/contest/433/submission/6713013 "Посылка 6713013 от zhonghaoxi") 107 108 --- 109 110 ### [Div. 1 D — Nanami's Power Plant](//codeforces.com/contest/434/problem/D) 111 112 We can use a flow network to solve the problem. 113 114 For each variable *x**i*, create *r**i* - *l**i* + 2 points, and denote them as *node*(*i*, *l**i* - 1) to *node*(*i*, *r**i*). Edges are as follows: 115 116 * Link *source* to each *node*(*i*, *l**i* - 1) with capacity of infinity. 117 * Link each *node*(*i*, *r**i*) to *sink* with capacity of infinity. 118 * Link each *node*(*i*, *x* - 1) to *node*(*i*, *x*) with capacity of *MAX* - *f**i*(*x*). Here *MAX* is a number greater than every possible value of the variables. 119 120 Let *C* be the value of the minimum cut of this network. If there are no further restrictions, it is obvious that *MAX*·*n* - *C* is the maximum profit. 121 122 Now consider the restrictions. Suppose a restriction is *x**u* ≤ *x**v* + *d*, then for each *node*(*u*, *x*), link it to *node*(*v*, *x* - *d*) (if exists) with a capacity of infinity. If there exists a solution, *MAX*·*n* - *C* will be the optimal profit. 123 124 We want to prove that the edges with infinite capacity can really restrict our choice of values for variables. Note that a valid solution is correspondent to a cut of the graph. It can be proved that if a restriction is not satisfied, there will be a augmenting path in the graph. You can verify this by drawing the graphs. And because we are looking for the minimum cut, in this case the maximum sum, there can be no valid solution with a greater sum. 125 126 **About the time limit:** The time limit for this problem is 5 seconds, which is by far greater than this solution actually need. We set the time limit to 5 seconds because of possible worst-case complexity of the maximum flow algorithm, although in "real-life" cases that complexity is never achieved. 127 128 **About the solution:** This solution takes advantage of the fact that there are few possible values for the variables. And also the fact that functions are all quadratic is no use here, so statements may be quite misleading. If you have any ideas on how to solve the problem with a larger range for variables, or a solution using the fact that functions are quadratic, please share it in the comments :) 129 130 **Solution:** [6712933](/contest/434/submission/6712933 "Посылка 6712933 от huzecong"), [6713009](/contest/434/submission/6713009 "Посылка 6713009 от zhonghaoxi") 131 132 --- 133 134 ### [Div. 1 E — Furukawa Nagisa's Tree](//codeforces.com/contest/434/problem/E) 135 136 *In order not to mess things up, we use capital letters *X*, *Y* and *K* to denote the values in the original problem.* 137 138 First, we can build a directed graph with *n*2 edges. Let *E*(*i*, *j*) be the edge from node *i* to node *j*. If path (*i*, *j*) is good, the color of *E*(*i*, *j*) is 0, otherwise it is 1. 139 140 We want to calculate the number of triplets (*i*, *j*, *k*) that satisfies (*i*, *j*), (*j*, *k*) and (*i*, *k*) are all good or all not good. It equals the number of directed triangles, the color of whose three edges are the same. (The triangle is like: ) 141 142 Calculating this is difficult, so let us calculate the number of directed triangles whose three edges are not all the same. 143 144 Let *in*0[*i*] be the number of in-edges of node *i* whose color is 0. Similarly define *in*1[*i*], *out*0[*i*], *out*1[*i*]. Let 145 146  147 148 We can see that the answer is twice the number of triangles whose three edges are not all the same. So we can see the answer of the original problem is *n*3 - *p* / 2. 149 150 It's certain that *out*0[*i*] + *out*1[*i*] = *in*0[*i*] + *in*1[*i*] = *n*, so we only need to calculate out0 and in0. 151 152 Let us calculate *out*0 first. We can use the "Divide and Conquer on trees" algorithm to solve this in  time. Choose a root *i* and get its subtree, we can get all the values of the paths from a node in the subtree to node *i*. We save the values and the lengths of the paths. 153 154 For a path from node *j* with value *v* and length *l*, we want to find a node *k* which makes *G*(*S*(*j*, *k*)) ≡ *X* (*mod* *Y*). Let *H*(*i*, *j*) be the sequence of the value of nodes on (*i*, *j*) except node *i*, then 155 156 *G*(*S*(*j*, *k*)) = *G*(*S*(*j*, *i*)) + *G*(*H*(*i*, *k*))·*K**l* = *v* + *G*(*H*(*i*, *k*))·*K**l* 157 158 As (*v* + *G*(*H*(*i*, *k*))·*K**l*) ≡ *X* (*mod* *Y*), so *G*(*H*(*i*, *k*)) = (*X* - *v*) / *K**l*. As *Y* is a prime number, we can get (*x* - *v*) / *K**l* easily. Let *z* = (*x* - *v*) / *K**l*, then the problem becomes that we need to calculate how many paths from node *i* to a node in the subtree except node *i*, whose value is *z*, this can be done by doing binary search on a sorted array. So we can get *out*0, and *in*0 likewise. 159 160 With these two arrays we can calculate the answer. The total complexity is . 161 162 **Solution:** [6707988](/contest/434/submission/6707988 "Посылка 6707988 от zhonghaoxi"), [6712931](/contest/434/submission/6712931 "Посылка 6712931 от huzecong")