355.md (12115B)
1 Source: https://codeforces.com/blog/entry/8672 2 3 [355A - Vasya and Digital Root](/contest/355/problem/A "Codeforces Round 206 (Div. 2)") 4 5 If *d* = 0, the there is the only number with , so, if *k* = 1, the answer is 0, otherwise — *No* *solution*. 6 7 If *d* > 0, then one of correct numbers is *d* × 10*k* - 1. 8 9 Time complexity: *O*(1) + *O*(*k*) for the output. 10 11 [355B - Vasya and Public Transport](/contest/355/problem/B "Codeforces Round 206 (Div. 2)") 12 13 If we buy a ticket of the fourth type, we don't have to buy anything else, so, the answer is *min*(*c*4, *answer* *using* *tickets* *of* *first* *three* *types*). 14 15 Now, when we don't have ticket of the fourth type, we can solve the task separately for buses and trolleys. 16 17 Solving the problem only for buses: if we buy a ticket of the third type, we don't have to buy anything else, so, the answer is *min*(*c*3, *answer* *using* *tickets* *of* *first* *two* *types*). 18 19 Without tickets of type three, we can solve the problem separately for each bus. If we buy a ticket of the second type, we will spend *c*2 burles and if we buy *a**i* tickets of the first type, we will spend (*a**i* × *c*1) burles. So, the answer for bus *i* is *min*(*c*2, *a**i* × *c*1). 20 21 Now it is not difficult to obtain the following solution: 22 23 ``` 24 function f(x, k) { 25 res = 0; 26 for i = 1 .. k 27 res = res + min(c2, x[i] * c1); 28 29 return min(c3, res); 30 } 31 32 ans = min(c4, f(a, n) + f(b, m)); 33 ``` 34 35 Time complexity: *O*(*n* + *m*). 36 37 [354A - Vasya and Robot](/contest/354/problem/A "Codeforces Round 206 (Div. 1)") 38 39 Brute force how many times we will use operation from the left. So, if we use it *k* times, then it's clear, that we will take first *k* items by the left operations and last (*n* - *k*) items by the right operations. So, robot will spend *sumLeft*[*k*]·*l* + *sumRight*[*n* - *k*]·*r* energy plus some penalty for the same operations. To minimize this penalty we should perform the operations in the following order LRLRL ... RLRLLLLL ..., starting from the bigger set. For example, if *k* = 7, *n* - *k* = 4, we should perform operations in this order: LRLRLRLRL **LL**. So, we will have to pay the penalty two times (7 - 4 - 1). 40 41 *sumLeft*[*i*] — sum of first *i* weights, *sumRight*[*i*] — sum of last *i* weights. 42 43 Solution in pseudocode: 44 45 ``` 46 ans = inf; 47 for i = 0 .. n { 48 curr = firstSum[i] * l + lastSum[n-i] * r; 49 if ( i > n - i ) curr = curr + (2i - n - 1) * Ql; 50 if ( i < n - i ) curr = curr + (n - 2i - 1) * Qr; 51 52 ans = min(ans, curr); 53 } 54 ``` 55 56 Time complexity: *O*(*n*). 57 58 [354B - Game with Strings](/contest/354/problem/B "Codeforces Round 206 (Div. 1)") 59 60 We will say that cell (*r*, *c*) corresponds to a string *s*, if there exist correct path, which ends in the cell (*r*, *c*) and this path corresponds to a string *s*. 61 62 Let call a set of cells which corresponds to some string *s* a state. One state can correspond to different strings. We can't brute force all possible strings, because their count —  is too big, but we can brute force all possible states. It's not hard to observe that all cells that corresponds to some string *s* lies on same diagonal, so the total count of states is 21 + 22 + ... + 2*n* - 1 + 2*n* + 2*n* - 1 + ... + 22 + 21 = *O*(2*n*). In implementation we can denote state with diagonal number (from 1 to 2*n* - 1) and bitmask of cells corresponding to this state (2*n*). 63 64 From each state we can move to 26 different states (actually less) and all possible moves depends on the state, not on the string. On the image you can see an example of move: from state, which is highlighted in blue by letter *a* we will move to the state, which is highlighted in yellow. 65 66  67 68 Now, for each state we can calculate a value of (count of letters A - count of letters B) in the string, starting from this state. If at the moment is first players turn (an even diagonal), we have to maximize this value, otherwise — minimize. It can be implemented as recursion with memoization. 69 70 The winner can be determined by the value of state, which corresponds to the single cell (1, 1). 71 72 Complexity: *O*(2*n* × (*n* + *alpha*)), where *alpha* is the size of alphabet. 73 74 [354C - Vasya and Beautiful Arrays](/contest/354/problem/C "Codeforces Round 206 (Div. 1)") 75 76 The problem was to find greatest *d*, such that *a**i* ≥ *d*, *a**i* *mod* *d* ≤ *k* holds for each *i*. 77 78 Let *m* = *min*(*a**i*), then *d* ≤ *m*. Let consider two cases: 79 80  81 82 . In this case we will brute force answer from *k* + 1 to *m*. We can check, if number *d* is a correct answer in the following way: 83 84 We have to check that *a**i* *mod* *d* ≤ *k* for some fixed *d*, which is equals to , where . Since all these intervals [*x*·*d*..*x*·*d* + *k*] doesn't intersects each with other, we can just check that , where *cnt*[*l*..*r*] — count of numbers *a**i* in the interval [*l*..*r*]. 85 86 Time complexity: *O*(*maxA* *log* *maxA*), proof is based on the sum of [harmonic series](https://ru.wikipedia.org/wiki/%D0%93%D0%B0%D1%80%D0%BC%D0%BE%D0%BD%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%80%D1%8F%D0%B4). 87 88 [354D - Transferring Pyramid](/contest/354/problem/D "Codeforces Round 206 (Div. 1)") 89 90  91 92 This tasks is solvable with dynamic programming. First of all let consider solution with complexity *O*(*n*3). 93 94 Let *dp*[*i*][*j*] be the answer for the highlighted in blue part (minimal cost of transferring all special cells that lies inside this area). Then *dp*[*n*][0] will be the answer for our original problem. 95 96 How to recalculate such DP? It's clear that in the leftmost column (inside the blue area) we will choose at most one cell as the top of some subpyramid. If we choose two, then the smallest one will lie fully inside the biggest one (as the orange subpyramid lies inside the blue one). Now, let brute force the cell, which will be the top of subpyramid in this column in time *O*(*n*) and we will obtain the following transition: 97 98 To simplify the formulas, let assume that . 99 100   0 ≤ *k* ≤ *i*, where *k* is the height on which we will choose our top cell, or 0, if we don't choose any subpyramid in this column. *sumUp*[*i*][*p*] — count of special cells in the *i*-th column at height starting from *p*, this cells we will have to transfer one by one, using the first type operations. 101 102 We can reduce the complexity by one *n*, if we will recalculate out DP in the following way: 103 104  0 ≤ *k* ≤ *i*; 105 106  for all *j* > 0. 107 108 The proof that this is correct is quite simple and is left to the reader. :) 109 110 Also, we can observe that it is not profitably to take some subpyramid with height greater than , because for such subpyramid we will pay > 3*k*, but if we transfer all cells using the first type operations we will pay only 3*k*. So, the second dimension (*j*) in out DP can be reduced to . 111 112 Also, to receive AC, you should store only last 2 layers of the DP, otherwise there will be not enough memory. 113 114 Time complexity: . 115 116 [354E - Lucky Number Representation](/contest/354/problem/E "Codeforces Round 206 (Div. 1)") 117 118 Author's solution, much more complicated than suggested by many participants during the competition, easy solution will be described below. 119 120 First of all, let write a DP with complexity *O*(*N* * *lucky*_*count*(*N*)), where *lucky*_*count*(*N*) is the count of lucky numbers ≤ *N*, *lucky*_*count*(10*n*) = 3*n*. As we can see, for all sufficiently large *N* solution exists. Really — for every *N* > 523. 121 122 Now, we can say that for *N* ≤ 10000 we have a solution, which is found using DP. Let's solve the task for larger values of *N*. 123 124 Next and key idea is to separate the task into two parts: *N* = *N*1 + *N*2. Let's choose *N*1 and *N*2 in such way that for them it was easy to find a solution and then merge these two solutions into one. Let *N*1 = *N* *mod* 4000, *N*2 = *N* - *N*1. Here we can have a problem that there is no solution for number *N*1, in this case we can do *N*1 = *N*1 + 4000, *N*2 = *N*2 - 4000. 125 126 Now it is guaranteed that solutions exists for both *N*1 and *N*2, moreover, the solution for number *N*1 will contain only numbers of not more than 3 digits ( < 1000). The proof is quite easy: if *N*1 < 4000 — it is obvious; else — if the solution uses some number of the form (4000 + *some*_*lucky*_*number*), we can replace it with just *some*_*lucky*_*number* and receive a correct solution for number (*N*1 - 4000), but is doesn't exist! 127 128 So, the solution for number *N*1 we have found using DP, now let's find the solution for *N*2. If it will contains only of numbers of the form (*some*_*lucky*_*number* × 1000), then we will be able to easily merge this solution with solution for *N*1, so, let's find such a solution. Here we will use the fact that *N*2 is divisible by 4. For simplicity, let's divide *N*2 by 1000 and in the end multiply all *Ans*2(*i*) by the same 1000. Let *P* = *N*2 / 4. Now, let's construct the solution. Consider, for example, P = 95: we will walk through digits of this number, last digit — 5, means that we want to put digit 4 at the last decimal position of five answer numbers — ok, put it and in the last, sixth, number leave there digit 0. Go forward, digit 9 — we don't have nine numbers, but we can replace seven fours with four sevens, then to the second position we have to put (9 - 7) fours and 4 sevens, in total — 6 numbers, exactly as much as we have. 129 130 Thus, if next digit *d* ≤ 6, we just put to the first *d* answer numbers digit 4 to the next position; if *d* > 6, then we put 4 sevens and (*d* - 7) fours. In all other numbers we just leave digit 0 at this position. 131 132 If *Ans*1(*i*) — answer for *N*1, *Ans*2(*i*) — for *N*2, the the answer for *N* will be just *Ans*(*i*) = *Ans*1(*i*) + *Ans*2(*i*). 133 134 Time complexity for one number: *O*(*logN*). 135 136 During the competition many participants have wrote the following solution: 137 138 *dp*[*i*][*j*] — can we put the digit to the last *i* decimal positions of the answer number in such way that we will get correct last *i* digits in the sum and with carry to the next position equals to *j*. Then the solution exist iff *dp*[19][0] = *true*. To restore the answer we just have to remember for each state the previous state. Base — *dp*[0][0] = *true*. Transition — brute force how many fours and sevens we will put to the *i*-th position.