Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

rng_58's blog

By rng_58, history, 11 months ago, In English,

AtCoder Grand Contest 033 will be held on Saturday (time). The writers are yutaka1999.

This is the third GP30-rated contest in this season — see this post for details.

Contest Announcement

Contest duration: TBD (around 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

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

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

Open the problemset, read problem A

Multi-source BFS

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not sure I understand usage of this meme. Could you elaborate? Do you suggest that this was hard as for problem A?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This problem was harder than usual A in AGC (the number of AC is also lower than usual A in AGC).

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

        Implementation-wise — yes

        Algorithm-wise — it was the most standard problem ever on AtCoder. Me and my friends were kinda disappointed that AtCoder always managed to get some interesting easy problems for A while this one was completely obvious and not at all interesting (however I understand that from point of view of not red coders this may look differently, hence lower number of ACs)

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, I guess that still, it is AtCoder's style. You can just write BFS, or you can think a moment longer and just use a few loops to push distances in each direction. Looks fair.

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

            Writing BFS on grid is not something that is worth simplifying. Especially with something like that which I don't think makes things simpler and is more prone to errors (because it's hard to make a bug in bfs that you wrote 100 times)

            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              not worth simplyfying

              It's a matter of perspective, really. To you? Definitely. To me? Just as well. To those 500 or so people who didn't even solve it, though?

»
11 months ago, # |
Rev. 2   Vote: I like it +65 Vote: I do not like it

I think many solutions for problem B are incorrect.

The counter-test for wrong solutions is:

2 2 3
1 2
DRL
LDD

