Nickolas's blog

By Nickolas, 6 years ago, translation, In English,

So, here goes the editorial. I'll tell you right away that nobody guessed 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.

148A - Insomnia cure

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 Ni, 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 N1 - N2 + N3 - N4. You'd have to use this method if the total number of dragons was too large for iterating over it.

148B - Escape

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  *  Vp. 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 Vd - Vp. 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).

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.

You'll also need to check for the case Vp ≥ Vd separately — the dragon can be old and fat and lazy, and he might never catch up with the princess.

148D - Bag of mice

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.

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.

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:

map<pair<int, int>, double> memo;

double p_win_1_rec(int W, int B) {
    if (W <= 0) return 0;
    if (B <= 0) return 1;
    pair<int, int> args = make_pair(W, B);
    if (memo.find(args) != memo.end()) {
        return memo[args];
    }
    // we know that currently it's player 1's turn
    // probability of winning from this draw
    double ret = W * 1.0 / (W + B), cont_prob = B * 1.0 / (W + B);
    B--;
    // probability of continuing after player 2's turn
    cont_prob *= B * 1.0 / (W + B);
    B--;
    // and now we have a choice: the mouse that jumps is either black or white
    if (cont_prob > 1e-13) {
        double p_black = p_win_1_rec(W, B - 1) * (B * 1.0 / (W + B));
        double p_white = p_win_1_rec(W - 1, B) * (W * 1.0 / (W + B));
        ret += cont_prob * (p_black + p_white);
    }
    memo[args] = ret;
    return ret;
}

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.

148E - Porcelain

This problem involved dynamic programming with precalculation.

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.

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.

 
 
 
 
  • Vote: I like it  
  • +47
  • Vote: I do not like it  

»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

In problem B,most solutions use double to calculate the distance between the princess and the cave...but I think the precision of double may lead sth wrong... I think it is not a good way to use the double...for example,you may get a distance of 9.99999999999999,but indeed it means 10. and if the distance between the castle and the cave is 10, these solutions will give the wrong answer that one more bijou than really needed..

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to solve it by using rational arithmetic library of my own in C++, with both numerators and denominators of type long long. It seems the test cases included the one that deliberately tried to overflow numerators and denominators. So you need arbitrary-precision arithmetic to solve this w/o floating-point numbers, which is a bit hard in C++.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      = =I know. But as a problem writer, it's not fair to prepare no data to fail the implementation using double.Because a careful participant may use something safe but more complicated(such as rational,java.math.BigDecimal) to implementation, and it takes more time which means lower score. Moreover,to accept a likely wrong solution is itself ironic.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If you guys disagree with me,please tell me why...

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      I agree with you in general case, but for this problem, bruteforce says: the worst possible test case is 17 99 1 3 999 minimum difference between current path and C is 0.00000047198966512951

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seem's like the solution of pE has the complexity of O(N^4) for enumerate N shelves and for each shelf there could be 100(N) items and for every time you advance to the next shelf you should calculate all the M possibilties...

so let's assume that val(i, j) means the maximum value when you take j items at the i-shelf and DP(i, j) means the maximum total value we took from the (1~i)-shelves when we had took j items where DP(i,j)=max(DP(i-1,j-k)+val[i][k]), but we'll have to enumerate k from 0~100

which part have I mistaken? shouldn't the complexity be O(100^4)? Or is there something wrong in my solution?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You solution is right and the complexity is really O(100^4).

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then how can a solution of this large complexity pass in < 0.25 Second?

      Do you have any ideas?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

