maroonrk's blog

AtCoder Grand Contest 062 Announcement
By maroonrk, history, 18 months ago, In English

We will hold AtCoder Grand Contest 062. This contest counts for GP30 scores.

The point values will be 400-700-800-1100-1300-2000.

We are looking forward to your participation!

Recently we are experiencing DDoS attacks and our website can be unstable during the contest. To mitigate the risk that the contest gets unrated, we will upload the PDF statement when the rated registration is closed (i.e. 5 minutes after the contest starts). We will later post the link here.

Problem Statement (link).

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

»
18 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Hope to not brick A this time

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +85 Vote: I do not like it

    Might as well start with B.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it +60 Vote: I do not like it

      Well, this time it's B for which I have completely no idea how to even approach it :)

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Maybe even with C next time

      → Reply
»
18 months ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve B

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    Let's say a subsequence is compact if all the adjacent numbers differ by 1.

    After one operation, the permutation is partitionable into at most 2 compact subsequences.

    After k operations, 2^k of them, and it turns out this is the IFF condition.

    Let's look at the operations in reverse order.

    We first sort all the compact subsequences: let's say there are M of them, S_1, ..., S_M.

    One reverse operation allows you to pick a subset of them and place them at the end. When you select such subset, they have to form a suffix of S_1, ..., S_M by definition. It now splits into two independent part, [S_1, ..., S_i] [S_i+1, ..., S_M], and both part acts independently till the end.

    Now set DP[x][l][r]: min cost to solve the interval [S_l, ..., S_r] using x last operations, 1 <= l <= r <= M. Transition is just iterating over all suffix.

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Another way to look at it: for each operation, assign 0 or 1 to each number and look at the operations in reverse order. Then the initial order of any two elements is determined by which has 0 in the first operation where they have different numbers; if there's no such operation, then it's the order in $$$P$$$.

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +66 Vote: I do not like it

Since no editorial yet, why this stupid solution for C is fast enough?

