341.md (30884B)
1 Source: https://codeforces.com/blog/entry/8755 2 3 ## [340A - The Wall](/contest/340/problem/A "Codeforces Round 198 (Div. 2)") 4 5 You are given a range [*A*, *B*]. You're asked to compute fast how many numbers in the range are divisible by both *x* and *y*. I'll present here an *O*(*log*(*max*(*x*, *y*)) solution. We made tests low so other not optimal solutions to pass as well. The solution refers to the original problem, where *x*, *y* ≤ 109. 6 7 Firstly, we can simplify the problem. Suppose we can calculate how many numbers are divisible in range [1, *X*] by both *x* and *y*. Can this solve our task? The answer is yes. All numbers in range [1, *B*] divisible by both numbers should be counted, except the numbers lower than *A* (1, 2, ..., A — 1). But, as you can see, numbers lower than A divisible by both numbers are actually numbers from range [1, A — 1]. So the answer of our task is f(B) — f(A — 1), where f(X) is how many numbers from 1, 2, ..., X are divisible by both x and y. 8 9 For calculate in *O*(*log*(*max*(*x*, *y*)) the f(X) we need some math. If you don't know about it, please read firstly about least common multiple. Now, what will be the lowest number divisible by both x and y. The answer is least common multiple of x and y. Let's note it by *M*. The sequence of the numbers divisible by both x and y is *M*, 2 * *M*, 3 * *M* and so on. As a proof, suppose a number z is divisible by both x and y, but it is not in the above sequence. If a number is divisible by both x and y, it will be divisible by M also. If a number is divisible by M, it will be in the above sequence. Hence, the only way a number to be divisible by both x and y is to be in sequence *M*, 2 * *M*, 3 * *M*, ... 10 11 The f(X) calculation reduces to finding the number of numbers from sequence *M*, 2 * *M*, 3 * *M*, ... lower or equal than X. It's obvious that if a number h * M is greater than X, so will be (h + 1) * M, (h + 2) * M and so on. We actually need to find the greatest integer number h such as *h* * *M* ≤ *X*. The numbers we're looking for will be 1 * *M*, 2 * *M*, ..., *h* * *M* (so their count will be *h*). The number h is actually [X / M], where [number] denotes the integer part of [number]. Take some examples on paper, you'll see why it's true. 12 13 The only thing not discussed is how to calculate the number M given 2 number x and y. You can use this formula *M* = *x* * *y* / *gcd*(*x*, *y*). For calculate gcd(x, y) you can use Euclid's algorithm. Its complexity is *O*(*log*(*max*(*x*, *y*)), so this is the running time for the entire algorithm. 14 15 Official solution: [4383403](/contest/340/submission/4383403 "Submission 4383403 by fchirica") 16 17 ## [340B - Maximal Area Quadrilateral](/contest/340/problem/B "Codeforces Round 198 (Div. 2)") 18 19 I want to apologize for not estimating the real difficulty of this task. It turns out that it was more complicated than we thought it might be. Let's start explanation. 20 21 Before reading this, you need to know what is signed area of a triangle (also called cross product or ccw function). Without it, this explanation will make no sense. 22 23 The first thing we note is that a quadrilateral self intersecting won't have maximum area. I'll show you this by an image made by my "talents" in Paint :) As you can see, if a quadrilateral self intersects, it can be transformed into one with greater area. 24 25  26 27 Each quadrilateral has 2 diagonals: connecting 1st and 3rd point and connecting 2nd and 4th point. A diagonal divides a plane into 2 subplanes. Suppose diagonal is AB. A point X can be in one of those two subplanes: that making cross product positive and that making cross product negative. A point is in "positive" subplane if ccw(X, A, B) > 0 and in "negative" subplane ccw(X, A, B) < 0. Note that according to the constraints of the task, ccw(X, A, B) will never be 0. 28 29 Let's make now the key observation of the task. We have a quadrilateral. Suppose AB is one of diagonals and C and D the other points from quadrilateral different by A and B. If the current quadrilateral could have maximal area, then one of points from C and D needs to be in "positive subplane" of AB and the other one in "negative subplane". What would happen if C and D will be in the same subplane of AB? The quadrilateral will self intersect. If it will self intersect, it won't have maximal area. "A picture is worth a thousand words" — this couldn't fit better in this case :) Note that the quadrilateral from the below image is A-C-B-D-A. 30 31  32 33 Out task reduces to fix a diagonal (this taking O(N ^ 2) time) and then choose one point from the positive and the negative subplane of the diagonal. I'll say here how to choose the point from the positive subplane. That from negative subplane can be chosen identically. The diagonal and 3rd point chosen form a triangle. As we want quadrilateral to have maximal area, we need to choose 3rd point such as triangle makes the maximal area. As the positive and negative subplanes are disjoint, the choosing 3rd point from each of them can be made independently. Hence we get O(N ^ 3) complexity. A tricky case is when you choose a diagonal but one of the subplanes is empty. In this case you have to disregard the diagonal and move to the next one. 34 35 Official solution: [4383413](/contest/340/submission/4383413 "Submission 4383413 by fchirica") 36 37 ## [340C - Tourist Problem](/contest/340/problem/C "Codeforces Round 198 (Div. 2)") 38 39 Despite this is a math task, the only math formula we'll use is that number of permutations with *n* elements is *n*!. From this one, we can deduce the whole task. 40 41 The average formula is sum_of_all_routes / number_of_routes. As each route is a permutation with n elements, number_of_routes is *n*!. Next suppose you have a permutation of a: p1, p2, …, pn. The sum for it will be p1 + |p2 – p1| + … + |pn – pn-1|. The sum of routes will be the sum for each possible permutation. 42 43 We can calculate sum_of_all routes in two steps: first time we calculate sums like “p1” and then we calculate sums like “|p2 – p1| + … + |pn – pn-1|” for every existing permutation. 44 45 **First step** Each element of *a*1, *a*2, …, *a**n* can appear on the first position on the routes and needs to be added as much as it appears. Suppose I fixed an element X for the first position. I can fill positions 2, 3, .., n – 1 in (n – 1)! ways. Why? It is equivalent to permuting n – 1 elements (all elements except X). So sum_of_all = *a*1 * (n – 1)! + *a*2 * (n – 1)! + … * *a**n* * (n – 1)! = (n – 1)! * (*a*1 + *a*2 + … + *a**n*). 46 47 **Second step** For each permutation, for each position j between 1 and n – 1 we need to compute |*p**j* — *p*(*j* + 1)|. Similarly to first step, we observe that only elements from *a* can appear on consecutive positions. We fix 2 indices i and j. We’re interested in how many permutations do *a**i* appear before *a**j*. We fix k such as on a permutation p, *a**i* appears on position k and *a**j* appears on a position k + 1. In how many ways can we fix this? n – 1 ways (1, 2, …, n – 1). What’s left? A sequence of (n – 2) elements which can be permuted independently. So the sum of second step is |*a**i* - *a**j*| * (n – 1) * (n – 2)!, for each i != j. If I note (*a*1 + *a*2 + … + *a**n*) by S1 and |*a**i* - *a**j*| for each i != j by S2, the answer is (N – 1)! * S1 + (N – 1)! * S2 / N!. By a simplification, the answer is (S1 + S2) / N. 48 49 The only problem remained is how to calculate S2. Simple iteration won’t enter in time limit. Let’s think different. For each element, I need to make sum of differences between it and all smaller elements in the array a. As well, I need to make sum of all different between bigger elements than it and it. I’ll focus on the first part. I sort increasing array a. Suppose I’m at position *i*. I know that (i – 1) elements are smaller than *a**i*. The difference is simply (i — 1) * *a**i* — sum_of_elements_before_position_i. Sum of elements before position i can be computed when iterating i. Let’s call the obtained sum Sleft. I need to calculate now sum of all differences between an element and bigger elements than it. This sum is equal to Sleft. As a proof, for an element *a**i*, calculating the difference *a**j* — *a**i* when *a**j* > *a**i* is equivalent to calculating differences between *a**j* and a smaller element of it (in this case *a**i*). That’s why Sleft = Sright. 50 51 As a conclusion, the answer is (S1 + 2 * Sleft) / N. For make fraction irreducible, you can use Euclid's algorithm. The complexity of the presented algorithm is *O*(*N* * *logN*), necessary due of sorting. Sorting can be implemented by count sort as well, having a complexity of O(maximalValue), but this is not necessary. 52 53 Official solution: [4383420](/contest/340/submission/4383420 "Submission 4383420 by fchirica") 54 55 ## [340D - Bubble Sort Graph](/contest/340/problem/D "Codeforces Round 198 (Div. 2)") 56 57 A good way to approach this problem is to notice that you can't build the graph. In worst case, the graph will be built in *O*(*N*2) complexity, which will time out. Also, notice that "maximal independent set" is a NP-Hard task, so even if you can build the graph you can't continue from there. So, the correct route to start is to think of graph's properties instead of building it. After sketching a little on the paper, you should find this property: 58 59 **Lemma 1** Suppose we choose 2 indices i and j, such as i < j. We'll have an edge on the graph between vertices *a**i* and *a**j* if and only if *a**i* > *a**j*. We'll call that i and j form an inversion in the permutation. 60 61 **Proof** We assume we know the proof that bubble sort does sort correctly an array. To proof lemma 1, we need to show two things. 62 63 1. Every inversion will be swapped by bubble sort. 64 2. For each i < j when *a**i* < *a**j*, bubble sort will NOT swap this elements. 65 66 To proof 1, if bubble sort wouldn't swap an inversion, the sequence wouldn't be sorted. But we know that bubble sort always sorts a sequence, so all inversions will be swapped. Proofing 2 is trivial, just by looking at the code. 67 68 So far we've got how the graph G is constructed. Let's apply it in maximal independent set problem. 69 70 **Lemma 2** A maximal independent set of graph G is a longest increasing sequence for permutation a. 71 72 **Proof**: Suppose we have a set of indices *i*1 < *i*2 < ... *ik* such as *a**i*1, *a**i*2, ..., *a**ik* form an independent set. Then, anyhow we'd choose *d* and *e*, there won't exist an edge between *a**id* and *a**ie*. According to proof 1, this only happens when *a**id* < *a**ie*. Hence, an independent set will be equivalent to an increasing sequence of permutation a. The maximal independent set is simply the maximal increasing sequence of permutation a. 73 74 The task reduces to find longest increasing sequence for permutation *a*. This is a classical problem which can be solved in *O*(*N* * *logN*). [Here](//codeforces.com/blog/entry/8761) is an interesting discussion about how to do it. 75 76 ## [340E - Iahub and Permutations](/contest/340/problem/E "Codeforces Round 198 (Div. 2)") 77 78 In this task, author's intended solution is an O(N ^ 2) dp. However, during testing [Gerald](/profile/Gerald "Master Gerald") fount a solution using principle of inclusion and exclusion. We've thought to keep both solutions. We're sorry if you say the problem was well-known, but for both me and the author of the task, it was first time we saw it. 79 80 **Dynamic programming solution** 81 82 After reading the sequence, we can find which elements are deleted. Suppose we have in a set D all deleted elements. I'll define from now on a "free position" a position which has -1 value, so it needs to be completed with a deleted element. 83 84 We observe that some elements from D can appear on all free positions of permutation without creating a fixed point. The other elements from D can appear in all free positions except one, that will create the fixed point. It's intuitive that those two "classes" don't influence in the same way the result, so they need to be treated separated. 85 86 So from here we can get the dp state. Let dp(n, k) = in how many ways can I fill (n + k) free positions, such as n elements from D can be placed anywhere in the free position and the other k elements can be placed in all free positions except one, which will create the fixed point. As we'll prove by the recurrences, we are not interested of the values from elements of D. Instead, we'll interested in their property: if they can(not) appear in all free positions. 87 88 If k = 0, the problem becomes straight-forward. The answer for dp(n, 0) will be n!, as each permutation of (n + 0) = n numbers is valid, because all numbers can appear on all free positions. We can also calculate dp(n, 1). This means we are not allowed to place an element in a position out of (n + 1) free positions. However, we can place it in the other n positions. From now we get n elements which can be placed anywhere in the n free positions left. Hence, dp(n, 1) = n! * n. 89 90 We want to calculate dp(n, k) now, k > 1. Our goal is to reduce the number k, until find something we know how to calculate. That is, when k becomes 0 or 1 problem is solved. Otherwise, we want to reduce the problem to a problem when k becomes 0 or 1. I have two cases. In a first case, I take a number from numbers which can be placed anywhere in order to reduce the numbers which can form fixed points. In the second case, I take a number from those which can form fixed points in order to make the same goal as in the first case. Let's analyze them. 91 92 Case 1. Suppose X is the first free position, such as in the set of k numbers there exist one which cannot be placed there (because it will make a fixed point). Obviously, this position exist, otherwise k = 0. Also obviously, this position will need to be completed with a term when having a solution. In this case, I complete position X with one of n numbers. This will make number equal to X from the k numbers set to become a number which can be placed anywhere. So I "loose" one number which can be placed anywhere, but I also "gain" one. As well, I loose one number which can form a fixed point. 93 94 Hence dp(n, k) += n * dp(n, k — 1). 95 96 Case 2. In this case position X will be completed with one number from the k numbers set. All numbers which can form fixed points can appear there, except number having value equal to X. So there are k — 1 of them. I choose an arbitrary number Y from those k — 1 to place on the position X. This time I "loose" two numbers which could form fixed points: X and Y. As well, I "gain" one number which can be placed anywhere: X. 97 98 Hence dp(n, k) += (k — 1) * dp(n + 1, k — 2). 99 100 **TL;DR** 101 102 dp[N][0]=N! 103 104 dp[N][1]=N*dp[N][0] 105 106 dp[N][K]=N*dp[N][K-1]+(K-1)*dp[N+1][K-2] for K>=2 107 108 This recurrences can be computed by classical dp or by memoization. I'll present [DamianS](/profile/DamianS "Grandmaster DamianS")'s source, which used memoization. As you can see, it's very short and easy to implement. [Link](http://pastie.org/8286348) 109 110 **Inclusion and exclusion principle** 111 112 I'll present here an alternative to the dynamic programming solution. Let's calculate in *tot* the number of deleted numbers. Also, let's calculate in *fixed* the **maximal number of fixed points a permutation can have**. For calculate *fixed*, let's iterate with an index *i* each permutation position. We can have a fixed point on position *i* if element from position *i* was deleted (*a**i* = -1) and element i does not exist in sequence *a*. With other words, element *i* was deleted and now I want to add it back on position *i* to obtain maximal number of fixed points. 113 114 We iterate now an index *i* from *fixed* to 0. Let sol[i] = the number of possible permutations having *exactly* *i* fixed points. Obviously, sol[0] is the answer to our problem. Let's introduce a [combination](https://en.wikipedia.org/wiki/Combination)  representing in how many ways I can choose k objects out of n. I have list of positions which can be transformed into fix points (they are *fixed* positions). I need to choose *i* of them. According to the above definition, I get sol[i] =  . Next, I have to fill *tot* - *i* positions with remained elements. We'll consider for this moment valid each permutation of not used values. So, sol[i] =  . Where is the problem to this formula? 115 116 The problem is that it's possible, when permuting (tot — i) remained elements to be added, one (or more) elements to form more (new) fixed points. But if somehow I can exclude (subtract) the wrong choices from sol[i], sol[i] will be calculated correctly. I iterate another index *j* from i + 1 to *fixed*. For each j, I'll calculate how many permutations I considered in sol[i] having *i* fixed points but actually they have *j*. I'll subtract from sol[i] this value calculated for each j. If I do this, obviously sol[i] will be calculated correctly. 117 118 Suppose we fixed a j. We know that exactly sol[j] permutations have j fixed points (as j > i, this value is calculated correctly). Suppose now I fix a permutation having j fixed points. For get the full result, I need to calculate for all sol[j] permutations. Happily, I can multiply result obtained for a single permutation with sol[j] and obtain the result for all permutations having j fixed points. So you have a permutation having j fixed points. The problem reduces to choosing i objects from a total of j. Why? Those i objects chosen are actually the positions considered in sol[i] to be ones having exactly i fixed points. But permutation has j fixed points. Quoting for above, "For each j, I'll calculate how many permutations I considered in sol[i] having *i* fixed points but actually they have *j*" . This is exactly what algorithm does. 119 120 To sum up in a "LaTeX" way,  121 122 We can compute binomial coefficients using Pascal's triangle. Using inclusion and exclusion principle, we get *O*(*N*2). Please note that there exist an *O*(*N*) solution for this task, using inclusion and exclusion principle, but it's not necessary to get AC. I'll upload [Gerald](/profile/Gerald "Master Gerald")'s source [here](http://pastie.org/8287332). 123 124 ## [341D - Iahub and Xors](/contest/341/problem/D "Codeforces Round 198 (Div. 1)") 125 126 The motivation of the problem is that x ^ x = 0. x ^ x ^ x… ^ x (even times) = 0 127 128 **Update per range, query per element** 129 130 When dealing with complicated problems, it's sometimes a good idea to try solving easier versions of them. Suppose you can query only one element each time (x0 = x1, y0 = y1). 131 132 To update a submatrix (x0, y0, x1, y1), I’ll do following operations. A[x0][y0] ^= val. A[x0][y1 + 1] ^= val. A[x1 + 1][y0] ^= val. A[x1 + 1][y1 + 1] ^= val. 133 134 To query about an element (X, Y), that element’s value will be the xor sum of submatrix A(1, 1, X, Y). Let’s take an example. I have a 6x6 matrix and I want to xor all elements from submatrix (2, 2, 3, 4) with a value. The below image should be explanatory how the method works: 135 136  137 138 Next, by (1, 1, X, Y) I’ll denote xor sum for this submatrix. 139 140 “White” cells are not influenced by (2, 2, 3, 4) matrix, as matrix (1, 1, X, Y) with (X, Y) a white cell will never intersect it. “Red” cells are from the submatrix, the ones that need to be xor-ed. Note that for a red cell, (1, 1, X, Y) will contain the value we need to xor (as it will contain (2, 2)). Next, “blue” cells. For this ones (1, 1, X, Y) will contain the value we xor with, despite they shouldn’t have it. This is why both (2, 5) and (4, 2) will be xor-ed again by that value, to cancel the xor of (2, 2). Now it’s okay, every “blue” cell do not contain the xor value in their (1, 1, X, Y). Finally, the “green” cells. These ones are intersection between the 2 blue rectangles. This means, in their (1, 1, X, Y) the value we xor with appears 3 times (this means it is contained 1 time). For cancel this, we xor (4, 5) with the value. Now for every green cell (1, 1, X, Y) contains 4 equal values, which cancel each other. 141 142 You need a data structure do to the following 2 operations: 143 144 * Update an element (X, Y) (xor it with a value). 145 * Query about xor sum of (1, 1, X, Y). 146 147 Both operations can be supported by a Fenwick tree 2D. If you don't know this data structure, learn it and come back to this problem after you do this. 148 149 **Coming back to our problem** 150 151 Now, instead of finding an element, I want xor sum of a submatrix. You can note that xor sum of (x0, y0, x1, y1) is (1, 1, x1, y1) ^ (1, 1, x0 – 1, y1) ^ (1, 1, x1, y0 – 1) ^ (1, 1, x0 – 1, y0 – 1). This is a classical problem, the answer is (1, 1, x1, y1) from which I exclude what is not in the matrix: (1, 1, x0 – 1, y1) and (1, 1, x1, y0 – 1). Right now I excluded (1, 1, x0 – 1, y0 – 1) 2 times, so I need to add it one more time. 152 153 How to get the xor sum of submatrix (1, 1, X, Y)? In brute force approach, I’d take all elements (x, y) with 1 <= x <= X and 1 <= y <= Y and xor their values. Recall the definition of the previous problem, each element (x, y) is the xor sum of A(1, 1, x, y). So the answer is xor sum of all xor sums of A(1, 1, x, y), with 1 <= x <= X and 1 <= y <= Y. 154 155 We can rewrite that long xor sum. A number A[x][y] appears in exactly (X – x + 1) * (Y – y + 1) terms of xor sum. If (X – x + 1) * (Y – y + 1) is odd, then the value A[x][y] should be xor-ed to the final result exactly once. If (X — x + 1) * (Y — y + 1) is even, it should be ignored. 156 157 Below, you'll find 4 pictures. They are matrixes with X lines and Y columns. Each picture represents a case: (X odd, Y odd) (X even, Y even) (X even Y odd) (X odd Y even). Can you observe a nice pattern? Elements colored represent those for which (X – x + 1) * (Y – y + 1) is odd. 158 159     160 161 Yep, that's right! There are 4 cases, diving the matrix into 4 disjoint areas. When having a query of form (1, 1, X, Y) you only need specific elements sharing same parity with X and Y. This method works in O(4 * logN * logN) for each operation and is the indented solution. We keep 4 Fenwick trees 2D. We made tests such as solutions having complexity greater than O(4 * logN * logN) per operation to fail. 162 163 Here is our official solution: [4383473](/contest/341/submission/4383473 "Submission 4383473 by fchirica") 164 165 ## [341E - Candies Game](/contest/341/problem/E "Codeforces Round 198 (Div. 1)") 166 167 **Key observation** Suppose you have 3 boxes containing A, B, C candies (A, B, C all greater than 0). Then, there will be always possible to empty one of boxes using some moves. 168 169 **Proof** We can suppose that A <= B <= C. We need some moves such as the minimum from A, B, C will be zero. If we always keep the numbers in order A <= B <= C, it’s enough some moves such as A = 0. I’ll call this notation (A, B, C). 170 171 How can we prove that always exist such moves? We can use reductio ad absurdum to prove it. Let’s suppose, starting from (A, B, C) we can go to a state (A2, B2, C2). We suppose A2 (A2 > 0) is minimal from every state we can obtain. Since A2 is minimal number of coins that can be obtained and A2 is not zero, the statement is equivalent with we can’t empty one chest from configuration (A, B, C). Then, we can prove that from (A2, B2, C2) we can go to a state (A3, B3, C3), where A3 < A2. Obviously, this contradicts our assumption that A2 is minimal of every possible states. If A2 would be minimal, then there won’t be any series of moves to empty one chest. But A2 isn’t minimal, hence there always exist some moves to empty one chest. 172 173 Our algorithm so far: 174 175 void emptyOneBox(int A, int B, int C) { 176 177 if A is 0, then exit function. 178 179 Make some moves such as to find another state (A2, B2, C2) with A2 < A. 180 181 emptyOneBox (A2, B2, C2); 182 183 } 184 185 The only problem which needs to be proven now is: given a configuration (A, B, C) with A > 0, can we find another one (A2, B2, C2) such as A2 < A? The answer is always yes, below I’ll prove why. 186 187 Firstly, let’s imagine we want to constantly move candies into a box. It doesn't matter yet from where come the candies, what matters is candies arrive into the box. The box has initially X candies. After 1 move, it will have 2 * X candies. After 2 moves, it will have 2 * (2 * X) candies = 4 * X candies. Generally, after K moves, the box will contain 2^K * X candies. 188 189 We have A < B < C (if 2 numbers are equal, we can make a move and empty 1 box). If we divide B by A, we get from math that B = A * q + r. (obviously, always r < A). What if we can move exactly A * q candies from B to A? Then, our new state would be (r, B2, C2). We have now a number A2 = r, such as A2 < A. 190 191 How can we move exactly A * q coins? Let’s write q in base 2. Making that, q will be written as a sum of powers of 2. Suppose lim is the maximum number such as 2 ^ lim <= q. We get every number k from 0 to lim. For each k, I push into the first box (the box containing initially A candies) a certain number of candies. As proven before, I'll need to push (2 ^ k) * A candies. Let's take a look at the k-th bit from binary representation of q. If k-th bit is 1, B will be written as following: B = A * (2 ^ k + 2 ^ (other_power_1) + 2 ^ (other_power_2) + ...) + r. Hence, I'll be able to move A * (2 ^ k) candies from "B box" to "A box". Otherwise, I'll move from "C box" to "A box". It will be always possible to do this move, as C > B and I could do that move from B, too. 192 193 The proposed algorithm may look abstract, so let's take an example. 194 195 Suppose A = 3, B = 905 and C = 1024. Can we get less than 3 for this state? 196 197 B = 3 * 301 + 2. B = 3 * (100101101)2 + 2. 198 199 K = 0: we need to move (2^0) * 3 coins into A. 0th bit of q is 1, so we can move from B to A. 200 201 A = 6, B = 3 * (100101100)2 + 2 C = 1024 202 203 K = 1: we need to move (2 ^ 1) * 3 coins into A. Since 1th bit of q is already 0, we have to move from C. 204 205 A = 12, B = 3 * (100101100)2 + 2 C = 1018 206 207 K = 2: we need to move (2 ^ 2) * 3 coins into A. 2nd bit of q is 1, so we can move from B. 208 209 A = 24, B = 3 * (100101000)2 + 2 C = 1018 210 211 K = 3: we need to move (2 ^ 3) * 3 coins into A. 3nd bit of q is 1, so we can move from B. 212 213 A = 48, B = 3 * (100100000)2 + 2 C = 1018 214 215 K = 4. we need to move (2 ^ 4) * 3 coins into A. 4th bit of q is 0, we need to move from C. 216 217 A = 96, B = 3 * (100100000)2 + 2 C = 970 218 219 K = 5. we need to move (2 ^ 5) * 3 coins into A. 5th bit of q is 1, so we need to move from B. 220 221 A = 192, B = 3 * (100000000)2 + 2 C = 970 222 223 K = 6 we need to move (2 ^ 6) * 3 coins into A. We mve them from C. 224 225 A = 384 B = 3 * (100000000)2 + 2 C = 778 226 227 K = 7 we need to move (2 ^ 7) * 3 coins into A. We move them from C 228 229 A = 768 B = 3 * (100000000)2 + 2 C = 394 230 231 K=8 Finally, we can move our last 1 bit from B to A. 232 233 A = 1536 B = 3 * (000000000)2 + 2 C = 394 234 235 A = 1536 B = (3 * 0 + 2) C = 394 236 237 In the example, from (3, 905, 1024) we can arrive to (2, 394, 1536). Then, with same logic, we can go from (2, 394, 1536) to (0, X, Y), because 394 = 2 * 197 + 0. 238 239 This is how you could write emptyOneBox() procedure. The remained problem is straight-forward: if initially there are zero or one boxes having candies, the answer is "-1". Otherwise, until there are more than 2 boxes having candies, pick 3 boxes arbitrary and apply emptyOneBox(). 240 241 Here is a source implementing the algorithm. [4383485](/contest/341/submission/4383485 "Submission 4383485 by fchirica") 242 243 ## BONUS 244 245 Instead of a conclusion, I'll post here related problems to the ones used in the round. :) Please note that some of them might be more easier / complicated than level of difficulty used in the round. Feel free to think of them / ask help / discuss them in the comment section :) 246 247 **Div2 A** Suppose *x*, *y*, *A*, *B* ≤ 109. Instead of being asked how many bricks are colored with both red and pink in range [*A*, *B*], you're asked how many bricks are colored with at least one color. After you solve this one, solve the same problem, but instead of having 2 persons painting, you have k persons (*k* ≤ 20). [Solution](//codeforces.com/blog/entry/8755#comment-144971) by [Enchom](/profile/Enchom "Candidate Master Enchom") 248 249 **Div2 B** Given a very long list of special points, can you find quickly a convex special quadrilateral? Can you find very very quickly? :) Also, can you find maximal area of a special convex quadrilateral in time better than *O*(*N*4)? Solutions for [first problem](//codeforces.com/blog/entry/8755#comment-145790) and [second problem](//codeforces.com/blog/entry/8755#comment-145492) provided by [Xellos](/profile/Xellos "Candidate Master Xellos") and [Enchom](/profile/Enchom "Candidate Master Enchom") 250 251 **Div2 D / Div1 B** Suppose the reverse problem. You are given a bubble sort graph having *N* vertices and *M* edges. Find its independent maximal set. Can you achieve *O*(*N*2) to do this? Does a solution in *O*((*N* + *M*) + *N* * *logN*) exist? [Solution](//codeforces.com/blog/entry/8755#comment-144890) by [CountZero](/profile/CountZero "Expert CountZero") 252 253 **Div2 E / Div1 C** Find a solution running in liniar time. [Solution (dynamic programming)](//codeforces.com/blog/entry/8755#comment-144888) by [ivan100sic](/profile/ivan100sic "Candidate Master ivan100sic") . [Solution (inclusion exclusion principle)](//codeforces.com/blog/entry/8748#comment-144745) by [eduardische](/profile/eduardische "Candidate Master eduardische") 254 255 **Div1 D** Suppose the 3D version of this problem. You have a 3D matrix and you perform same QUERY/UPDATE operations, but using 6 parameters (a submatrix is defined now all elements a[i][j][k] for which x0 <= i <= x1, y0 <= j <= y1, z0 <= k <= z1). Can you get a solution using *O*(*log*3 * *N*) per query, having constant 8? But for d dimensions, does an *O*(2*d* * (*log**d*)*n*) algorithm per query exist? :) [Solution](//codeforces.com/blog/entry/8755#comment-144896) by [Dwylkz](/profile/Dwylkz "Expert Dwylkz"). 256 257 **Div1 E** In our algorithm, we pick arbitrary 3 boxes. Can you find some heuristics of picking 3 boxes to reduce number of moves?