rng_58's blog

AtCoder Grand Contest 028
By rng_58, history, 8 years ago, In English

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

Contest Link

Contest Announcement

Contest duration: 150 minutes

The point values will be announced later.

Let's discuss problems after the contest.

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

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

3min

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it +41 Vote: I do not like it

F is solvable in O(N2logN), so please try it.

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I have solved task A and I have read 'editorial', but could anyone explain the solution in his own words?

→ Reply
»
8 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

How to solve task B?

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 5  
    Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Thank you very much :)

      → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        8 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Connectivity is reflexive. By “x and y are connected” they mean “x and y are both connected to each other.”

        → Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve problem B ? I'm not getting it through editorial.

→ Reply
»
8 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

It seems that F1 is solvable in O(N^4/w) with bitset and some optimizations, for example this submission.

→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to task B?

→ Reply