Sort $$$a_i$$$ by increasing, and maintain the set $$$S_i$$$ of numbers representable with $$$a_1, \ldots, a_i$$$ as a union of segments. If there at least $$$k$$$ non-representable numbers less than $$$a_{i + 1}$$$, print them, otherwise find $$$S_{i + 1} = S_i \cup (S_i + a_{i + 1})$$$.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    This is indeed equivalent to the intended solution. When you add $$$a_i$$$ and there are less than $$$k$$$ non-representable values, it means there are no more than $$$k$$$ segments before $$$a_i$$$. Therefore the number of segments increases by at most $$$k$$$ after adding $$$a_i$$$.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      But why can't segments after $$$a_i$$$ grow exponentially? I must be missing something.

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Heavy plus. I just wrote that out of desperation. The solution is super obvious, but why it works...

        → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        The segments after $$$a_i$$$ are a union of $$$(S_i+a_i)$$$ and something. Therefore the number of segments is at most the number of segments in $$$(S_i+a_i)$$$, which is just the number of segments in $$$S_i$$$.

        → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          ← Rev. 2   Vote: I like it +23 Vote: I do not like it

          Can't say I get it still. The trivial upper bound for size of "union of $$$(S_i + a_i)$$$ and something" is $$$|S_i + a_i|$$$ + |something|, unless there's something more to be said about their superposition. Why can't the two be just disjoint, for instance?

          → Reply
          • »
            »
            »
            »
            »
            »
            18 months ago, # ^ |
              Vote: I like it +89 Vote: I do not like it

            Let $$$V_i=a_1+a_2+\cdots+a_i$$$. We can prove that, after adding $$$a_i$$$, there are at most $$$K \times i$$$ non-representable numbers in the range $$$[0,V_i]$$$. (Note that I'm now talking about the number of values, not the number of segments.)

            Let's say $$$S_{i-1}$$$ satisfies the condition and let's see what happens after adding $$$a_i$$$. In the range $$$[0,a_i]$$$, there are at most $$$K$$$ non-representable numbers. In the range $$$[a_i,V_{i+1}]$$$, there are at most $$$K \times i$$$ non-representable numbers. This is because this range contains all elements of $$$(S_i+a_i)$$$.

            The intended solution keeps non-representable numbers in $$$[0,V_i]$$$. Keeping segments is almost the same as that.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              18 months ago, # ^ |
                Vote: I like it +15 Vote: I do not like it

              Ah, now in terms of non-representable numbers below $$$V_i$$$ this is much more clear. Thanks for your explanation!

              → Reply
»
18 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +45 Vote: I do not like it

    In general, after any number of steps there exist numbers $$$L, R$$$ such that we can be anywhere in the region $$$L \leq |x| + |y| \leq R$$$. If the next step is $$$d$$$, then the new boundaries are $$$R' = R + d$$$, $$$L' = \max(0, L - d, d - R)$$$. If we additionally put an upper bound $$$M$$$, then the first one simply becomes $$$R' = \min(M, R + d)$$$. Note that if $$$D$$$ is the largest step in the set, we have $$$M \geq D / 2$$$ to be able to make the step $$$D$$$. Also, if answer $$$M$$$ exists, it is at most $$$D$$$.

    Respective to the upper bound $$$M$$$, say that a step $$$d$$$ is large if $$$d > M$$$, and small otherwise. Note that once $$$R = M$$$, is always stays that way (provided on every step $$$L \leq R$$$), thus any solution step sequence can be divided into two phases: before and after $$$R$$$ reaches $$$M$$$. With an exchange argument one can prove that the second phase should use steps by decreasing of magnitude. Further, in the second phase:

    • after a large step $$$D$$$ in second phase we simply have $$$R' = M$$$, $$$L' = D - M$$$
    • and after a small step $$$d$$$ we have $$$R = M$$$, $$$L' = \max(0, L - d)$$$.

    Let $$$S$$$ be the sum of all small steps. Now there are a few cases:

    • there is at most one large step in total. Then we just check that the largest step is at most the sum of all others.
    • all large steps occur in the second phase. Let the sum of (small) steps in the first phase be $$$s_1$$$, and the smallest large step be $$$D$$$. We must have $$$s_1 \geq M$$$, $$$S - s_1 \geq D - M$$$.
    • there is a large step $$$D_1$$$ at the end of the first phase, and the last large step in the second phase is $$$D_2$$$. Then, defining $$$s_1$$$ similarly, we have $$$s_1 \geq D_1 - M$$$, $$$s_2 \geq D_2 - M$$$.

    Note that we can only consider

    Unable to parse markup [type=CF_MATHJAX]

    above among the smallest two large steps available (check all combinations). Checking conditions requires finding the smallest representable sum $$$s \geq x$$$ of small steps. These can be maintained and queried with a bitset of reachable sums, along with gradually increasing $$$M$$$.
    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

So:

1) Does unrated participation count towards race score?

2) Does unrated participation count towards the number of won rounds? Currently neither of us has it counted as a win.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    1) They count. (See the discussion here).

    2) They also count. It must be a small bug and we will fix it.

    → Reply
»
18 months ago, # |
  Vote: I like it +56 Vote: I do not like it

Even though I was angry at some of the problems in this round, I want to thank you, maroonrk, for slightly lowering your difficulty standards and allowing AGC where it is actually possible to solve more than 1 problem.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

On kenkoooo, problem F is shown as $$$0$$$ points instead of $$$2000$$$. Someone please fix it.

→ Reply
»
18 months ago, # |
  Vote: I like it +63 Vote: I do not like it

So lucky to take the first place in this round! But because there was a conflict with the APIO closing ceremony in the first thirty minutes, I chose unrated to participate TAT.

C and D seems very magical, I solved them just by feeling and guessing.

I also want to ask the same question as Radewoosh's.

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

So when editorial?

→ Reply