17

Educational Codeforces Round 116 Editorial

 2 years ago
source link: http://codeforces.com/blog/entry/96454
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By awoo, history, 6 days ago, translation, In English
1606A - AB Balance

Idea: BledDest

Tutorial
Solution (adedalic)
1606B - Update Files
Tutorial
Solution (Neon)
1606C - Banknotes

Idea: BledDest

Tutorial
Solution (Neon)
1606D - Red-Blue Matrix

Idea: BledDest

Tutorial
Solution (awoo)
1606E - Arena

Idea: BledDest

Tutorial
Solution (Neon)
1606F - Tree Queries

Idea: BledDest

Tutorial
Solution (BledDest)

6 days ago, # |

← Rev. 2 →  

+17

I didn't sort the array in problem D, but the rest matches with the editorial. No. No. No. NOOOOOOOOOOOOO my ratings :'(

6 days ago, # |

For problem E Total permutations possible are x^n. To get a winner I set one maximum value(suppose a) and set rest values less than a so they have a-1 options. So its total permutations will be n.(a-1)^(n-1). Now minimum value of a can be n otherwise all players will be eleminated in the first round. So I get the formula x^n — n.( (n-1)^(n-1) + (n)^(n-1) + (n+1)^(n-1) + ..... + (x-1)^(n-1)) Can anyone tell me what is wrong in this approach it is failing on sample 4.

  • 6 days ago, # ^ |

    It isn't always the case that the losing players can have any health that's less than the winning player's health. Take the case n=3, health values are 4,3,3.

    • 6 days ago, # ^ |

      Thanks, Got it now.

6 days ago, # |

In editorial of problem E it should be <2 or <=1, when talking about fights which ended.

6 days ago, # |

Hi in Problem B, if k is larger than n/2 we can use ceil(log2(n)) to get the answer as at each step we can go up by power of ^2 so I am pretty confident in my solution.

But it fails at test case: 576460752303423489 576460752303423489 (https://codeforces.com/contest/1606/submission/133708639) I just want to know if this is because the precision points are too small to consider? and this is a language issue? but mathematically it is correct. Can you please help me?

  • 6 days ago, # ^ |

    Yes, same I was trying but it failed, though it is mathematically correct!!!

  • 6 days ago, # ^ |

    Precision error, definitely. In this case 57646075230342348 9 (as long long int) is implicitly converted to 57646075230342348 8 .0000 (as double)

    Codeforces (along with most computers/compilers) uses 64-bit long long int and 64-bit IEEE-754 double. However, IEEE-754 double has only 53-bit significand precision, according to Wikipedia.

    • 5 days ago, # ^ |

      ← Rev. 2 →  

      0

      Thanks, I didn't know that. I appreciate your help all.

  • 5 days ago, # ^ |

    ← Rev. 2 →  

    +3

    I have used a similar approach 133723445
    The constraints of n and k are probably too big for log2() function, Therefore I've used log2l() for extra precision. You can read the documentation about these functions here https://www.cplusplus.com/reference/cmath/log2/

    • 5 days ago, # ^ |

      I used the log2l() version and it worked, also there is a similar version for the pow() function powl(). to use the long double. Thanks for the help :)

5 days ago, # |

My solution to D was much longer and more complicated, but here is at least a neat-ish observation that it used:

Just looking at the first column, we can be sure that if a solution exists, the row with the max element is red and the row with the min element is blue. This is enough to uniquely identify where the cut should be: going left to right, it is whenever we switch from red > blue to blue > red. Now that we know where the split is, we can simplify the matrix by only keeping the min and max element for each row, on each side of the matrix.

My solution did this, then treated each row as an interval [min, max]. On the left side, any overlapping/touching intervals need to be merged, and in the end we have a list of disjoint ranges, after which, in similar spirit to the editorial solution, we sort then brute force on the number of blue ranges. I then used BSTs on the right side to keep track of whether blue > red, which are quick to update since I've condensed each row into only 2 values.

4 days ago, # |

Is it just me ? or C seems to have relatively high number of submissions during contest compared to it's toughness.

4 days ago, # |

Can anyone explain me C- Bank Notes? I did not understand the part how the maximum we are allowed to take is 10^a(i) + 1/10^a(i) -1

Thanks

  • 35 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Imagine you have input 

    2 999
0 3

    In order to get a minimum number that can be made with atleast 1000 (k + 1), final choice;

    1. 999 -> 0 (1) = 999
    2. 1 -> 3 (1000) = 1000

    That will make 1999. If you move any notes from 0 to 1 denominator then number increases and its not minimum number any more for given notes.

    So the idea is to choose maximum notes for lower denominator. And maximum notes will be diff between two adjacent denominator. Hope that helps.

    now imaging then k = 1000 for same input picking 1001 (k+1). The optimal choice is; 1. 999 -> 0 (1) = 999 2. 2 -> 3 (1000) = 2000

    That will make 2999 which will require atleast 1000 notes. no less than that.

    else fyi,

    1. 1000 -> 0 (1) = 1000
    2. 1 -> 3 (1000) = 1000

    That will make 2000 But 2000 can be make with just two notes.

    Hope that helps !

    • 33 hours ago, # ^ |

      Thankyou so much for the reply, It makes sense now.

      also I misread the editorial it is not [10^(a[i]) + 1] it is [10^a[i+1]].

      Thanks again.

4 days ago, # |

excellent tutorial, thanks a lot.

4 days ago, # |

← Rev. 2 →  

0

UPDATING FILES :- doubt if (cur < n) ans += (n — cur +k-1) / k; can anyone explain why k-1 is being added . It seems to be confusing . Pls explain

  • 4 days ago, # ^ |

    (a+b-1)/b is the same as ceil(a/b) if b is positive

3 days ago, # |

← Rev. 2 →  

+42

Another solution for F with liangjiawen2007.

Considering the value of kk, obviously we do at most nknk operations. Thus, we can have a O(nn−−√)O(nn) solution based on the observation.

When k≤n−−√k≤n, there are at most n−−√n different values of kk. We can have such dp as follow: fi,jfi,j for the maximum value you can get for k=jk=j. Transforming is easy, fu,i=∑max(1,fv,i−i)fu,i=∑max(1,fv,i−i) and we can do it in O(n)O(n) for every jj.

When k>n−−√k>n, we do at most n−−√n operations, we can have dp as follow: gi,jgi,j for the maximum sons you can get when you do jj operations. When we merge subtree uu and vv, we get gu,i+j+1←gu,i+gv,jgu,i+j+1←gu,i+gv,j.

This is a knapsack problem on tree, as j≤n−−√j≤n, we can use the trick that we only do i≤min(k,sizu)i≤min(k,sizu) and j≤min(k,sizv)j≤min(k,sizv) while transforming, then the time complexity will be O(nk)O(nk) while k=n−−√k=n

The total time and space complexity is O(nn−−√)O(nn)

Here is the submission 134047234

3 days ago, # |

can someone explain the output for n = 3 and x = 3 of problem E ?

15 hours ago, # |

← Rev. 2 →  

0

UPDATE It's my fault, I misunderstand that it will compare only the column. Please give me an apologize.

In problem D, I found that there is a test case

The solution gives the answer as NO.

But I think it is possible for YES by painting to be RBR with k = 2.

Please correct me if I'm wrong. Thank you :)

3 hours ago, # |

can somebody tell why this is wrong answer for C.Banknotes ? 134382992


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK