643.md (13966B)
1 Source: https://codeforces.com/blog/entry/44754 2 3 Editorial was created by [Errichto](/profile/Errichto "International Grandmaster Errichto"), but he said that he has enough contribution, so I'm posting it for you. ;) 4 5 # 1 [673A - Bear and Game](/contest/673/problem/A "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 2 Edition)") 6 7 (invented by [GlebsHP](/profile/GlebsHP "Grandmaster GlebsHP") — thanks!) 8 9 You are supposed to implement what is described in the statement. When you read numbers *t**i*, check if two consecutive numbers differ by more than 15 (i.e. *t**i* - *t**i* - 1 > 15). If yes then you should print *t**i* - 1 + 15. You can assume that *t*0 = 0 and then you don't have to care about some corner case at the beginning. Also, you can assume that *t**n* + 1 = 91 or *t**n* + 1 = 90 (both should work — do you see why?). If your program haven't found two consecutive numbers different by more than 15 then print 90. If you still have problems to solve this problem then check codes of other participants. 10 11 [18286606](/contest/673/submission/18286606 "Submission 18286606 by Radewoosh") 12 13 # 2 [673B - Problems for Round](/contest/673/problem/B "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 2 Edition)") 14 15 (invented by [Errichto](/profile/Errichto "International Grandmaster Errichto")) 16 17 Some prefix of problems must belong to one division, and the remaining suffix must belong to the other division. Thus, we can say that we should choose the place (between two numbers) where we split problems. Each pair *a**i*, *b**i* (let's say that *a**i* < *b**i*) means that the splitting place must be between *a**i* and *b**i*. In other words, it must be on the right from *a**i* and on the left from *b**i*. 18 19 For each pair if *a**i* > *b**i* then we swap these two numbers. Now, the splitting place must be on the right from *a*1, *a*2, ..., *a**m*, so it must be on the right from *A* = *max*(*a*1, *a*2, ..., *a**m*). In linear time you can calculate *A*, and similarly calculate *B* = *min*(*b*1, ..., *b**m*). Then, the answer is *B* - *A*. It may turn out that *A* > *B* though but we don't want to print a negative answer. So, we should print *max*(0, *B* - *A*). 20 21 [18286633](/contest/673/submission/18286633 "Submission 18286633 by Radewoosh") 22 23 # 3 [673C - Bear and Colors](/contest/673/problem/C "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 2 Edition)") 24 25 (invented by [Errichto](/profile/Errichto "International Grandmaster Errichto")) 26 27 We are going to iterate over all intervals. Let's first fix the left end of the interval and denote it by *i*. Now, we iterate over the right end *j*. When we go from *j* to *j* + 1 then we get one extra ball with color *c**j* + 1. In one global array *cnt*[*n*] we can keep the number of occurrences of each color (we can clear the array for each new *i*). We should increase by one *cnt*[*c**j* + 1] and then check whether *c**j* + 1 becomes a new dominant color. But how to do it? 28 29 Additionally, let's keep one variable *best* with the current dominant color. When we go to *j* + 1 then we should whether *cnt*[*c**j* + 1] > *cnt*[*best*] or (*cnt*[*c**j* + 1] = = *cnt*[*best*] and *c**j* + 1 < *best*). The second condition checks which color has smaller index (in case of a tie). And we must increase *answer*[*best*] by one then because we know that *best* is dominant for the current interval. At the end, print values *answer*[1], *answer*[2], ..., *answer*[*n*]. 30 31 [18286663](/contest/643/submission/18286663 "Submission 18286663 by Radewoosh") 32 33 # 4 [673D - Bear and Two Paths](/contest/673/problem/D "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 2 Edition)") 34 35 (invented by [Errichto](/profile/Errichto "International Grandmaster Errichto")) 36 37 There is no solution if *n* = 4 or *k* ≤ *n*. But for *n* ≥ 5 and *k* ≥ *n* + 1 you can construct the following graph: 38 39  40 41 Here, cities (*x*1, *x*2, ..., *x**n* - 4) denote other cities in any order you choose (cities different than *a*, *b*, *c*, *d*). You should print (*a*, *c*, *x*1, *x*2, ..., *x**n* - 4, *d*, *b*) in the first line, and (*c*, *a*, *x*1, *x*2, ..., *x**n* - 4, *b*, *d*) in the second line. 42 43 Two not very hard challenges for you. Are you able to prove that the answer doesn't exist for *k* = *n*? Can you solve the problem if the four given cities don't have to be distinct but it's guaranteed that *a* ≠ *b* and *c* ≠ *d*? 44 45 [18286683](/contest/643/submission/18286683 "Submission 18286683 by Radewoosh") 46 47 # 5 [673E - Levels and Regions](/contest/673/problem/E "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 2 Edition)") 48 49 (invented by [Radewoosh](/profile/Radewoosh "International Grandmaster Radewoosh")) 50 51 When we repeat something and each time we have probability *p* to succeed then the expected number or tries is , till we succeed. How to calculate the expected time for one region [*low*, *high*]? For each *i* in some moment we will try to beat this level and then there will be *S* = *t**low* + *t**low* + 1 + ... + *t**i* tokens in the bag, including *t**i* tokens allowing us to beat this new level. The probability to succeed is , so the expected time is . So, in total we should sum up values  for *i* < *j*. Ok, we managed to understand the actual problem. You can now stop and try to find a slow solution in *O*(*n*2·*k*). Hint: use the dynamic programming. 52 53 * Let *dp*[*i*][*j*] denote the optimal result for prefix of *i* levels, if we divide them into *j* regions. 54 * Let *pre*[*i*] denote the result for region containing levels 1, 2, ..., *i* (think how to calculate it easily with one loop). 55 * Let *sum*[*i*] denote the sum of *t**j* for all 1 ≤ *j* ≤ *i*. 56 * Let *rev*[*i*] denote the sum of  for all 1 ≤ *j* ≤ *i*. 57 58 Now let's write formula for *dp*[*i*][*j*], as the minimum over *l* denoting the end of the previous region: 59 60    61 62 So we can use convex hull trick to calculate it in *O*(*n*·*k*). You should also get AC with a bit slower divide&conquer trick, if it's implemented carefully. 63 64 [18286696](/contest/643/submission/18286696 "Submission 18286696 by Radewoosh") 65 66 # 6 [673F - Bearish Fanpages](/contest/673/problem/F "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 2 Edition)") 67 68 (invented by [Radewoosh](/profile/Radewoosh "International Grandmaster Radewoosh")) 69 70 Let's say that every company has one parent (a company it follows). Also, every copmany has some (maybe empty) set of children. It's crucial that sets of children are disjoint. 71 72 For each company let's keep (and always update) one value, equal to the sum of: 73 74 * the income from its own fanpage 75 * the income from its children's fanpages 76 77 It turns out that after each query only the above sum changes only for a few values. If *a* starts to follows *b* then you should care about *a*, *b*, *par*[*a*], *par*[*b*], *par*[*par*[*a*]]. And maybe *par*[*par*[*b*]] and *par*[*par*[*par*[*a*]]] if you want to be sure. You can stop reading now for a moment and analyze that indeed other companies will keep the same sum, described above. 78 79 Ok, but so far we don't count the income coming from parent's fanpage. But, for each company we can store all its children in one set. All children have the same "income from parent's fanpage" because they have the same parent. So, in set you can keep children sorted by the sum described above. Then, we should always puts the extreme elements from sets in one global set. In the global set you care about the total income, equal to the sum described above and this new "income from parent". Check codes for details. The complexity should be , with big constant factor. 80 81 [18286747](/contest/643/submission/18286747 "Submission 18286747 by Radewoosh") 82 83 # 7 [674E - Bear and Destroying Subtrees](/contest/674/problem/E "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 1 Edition)") 84 85 (invented by [Errichto](/profile/Errichto "International Grandmaster Errichto")) 86 87 Let *dp*[*v*][*h*] denote the probability that subtree *v* (if attacked now) would have height at most *h*. The first observation is that we don't care about big *h* because it's very unlikely that a path with e.g. 100 edges will survive. Let's later talk about choosing *h* and now let's say that it's enough to consider *h* up to 60. 88 89 When we should answer a query for subtree *v* then we should sum up *h*·(*dp*[*v*][*h*] - *dp*[*v*][*h* - 1]) to get the answer. The other query is harder. 90 91 Let's say that a new vertex is attached to vertex *v*. Then, among *dp*[*v*][0], *dp*[*v*][1], *dp*[*v*][2], ... only *dp*[*v*][0] changes (other values stay the same). Also, one value *dp*[*par*[*v*]][1] changes, and so does *dp*[*par*[*par*[*v*]]][2] and so on. You should iterate over *MAX*_*H* vertices (each time going to parent) and update the corresponding value. TODO — puts here come formula for updating value. 92 93 The complexity is *O*(*q*·*MAX*_*H*). You may think that *MAX*_*H* = 30 is enough because  is small enough. Unfortunately, there exist malicious tests. Consider a tree with  paths from root, each with length 31. Now, we talk about the probability of magnitude: 94 95 1 - (1 - (1 / 2)*d*)*N* / *d* 96 97 which is more than 10- 6 for *d* = 30. 98 99 <http://www.wolframalpha.com/input/?i=1+-+(1-(1%2F2)%5Ed)%5E(N%2Fd)+for+N+%3D+500000+and+d+%3D+30> 100 101 [18286721](/contest/643/submission/18286721 "Submission 18286721 by Radewoosh") 102 103 # 8 [674F - Bears and Juice](/contest/674/problem/F "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 1 Edition)") 104 105 (invented by [Radewoosh](/profile/Radewoosh "International Grandmaster Radewoosh")) 106 107 Let's start with *O*(*q*·*p*2) approach, with the dynamic programming. Let *dp*[*days*][*beds*] denote the maximum number of barrels to win if there are *days* days left and *beds* places to sleep left. Then: 108 109  110 111 Here, *i* represents the number of bears who will go to sleep. If the same *i* bears drink from the same *X* barrels and this exact set of bears go to sleep then on the next day we only have *X* barrels to consider (wine is in one of them). And for *X* = *dp*[*days* - 1][*beds* - *i*] we will manage to find the wine then. 112 113 And how to compute the dp faster? Organizers have ugly solution with something similar to meet in the middle. We calculate dp for first *q*2 / 3 days and later we use multiply vectors by matrix, to get further answers faster. The complexity is equivalent to *O*(*p*·*q*) but only because roughly *q* = *p*3. We saw shortest codes though. How to do it guys? 114 115 You may wonder why there was 232 instead of 109 + 7. It was to fight with making the brute force faster. For 109 + 7 you could add *sum* + = *dp*[*a*][*b*]·*dp*[*c*][*d*] about 15 times (using unsigned long long's) and only then compute modulo. You would then get very fast solution. 116 117 [18286766](/contest/643/submission/18286766 "Submission 18286766 by Radewoosh") 118 119 # 9 [674G - Choosing Ads](/contest/674/problem/G "Codeforces Round 351 (VK Cup 2016 Round 3, Div. 1 Edition)") 120 121 (invented by [qwerty787788](/profile/qwerty787788 "Grandmaster qwerty787788")) 122 123 Let's first consider a solution processing query in O(n) time, but using O(1) extra memory. If p = 51%, it's a well known problem. We should store one element and some balance. When processing next element, if it's equal to our, we increase balance. If it's not equal, and balance is positive, we decrease it. If it is zero, we getting new element as stored, and setting balance to 1. 124 125 To generalize to case of elements, which are at least 100/k%, we will do next. Let's store k elements with balance for each. When getting a new element, if it's in set of our 5, we will add 1 to it's balance. If we have less, than 5 elements, just add new element with balance 1. Else, if there is element with balance 0, replace it by new element with balance one. Else, subtract 1 from each balance. The meaning of such balance becomes more mysterious, but it's not hard to check, that value is at least 100/k% of all elements, it's balance will be positive. 126 127 To generalize even more, we can join two of such balanced set. To do that, we sum balances of elements of all sets, than join sets to one, and then removing elements with smallest balance one, by one, untill there is k elements in set. To remove element, we should subtract it's balance from all other balances. 128 129 And now, we can merge this sets on segment, using segment tree. This solution will have complexity like *n* * *log*(*n*) * *MERGE*, where MERGE is time of merging two structures. Probably, when k is 5, *k*2 / 2 is fastest way. But the profit is we don't need complex structures to check which elements are really in top, so solution works much faster.