Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### rng_58's blog

By rng_58, history, 2 months ago, ,

AtCoder Grand Contest 028 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.

Contest Announcement

Contest duration: 150 minutes

The point values will be announced later.

Let's discuss problems after the contest.

•
• +125
•

 » 2 months ago, # |   0 3min
 » 2 months ago, # | ← Rev. 2 →   +41 F is solvable in O(N2logN), so please try it.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +20 My solution is slower than most of the O(N3) solutions:(my implementionIs there any way to distinguish them?
 » 2 months ago, # |   0 I have solved task A and I have read 'editorial', but could anyone explain the solution in his own words?
 » 2 months ago, # |   +15 How to solve task B?
•  » » 2 months ago, # ^ | ← Rev. 5 →   +11 Basic idea is this: fix two specific elements i and j. The cost for removing block j will include the weight of i if and only if j is removed first out of the blocks in the section i through j. If not, i will be disconnected from j (or won't be present at all) by the time j is removed.The number of permutations in which j is removed first among the blocks in i through j is N! / (j — i + 1). That's because there's N! total permutations, there are j — i + 1 blocks in that section, and by symmetry each of the blocks appears first in the same number of permutations.By precomputing N! / k we get an O(N2) solution. It can be sped up to O(N); maybe you can see how.
•  » » » 2 months ago, # ^ |   +3 Thank you very much :)
•  » » » 2 months ago, # ^ |   0 Here, two blocks x and y ( x ≤ y ) are connected when, for all z ( x ≤ z ≤ y ), Block z is still not removed. Does it mean only blocks to the left of y are connected to it ? Can someone explain the connectivity of two blocks? or all blocks which are not removed are connected ?
•  » » » » 2 months ago, # ^ |   0 Connectivity is reflexive. By “x and y are connected” they mean “x and y are both connected to each other.”
•  » » » » » 2 months ago, # ^ |   0 Does it imply all blocks which are not removed are connected ?
•  » » » » » » 2 months ago, # ^ |   0 No, the condition for x, y (x <= y) to be connected is that all blocks z in the interval [x, y] should not have been removed yet. If you have three blocks 1, 2, 3 and 2 is removed, then 1 and 3 are no longer connected.
•  » » » » » » » 2 months ago, # ^ |   0 Got it. Thank you !!
 » 2 months ago, # |   0 Can someone explain how to solve problem B ? I'm not getting it through editorial.
 » 2 months ago, # |   +5 It seems that F1 is solvable in O(N^4/w) with bitset and some optimizations, for example this submission.
 » 2 months ago, # |   0 Can someone explain the solution to task B?