441.md (7020B)
1 Source: https://codeforces.com/blog/entry/12615 2 3 ## [441A - Valera and Antique Items](/contest/441/problem/A "Codeforces Round 252 (Div. 2)") 4 5 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit") 6 7 You need to implement what written in statement. You could act like that: let's calculate *q**i* — minimum item price from seller *i*. Then if *q**i* < *v*, we can make a deal with seller *i*, otherwise we can't. 8 9 Jury's solution: [6850474](/contest/441/submission/6850474 "Submission 6850474 by gridnevvvit") 10 11 ## [441B - Valera and Fruits](/contest/441/problem/B "Codeforces Round 252 (Div. 2)") 12 13 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit") 14 15 Let's start counting days from 1 to 3001. Let current day be *i*. Additionally, we'll have *cur* variable — number of fruit we didn't collect previous days. Suppose *now* fruit is ripen current day. If *now* + *cur* ≤ *v*, we need to add *now* + *cur* to answer and update *cur* value (*cur* = 0). Otherwise we add *v* to answer, but *cur* value need to be updated as follows. Let *tv* = *max*(*v* - *cur*, 0). Then *cur* = *now* - *tv*. In other words, we try to collect fruits that will not be collectable next day. 16 17 Additionally, problem could be solved with , but this is not required. 18 19 Jury's solution: [6850502](/contest/441/submission/6850502 "Submission 6850502 by gridnevvvit") 20 21 **Bonus**. Suppose fruit can be collected at days *a**i*, *a**i* + 1, ..., *a**i* + *T**i*, where *T**i* — some number for each tree. How to solve this task optimally? 22 23 Additionaly, for every day there will be its own *v* (maximum number of fruit collected). 24 25 ## [441C - Valera and Tubes](/contest/441/problem/C "Codeforces Round 252 (Div. 2)") 26 27 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit") 28 29 The solution is pretty simple. First we need to make such route that visits every cell exactly one time. It is not difficult: 30 31 1. Initially we stay in (1, 1) cell. Moving from left to right, we should reach (1, *m*) cell. 32 2. Move to the next line, in (2, *m*) cell. Moving from right to left, we should reach the most left sell of 2nd line, (2, 1). 33 3. Move to the next line. Repeat 1. and 2. while we have not all cells visited. 34 35  36 37 After that, we can easily find the solution: you can make first (*k* - 1) tubes length be 2, and the last *k* tube will consist from cells left. 38 39 Jury's solution: [6850508](/contest/441/submission/6850508 "Submission 6850508 by gridnevvvit") 40 41 ## [441D - Valera and Swaps](/contest/441/problem/D "Codeforces Round 252 (Div. 2)") 42 43 Problem author [danilka.pro](/profile/danilka.pro "Expert danilka.pro") 44 45 In this task you should represent permutation as graph with *n* vertexes, and from every vertex *i* exists exactly one edge to vertex *p*[*i*]. It's easy to understand that such graph consists of simple cycles only. 46 47 If we make swap (*i*, *j*), edges  and  will become edges  and  respectively. Then if *i* and *j* is in the same cycle, this cycle will break: 48 49  50 51 but if they are in different cycles, these cycles will merge into one: 52 53  54 55 this means that every swap operation increases number of cycles by one, or decreases it by one. 56 57 Assuming all above, to get permutation *q* from permutation *p*, we need to increase (or decrease) number of cycles in *p* to *n* - *m*. Let *c* — number of cycles in *p*. Then *k* always equals |(*n* - *m*) - *c*|. 58 59 For satisfying lexicographical minimality we will review three cases: 60 61 1) *n* - *m* < *c* 62 63 It's easy to understand, that in this case you must decrease cycles number by merging cycles one by one with cycle containing vertex 1. This way every swap has form (1, *v*), where *v* > 1. Because every cycle vertex is bigger than previous cycle vertex, this case can be solved with *O*(*n*). 64 65 2) *n* - *m* > *c* 66 67 In this case you should break cycle for every vertex, making swap with smallest possible vertex (it should be in this cycle too). This could be done if represent cycle by line . As soon as every cycle is broken with linear asymptotics, this case solution works with *O*(*n*2). 68 69 **Bonus**: this way of representing cycle lets us optimize solution to  asymptotics, you may think how. 70 71 3) *n* - *m* = *с* 72 73 Besause in this case *k* = 0, there is nothing need to be swapped. 74 75 It's highly recommended to inspect jury's solution: [6850515](/contest/441/submission/6850515 "Submission 6850515 by gridnevvvit") 76 77 ## [441E - Valera and Number](/contest/441/problem/E "Codeforces Round 252 (Div. 2)") 78 79 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit") 80 81 We will solve the task by calculating dynamic *d*[*i*][*mask*][*last*][*cnt*] — possibility of getting *v* which 8 last bits equals *mask*, 9th bit equals *last*, *cnt* — number of consecutive bits (following 9th bit) and equal to *last*, after *i* steps. 82 83 Good, but why we left other bits? It's clear, that using operation + = 1 we can change only first 0 bit with index ≥ 9. 84 85 Transitions is pretty obvious: we add 1 or multiply by 2 (it's recommended to see them in jury's solution). Perhaps, you should ask following question. For example, we have number *x* = 1011111111 in binary representation. 86 87 And at this moment, we make + = 1. According to all above, we must go to *d*[1][0][1][2] condition, but we can't do that because we don't have any information about 1 in 10th position. But, as we can not change any bit with index ≥ 9 (*mask* = 0) we make transition to *d*[1][0][1][1]. 88 89 Jury's solution: [6850523](/contest/441/submission/6850523 "Submission 6850523 by gridnevvvit") 90 91 **Bonus**. Let us have other pseudocode. 92 93 ``` 94 // input x, k, p 95 96 for(i = 0; i < k; i += 1) { 97 if (x is even) { 98 rnd = random number from interval [1, 100] 99 if (rnd <= p) 100 x *= 2; 101 else 102 x += 1; 103 } else { 104 x *= 2; 105 } 106 } 107 108 s = 0; 109 110 while (x is even) { 111 x /= 2; 112 s += 1; 113 } 114 ``` 115 116 As before, you must find expected value of *s*. 117 118 How effectively you can solve this problem? Can you prove your solution? 119 120 **Your corrections of my bad English are welcome, thank you.**