rng_58's blog

AtCoder Grand Contest 028
By rng_58, history, 6 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

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

3min

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

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

→ Reply
»
6 years ago, # |
  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
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve task B?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← 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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you very much :)

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        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
      • »
        »
        »
        »
        6 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Does it imply all blocks which are not removed are connected ?

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

            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.

            → Reply
»
6 years ago, # |
  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
»
6 years ago, # |
  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
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to task B?

→ Reply