codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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)** |  |