codeforces-scrape

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

148.md (7000B)


      1 Source: https://codeforces.com/blog/entry/3819
      2 
      3 So, here goes the editorial. I'll tell you right away that nobody guessed [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")'s problem (nice disguise, er?) — it was problem C about the picky princess. Actually, this was the first problem of the round, the rest of problems I invented to keep up the lovely topic.
      4 
      5 [148A - Insomnia cure](/contest/148/problem/A "Codeforces Round 105 (Div. 2)")
      6 
      7 The number of dragons D can be quite small, so the problem can be solved in a straightforward way, by iterating over dragons 1 through D and checking each dragon individually. Time complexity of such solution is O(D). There exists a smarter solution with O(1) complexity, based on inclusion-exclusion principle. You'll have to count the numbers of dragons which satisfy at least one, two, three or four of the damage conditions *N**i*, i.e., dragons who have index divisible by LCM of the corresponding sets of numbers. Remember that the number of numbers between 1 and D which are divisible by T equals *D* / *T*. Finally, the number of dragons that get damaged equals *N*1 - *N*2 + *N*3 - *N*4. You'd have to use this method if the total number of dragons was too large for iterating over it.
      8 
      9 [148B - Escape](/contest/148/problem/B "Codeforces Round 105 (Div. 2)")
     10 
     11 In this problem it was enough to simulate the sequence of events that happen on the line between the cave and the castle. My solution focused on two types of evens — "the dragon is in the cave and sets off after the princess" and "the dragon and the princess are at the same coordinate"; in this case it's enough to keep track of time and princess' coordinate, no need to store dragon's one. The first type of event happens for the first time at time T, when the princess' coordinate is *T*  *  *V**p*. If at this time she has already reached the castle, no bijous are needed. Otherwise we can start iterating. The time between events of first and second type equals the princess' coordinate at the moment of first event, divided by *V**d* - *V**p*. Adjust the princess' coordinate by the distance she will cover during this time and check whether she reached the castle again. If she didn't, she'll need a bijou — increment the number of bijous required. The second part of the loop processes the return of the dragon, i.e., the transition from second type of event to the first one. The time between the events equals princess' new coordinate, divided by the dragon's speed, plus the time of straightening things out in the treasury. Adjust princess' coordinate again and return to the start of the loop (you don't need to check whether the princess reached the castle at this stage, since it doesn't affect the return value).
     12 
     13 The complexity of the algorithm can be estimated practically: the number of loop iterations will be maximized when dragon's speed and distance to the castle are maximum, and the rest of parameters are minimum. This results in about 150 bijous and the same number of iterations.
     14 
     15 You'll also need to check for the case *V**p* ≥ *V**d* separately — the dragon can be old and fat and lazy, and he might never catch up with the princess.
     16 
     17 [148D - Bag of mice](/contest/148/problem/D "Codeforces Round 105 (Div. 2)")
     18 
     19 Initially this problem was a boring homework one about drawing balls out of the bag. But seriously, do you think a dragon would have something so mundane as a bag of balls in his cave? And he definitely could find some use for a bag of mice — for example, using them to scare the princess or as a snack.
     20 
     21 If mice were balls and never jumped out of the bag, the problem would be doable in a single loop. Suppose that at some step we have W white and B black mice left in the bag, and the probability to get into this state is P (initially W and B are input values, and P = 1). The absolute probability to get a white mouse at this step is *P* * *W* / (*B* + *W*) (the probability of getting to this state, multiplied by the conditional probability of getting white mouse). If it's princess' turn to draw, this probability adds to her winning probability, otherwise her winning probability doesn't change. To move to the next iteration, we need the game to continue, i.e., a black mouse to be drawn on this iteration. This means that the number of black mice decreases by 1, and the probability of getting to the next iteration is multiplied by *B* / (*B* + *W*). Once we've iterated until we're out of black mice, we have the answer.
     22 
     23 Unfortunately, the mice in the bag behave not as calmly as the balls. This adds uncertainty — we don't know for sure what state we will get to after the dragon's draw. We'll need a recursive solution to handle this (or dynamic programming — whichever one prefers). When we solve a case for (W, B), the princess' and the dragon's draws are processed in a same way, but to process the mouse jumping out of the bag, we'll need to combine the results of solving subproblems (W, B — 3) and (W — 1, B — 2). The recursive function of the reference solution is:
     24 
     25 ```
     26 map<pair<int, int>, double> memo;
     27 
     28 double p_win_1_rec(int W, int B) {
     29     if (W <= 0) return 0;
     30     if (B <= 0) return 1;
     31     pair<int, int> args = make_pair(W, B);
     32     if (memo.find(args) != memo.end()) {
     33         return memo[args];
     34     }
     35     // we know that currently it's player 1's turn
     36     // probability of winning from this draw
     37     double ret = W * 1.0 / (W + B), cont_prob = B * 1.0 / (W + B);
     38     B--;
     39     // probability of continuing after player 2's turn
     40     cont_prob *= B * 1.0 / (W + B);
     41     B--;
     42     // and now we have a choice: the mouse that jumps is either black or white
     43     if (cont_prob > 1e-13) {
     44         double p_black = p_win_1_rec(W, B - 1) * (B * 1.0 / (W + B));
     45         double p_white = p_win_1_rec(W - 1, B) * (W * 1.0 / (W + B));
     46         ret += cont_prob * (p_black + p_white);
     47     }
     48     memo[args] = ret;
     49     return ret;
     50 }
     51 ```
     52 
     53 The time complexity of recursion with memoization is O(W*B), i.e., the number of different values the input can take. Note that in this implementation access to the map adds log(W*B) complexity, but you can avoid this by storing the values in an 2-dimensional array.
     54 
     55 [148E - Porcelain](/contest/148/problem/E "Codeforces Round 105 (Div. 2)")
     56 
     57 This problem involved dynamic programming with precalculation.
     58 
     59 The first part of the solution was to precalculate the maximal cost of i items taken from the shelf (i ranging from 1 to the number of items on the shelf) for each shelf. Note that this can't be done greedily: this can be seen on the shelf 6: 5 1 10 1 1 5.
     60 
     61 The second part is a standard dynamic programming, which calculates the maximal cost of items taken for index of last shelf used and total number of items taken. To advance to the next shelf, one has to try all possible numbers of items taken from it and increase the total cost of items taken by corresponding precalculated values.