103.md (5982B)
1 Source: https://codeforces.com/blog/entry/2426 2 3 It will be fully translated later, sorry for slowpoking :( 4 5 | | | | 6 | --- | --- | --- | 7 | | **Blackjack ([problem A, div-2](//codeforces.com/contest/104/problem/A)). The problem's author is [Alex_KPR](https://codeforces.com/profile/Alex_KPR "Подполковник Alex_KPR")** | | 8 | | Obviously, suits are not change the answer. Look at all possible situations: [0 - 10] — zero ways. [11] — four ways using aces. [12 - 19] — four ways using cards from 2 to 9. [20] — 15 ways, they are described in statement. [21] — four ways using aces. [22 - 25] — zero ways. | | 9 | | Complexity is *O*(1). | | 10 11 12 13 | | | | 14 | --- | --- | --- | 15 | | **Testing Pants for Sadness ([problem B, div-2](//codeforces.com/contest/104/problem/B); [problem A, div-1](//codeforces.com/contest/103/problem/A)). The problem's author is [Alex_KPR](https://codeforces.com/profile/Alex_KPR "Подполковник Alex_KPR")** | | 16 | | We can't move to the *i* + 1-th question before clicking all answers at *i*-th question. We will move to the very beginning clicking at *a**i* - 1 answers and only one will move us to the next step. Every way from beginning to *i*-th question have length equal to *i* - 1 plus one for click. There is a simple formula for *i* + 1-th question: *c**i* = (*a**i* - 1)· *i* + 1, 1-based numeration. Let's summarize all values of *c**i* for making the answer. | | 17 | | Complexity is *O*(*n*). | | 18 19 20 21 | | | | 22 | --- | --- | --- | 23 | | **Cthulhu ([problem C, div-2](//codeforces.com/contest/104/problem/C); [problem B, div-1](//codeforces.com/contest/103/problem/B)). The problem's author is [Alex_KPR](https://codeforces.com/profile/Alex_KPR "Подполковник Alex_KPR")** | | 24 | | Look at the formal part of statement. Cthulhu is a simple cycle with length of 3 or more and every vertix of the cycle should be a root of some tree. Notice this two important facts: a) Cthulhu is a connected graph b) Cthulhu is a graph with only cycle If we add only one edge to tree (not a multiedge nor loop) then we will get a graph that a) and b) properties. There is a simple solution: let's check graph for connectivity (we can do it by one DFS only) and check *n* = *m* restriction. If all are ok then graph is Cthulhu. | | 25 | | Complexity is *O*(*m*). | | 26 27 28 29 | | | | 30 | --- | --- | --- | 31 | | **Russian Roulette ([problem D, div-2](//codeforces.com/contest/104/problem/D); [problem C, div-1](//codeforces.com/contest/103/problem/C)). The problem's author is [Alex_KPR](https://codeforces.com/profile/Alex_KPR "Подполковник Alex_KPR")** | | 32 | | Let's solve the problem when value *n* is even. Obviously, if *k* = 1 we should put a bullet at most right position. For example, choose *n* = 8 and our answer string will be: .......X Let's find probability of winning at this situation. We will write zeros at losing positions and ones at winning positions: 10101010 The simple idea is to put every next bullet for non-dropping down our winning chance as long as we can. After that we should put bullets in lexicographically order with growing value of *k*. Look for the answer for another *k*'s with *n* = 8: .....X.X ...X.X.X .X.X.X.X .X.X.XXX .X.XXXXX .XXXXXXX XXXXXXXX When *n* is odd our reasoning will be the same with a little bit difference at the beginning. Look at the answer with *n* = 9 and *k* = 1:: ........X 010101010 We may put second bullet as at even case. But there is exists another way, we may put our bullet at **1st** position and turn left the cylinder, look here: X.......X => .......XX 010101010 101010100 Obvioulsy probability of winning was not changed but answer made better. Next steps of putting are equal to even case: .....X.XX ...X.X.XX .X.X.X.XX .X.X.XXXX .X.XXXXXX .XXXXXXXX XXXXXXXXX There is no difficulties to give answers to queries. | | 33 | | Complexity is *O*(*p*). | | 34 35 36 37 | | | | 38 | --- | --- | --- | 39 | | **Time to Raid Cowavans ([problem E, div-2](//codeforces.com/contest/104/problem/E); [problem D, div-1](//codeforces.com/contest/103/problem/D)). The problem's author is [Alex_KPR](https://codeforces.com/profile/Alex_KPR "Подполковник Alex_KPR")** | | 40 | | Let's solve this problem by offline. Read all queries and sort them by increasing *b*. After that there are many effective solutions but I tell you a most simple of them. Look at two following algorithms: 1. For each (*a*, *b*)-query calculate the answer by the simple way: for(int i = a; i < n; i += b) ans += a[i]; 2. Fix the value of *b* and calculate DP for all possible values of *a*: for(int i = n - 1; i >= 0; i--) if (i + b >= n) d[i] = a[i]; else d[i] = d[i + b] + a[i]; Obvioulsy, the 1st algorithm is non-effective with little values of *b* and the 2nd algorithm is non-effecitve with very different values of *b*. Behold that it's impossible to generate the situation where all *b*'s are so little and different simultaniously. There is a simple idea: we may solve the problem by 1st algo if values of *b* are so large (if they are greater than *c*) and solve by 2nd algo if values of *b* are so small (if they are less of equal to *c*). We need to sort our queries because of no reason to calculate DP of any *b* more than once. If we choose *c* equal to that we will get a complexity. | | 41 | | Complexity is . | | 42 43 44 45 | | | | 46 | --- | --- | --- | 47 | | **Buying Sets ([problem E, div-1](//codeforces.com/contest/103/problem/E)). The problem's author is [winger](https://codeforces.com/profile/winger "Colonel winger")** | | 48 | | Translated by [Borisp](https://codeforces.com/profile/Borisp "Lieutenant colonel Borisp"). *[http://codeforces.com/blog/entry/2539](//codeforces.com/blog/entry/2539)* | | 49 | | | | 50 51 52 53 | | | | 54 | --- | --- | --- | 55 | | **[Discuss this contest](//codeforces.com/blog/entry/2405)** | |