rng_58's blog

AtCoder Grand Contest 030
By rng_58, history, 6 years ago, In English

AtCoder Grand Contest 030 will be held on Saturday (time). The writers are semiexp, sugim48, and DEGwer.

Contest Link

Contest Announcement

Contest duration: 110 minutes

The point values will be 200 — 800 (300) — 1000 — 1000 — 1400 — 1600.

Let's discuss problems after the contest.

By the way, this is the last contest of the year, and after this match, top 8 people by GP30 scores will qualify for tour finals. Four people (tourist, V--o_o--V, Petr, LHiC) have already qualified, but there are four more slots. Good luck!

Current Standings

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

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

Did you make beta version main one?

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

    Yes. Now beta.atcoder.jp will be redirected to atcoder.jp. Please use this.

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

how to solve B — Tree Burning ? [Editorial available, i gonna read from that]

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

    (I assumed that the distance from the Takahashi's residence is measured clockwise, since I'm more familiar with that metric).

    Let bi the distance between i-th and (i+1)-th tree (b0 = a[0], and bn = L — a[n]). Then the answer is sum of xi * bi for some set of xi.

    By toying around with a hand-written simulator, one can figured out that the most optimal solution has a form of either "RRR..RRLRLRLRL.." or "LLL..LLRLRLRL.." ("R" mean clockwise, "L" mean counter-clockwise. For the sake of simplicity, one only have to handle with the later case (the former can be handled by reversing the coordinate).

    Again, with the above simulator, one can figure out the pattern for the set x.

    For example, when n = 8, the pattern of x looked like following:

    8 6 4 2 0 1 3 5 7
7 7 5 3 1 0 2 4 6
6 6 6 4 2 0 1 3 5
5 5 5 5 3 1 0 2 4
4 4 4 4 4 2 0 1 3
3 3 3 3 3 3 1 0 2
2 2 2 2 2 2 2 0 1
1 1 1 1 1 1 1 1 0

    The array on the i-th line is the set x for the pattern with i letter "R" at the beginning of the move sequence.

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

I solved Problem B during the contest. My strategy is that the turning are always at the last trees, and we just check every possible number of turning. However, I do not quite get what the editorial means by Here, we can assume that b − a = 0 − b = e − d = d − c = 1 (otherwise we can get a longer path in an obvious way).. Would anyone like to explain this?

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

    For example, if d - c = 1 doesn't hold, we can extend the path as in the picture above, so it never becomes the optimal path.

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

      Oh.... For anyone else who was confused in a dumb way like me, d-c=1 means that d-c is one index off, not that d-c are actually one distance away.

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

        Thank you two so much! I was also confused in that way!

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

      if b = -1 doesn't hold，how can I get a longer path?

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

        Attach 0 -> b+1 -> 0 at the beginning (this is a special case, the initial direction changes)

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

    How did you get to the conclusion that turning always happens at the last trees, I personally think, I should have done something like xuanquang1999 did with the brute force solution, but I was too busy finding a DP solution, I was not able to come up with a solid greedy approach like yours so I would like to know the intuition!

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

When you get D accepted 49 seconds after the contest end...

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

    I feel you, though in my case I got F accepted 2.5 minutes after contest and the difference between it and the one I submitted in the last minute of contest was that I removed one dimension of dp which was completely useless in the problem but I only realized it 1 or 2 minutes after contest ends T.T

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

      My case is exactly the same as yours. I didn't solve it in time simply because I hadn't dealt with the case a[2i] != -1 && a[2i-1] != -1 properly QAQ Something even more annoying: I didn't solve any other problem, either. (Yet I've got rejected submissions) Sad...

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

    I only had 11min for C, and somehow got the correct solution. I coded it very quick, but while doing it I thought it was wrong, so I just stopped in last 1 minute :(

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

    I feel your pain.

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

258D - Little Elephant and Broken Sorting

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

    Sorry, it seems I even participated in the contest and solved it. My memory is not good.

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

    Ffs, stop using a meme in a wrong way. Do you really think the problem was stolen? Do you know how often it happens to invent an already existing problem?

    This overused meme/question makes sense only if several problems are from other contests, or if the statement looks very similar, including the sample test.

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

      Sorry, I didn't know the exact meaning of the meme. I just thought it's a coincidence.

      Though it's hard to come up with a non-existent idea/problem, it's a little sad to find a problem in AGC you already solved somewhere before anyway.

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

My approach for problem B. Suppose that tree is the last one that we burn, and assume that we arrive at it in the counter-clockwise direction. Let there be k trees within at which we change direction. It means that there may be either k or k + 1 trees in at which we change direction. For example:

The total distance travelled is given by the travel distance from 0 to plus twice the travel distance from 0 to each of trees at which we change direction. If we fix , there is no reason not to change directions at as many trees as possible; k should be the minimum between the number of trees in and the number of trees in , and we should use the "k+1" pattern if possible. So, for any particular we can calculate the greatest possible travel distance in O(1) if we precompute prefix sums of xi. Trying all possible gives an O(N) solution.

It is easy to apply the same approach for the case that we arrive at in the clockwise direction.

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

    Your solution is very clear and clean! Thank u so much for sharing!

    → Reply