148A - Средство от бессонницы I write a solution for problem A by the technique you mentioned second but can't get the correct output. What am I missing :/ http://ideone.com/fS5eup#

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For Solving Insomnia Cure Problem using the inclusion-exclusion principle:

    Let's imagine a simpler case in which "Every k-th dragon got punched in the face with a frying pan. Every l-th dragon got his tail shut into the balcony door." so every m-th and n-th dragon go away safe. In this case how to calculate the number of damaged dragons ? - every kth dragon, there is definitely: d/k dragons damaged - every lth dragon, there is definitely: d/l dragons damaged - but some of the dragons damaged were counted twice, i.e., the same dragon got punched and go his tail shut into the door, so we must subtract them by the principle: the principle says to get the union set size ,you need to subtract the intersection size from the size of the two sets. - but what is the intersection set? set of number that can be divided by k and also by l, definitely any multiple of k*l is qualified but are these numbers only the numbers in the set ? no, in fact multiples of least common multiple of k and l satisfy the requirement, i.e, lcm (k,l). To get the size of this set in the range till d, calculate: d/lcm(k,l) Now what to do for a harder case of more m-th and n-th dragon getting damaged? use the generalization of the equation above :

    • so now you need to calculate not only one intersection of 2 sets, but multiple intersections : there is 4 sets: divisors of each one of the four numbers make a set.
    • not only intersection of 2 sets is needed but also intersection of 3 sets and 4 sets
    • alternating +ve and -ve is needed
    • submission
    • At last, this solution is not O(1) as calculating LCM requires calculating Greatest Common Divisor which have Logarithmic complexity.
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks for this. I was having the same problem. I guess I wasn't getting the right answer because I was using plain multiplication instead of LCM.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give a hint for Problem C? Thanks.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I'll tell you how I approached this problem (and I don't claim this is the best/optimal way to approach it).

    After reading the problem for the first time, I quickly categorized it to be easy greedy problem, (Div2A problem which author mistakenly put it in Div2C) unaware of the plenty landmines present in this problem.

    The problem statement is simple to understand -
    If the current value is strictly greater than all the previous values, then the queen says "oh"; and if the current value is strictly greater than the sum of all the previous values, then the queen says "wow".
    Tip: For such problem, one should use pencil and paper more quickly than they think they should.

    Case 1) If n == 1, then print any random number between [1, 50000] (this range constraint is mentioned in the problem)
    Case 2) If n == 2, then (*This part will make you understand why -1 is even present*)

    n Number_of_oh number_of_wow Is sequence possible? Example sequence
    2 0 0 Yes {1, 1}
    2 0 1 Yes {1, 2}
    2 1 0 No, because its ambigious to count this value as "oh" or "wow". NA

    Case 3) If n == 3, then

    n Number_of_oh Number_of_wow is sequence possible example sequence
    3 0 0 Yes {1, 1, 1}
    3 0 1 Yes {1, 2, 2}
    3 0 2 Yes {1, 2, 4}
    3 1 0 Yes {1, 1, 2}
    3 1 1 Yes {1, 2, 3}
    3 2 0 No, because its ambigious to count the second value as "oh" or "wow"

    Now if you extend this, you will observe following patterns -
    Observation 1) When number_of_wow = 0, and number_of_oh = n — 1, it is not possible to generate the sequence.
    Observation 2) It is always better to generate all the number_of_wow first, and then generate all number_of_oh, after which keep the number constant. (Don't ask for formal proof! Go by your intuition :) )
    Observation 3) If number_of_wow = 0, and number_of_oh < n — 1, then one should generate non-decreasing (or ascending) sequence after the second number/element.
    For example — if n = 5, number_of_wow = 0, and number_of_oh = 2, then possible sequence is {1, 1, 2, 3, 3}. Reason — The second element, if greater than the first one will always be counted as "wow" and not as "oh".
    Observation 4) If number_of_wow != 0, then generate non-decreasing (or ascending) sequence from second element itself.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For Div2C, what should be the output for the following test cases, and why?
1. 2 0 1
2. 2 1 0

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem A: Inclusion-Exclusion Approach O(1) solution

int main(){

int a,b,c,d;
cin>>a>>b>>c>>d;
int n;cin>>n;


int sum=0;
for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
       for(int k=0;k<2;k++){
         for(int l=0;l<2;l++){

          int ct=0;
          int accum=1;
          if(i){
              ct++;
              accum*=a;
          }
          if(j){
              ct++;
              accum*=b;
          }
          if(k){
              ct++;
              accum*=c;
          }
          if(l){
              ct++;
              accum*=d;
          }


          if(ct==0)continue;
          if(ct%2){
              sum+=n/accum;
          }
          else sum-=n/accum;

         }
       }
    }
}

cout<<sum;

}

This gets the 2nd test case incorrect ( gets 18 instead of 17 ) . Any solution to this problem ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got it ... taking the lcm of the accumulate step did the trick !!

    Modified code :


    ll lcm2(ll a,ll b){return (a*b)/ __gcd(a,b);}

    int main(){

    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int n;cin>>n;
    
    
    int sum=0;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
           for(int k=0;k<2;k++){
             for(int l=0;l<2;l++){
    
              int ct=0;
              int accum=1;
              if(i){
                  ct++;
                  accum=lcm2(accum,a);
              }
              if(j){
                  ct++;
    
                  accum=lcm2(accum,b);
    
    
              }
              if(k){
                  ct++;
                  accum=lcm2(accum,c);
              }
              if(l){
                  ct++;
                  accum=lcm2(accum,d);
              }
    
    
              if(ct==0)continue;
              if(ct%2){
                  sum+=n/accum;
              }
              else sum-=n/accum;
    
             }
           }
        }
    }
    
    cout<<sum;
    

    }