The correct answer is NO

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    How to solve B correctly, after the idea of seperating coordinate?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

      Go backwards and maintain a segment of positions which are winning for the second player.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    I think most solution of B are wrong and should be rejudged. rng_58

    Test Case

    3 3 4 2 2

    DLLR

    RDDD

    solution of mnbvmar and square1001 are both failing on this. Answer should be NO while both are printing YES.

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

      Tough situation, but I do believe many high rated coders would resubmit the right solution after some time after getting WA on separated coordinates approach.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh my god. If this rejudged (I don't think so, though), I will get overwhelmingly worst performance of atcoder in my life.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      The Atcoder format includes full tests at the time of submission. It is unfortunate when tests happen to be weak, but it would not be consistent with the rules to rejudge submissions after the contest is over.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    What were some of the wrong solutions?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My wrong but the accepted solution was just checking every direction separately. If we try to move left, then take all the lefts from the first player and all the rights from the second (provided that it will not move the stone out on the right). Obviously, it does not take into account the case above, where taking too many rights from the second player, could enable the first one, to move further right.

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

Special prize goes for ksun48 for solving F in $$$O(N^2)$$$.

(Sorry, we missed bitset solutions...)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I have no idea how to prove my complexity, though...

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +48 Vote: I do not like it

    I also found proving complexities of the (non-bitset) solutions to F non-trivial.

    I did find a case (see below) which shows ksun48's solution is definitely not $$$\mathcal{O}(n^2)$$$, allthough it does use similar ideas as the intended solution. On atcoder custom test, the case generated by the code below runs in 5983ms and uses an obsessive amount of memory (2210988KB).

    generator for testcase on which Kevin's solution fails

    As for the intended solution, I am not entirely sure about it's complexity, but I think I'm close, allthough it still feels a bit 'hand-waivy'. Anyway, I implemented a version of it based on google translate of the japanese editorial and based on the writers implementation. The only tricky part is the 'addedge'-function. My current hypotheses is that when this method is called recursively, it will always result in creating a new edge (never returning in line 53), which obsoletes the edge from which it is created. And it seems that obsoleted edges will never result in recursive calls. Therefore, each of the $$$m$$$ input edges (together with their shortened versions) can only be shortened at most $$$n$$$ times in total in lines 51 and 52. And each iteration of lines 61 to 68 will be paid for by changing an entry in the 'exists' array from -1 to some value (either directly, or in the recursive call), which can happen at most $$$n^2$$$ times in total. Therefore, the complexity seems to be $$$\mathcal{O}(n^2+nm)$$$.

    And as a final remark, I also saw an interesting accepted hashing + heavy-light-decomposition + segment tree implementation which looks like $$$\mathcal{O}(n^2log^2(n))$$$.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I agree that the complexity of my implementation is ambiguous. Here is a modified version. The array 'use' means 'is there an edge of G?' The problem of my first implementation is that when we shorten an edge a-c using a-b, a-c won't be shortened using a-x forever, but it might be shortened using y-c. Such a situation can be avoided using the array.

      By the way, my original solution is $$$O(NM\log N+N^2)$$$. This complexity is clearer. Here is rng_58's implementation.

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

Somebody pls explain why is the solution to C just checking if diameter%3==1 ?

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +34 Vote: I do not like it

    One operation is equivalent to either:

    • removing all leaves
    • removing all leaves except one

    In the first case, the diameter decreases by 2. In the second case, the diameter decreases by 1 if you choose a leaf that is on diameter (otherwise by 2). Hence this a single pile Nim game, and diameter = 1 is a losing position.

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

Can we get an access to the testcases of pB?

I'm doubting the correctness of the judge.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am extremely sorry, but

U is moving down and D is moving up? SERIOUSLY? I know I should have paid attention to that, but fuck, what is the reason for such a weird correspondence?

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

    U is moving up if you will consider classic grid $$$(row, column)$$$ coordinates.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      Makes sense, thanks for the explanation But still when I see 'U' I naturally think it's $$$(x, y)\to(x+1, y)$$$ as it appears in that way in the vast majority of cases

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

        If so, 'U' is naturally $$$(x,y) \to (x,y+1)$$$ as it appears in the coordinate system. Why $$$(x+1,y)$$$?

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

Can anyone explain the solution for D ?

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Let $$$down(X, r_0, c_0, c_1)$$$ be the largest $$$r$$$ such that the subgrid of rows $$$[r_0, r_0 + r)$$$ and columns $$$[c_0, c_1)$$$ has complexity less than or equal to $$$X$$$. Similarly, let $$$right(X, c_0, r_0, r_1)$$$ be the largest $$$c$$$ such that the subgrid of rows $$$[r_0, r_1)$$$ and columns $$$[c_0, c_0 + c)$$$ has complexity less than or equal to $$$X$$$.

    We can initialize $$$down$$$ and $$$right$$$ for $$$X = 0$$$ by checking which subgrids are monochromatic. $$$down(X = 0, r_0, c_0, c_1) = 0$$$ if the elements $$$[c_0, c_1)$$$ of row $$$r_0$$$ are not monochromatic. If they are, $$$down(0, r_0, c_0, c_1) = 1 + down(0, r_0 + 1, c_0, c_1)$$$. $$$right$$$ is computed almost identically.

    For $$$X > 0$$$, assume that we have already computed the values of $$$down$$$ and $$$right$$$ for complexity $$$X - 1$$$. Suppose that our first division must be a horizontal line. Then $$$down_h(X, r_0, c_0, c_1) = down(X-1, r_0 + down(X-1, r_0, c_0, c_1), c_0, c_1)$$$. Similarly, if our first division must be a vertical line, $$$right_v(X, c_0, r_0, r_1) = right(X - 1, c_0 + right(X - 1, c_0, r_0, r_1), r_0, r_1)$$$.

    Finally, $$$down(X, r_0, c_0, c_1)$$$ is equal to the maximum between $$$down_h(X, r_0, c_0, c_1)$$$ and the greatest $$$r$$$ such that $$$right_v(X, c_0, r_0, r_0 + r) \geq c_1 - c_0$$$. This definition can be transformed a little bit so the values of $$$down$$$ can each be computed in constant time. $$$right$$$ is computed almost identically.

    Runtime complexity is $$$O(H^2W + HW^2)$$$ for each value of $$$X$$$. $$$X$$$ is bounded by $$$log_2(H) + log_2(W)$$$.

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

Could someone explain the solution for B? TIA.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Horizontal movements are independent from vertical movements. Each dimension can be transformed to a 1-D problem in which each player's list of moves has elements {-1, 0, 1}. Aoki wins iff he can win in both dimensions.

    Suppose that the length of the one-dimensional board is $$$D$$$. At the end of the game, Aoki wins if the piece is on any location in $$$[1, D]$$$. Processing all moves backwards, if the interval of winning positions for Aoki is $$$[x, y]$$$, it should be updated to:

    Value Aoki Takashi
    -1 $$$[x, min(y+1, D)]$$$ $$$[x+1, y]$$$
    0 $$$[x, y]$$$ $$$[x, y]$$$
    1 $$$[max(x-1, 1), y]$$$ $$$[x, y-1]$$$

    If the interval becomes empty at any point, we can terminate immediately and declare Takahashi as the winner.

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

Sorry for the delay, now the editorial is ready.