Блог пользователя rng_58

Автор rng_58, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +61
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did you make beta version main one?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    (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.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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...

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 :(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I feel your pain.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +124 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      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.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

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.