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

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.

• +154

 » 11 months ago, # |   +80 Open the problemset, read problem AMulti-source BFS
•  » » 11 months ago, # ^ |   0 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, # ^ |   0 This problem was harder than usual A in AGC (the number of AC is also lower than usual A in AGC).
•  » » » » 11 months ago, # ^ |   +10 Implementation-wise — yesAlgorithm-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, # ^ |   0 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, # ^ |   +5 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, # ^ |   -10 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 →   +65 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, # ^ |   +34 How to solve B correctly, after the idea of seperating coordinate?
•  » » » 11 months ago, # ^ |   +54 Go backwards and maintain a segment of positions which are winning for the second player.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +24 I think most solution of B are wrong and should be rejudged. rng_58Test Case3 3 4 2 2DLLRRDDDsolution of mnbvmar and square1001 are both failing on this. Answer should be NO while both are printing YES.
•  » » » 11 months ago, # ^ |   +18 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 →   0 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, # ^ |   +45 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, # ^ |   +20 What were some of the wrong solutions?
•  » » » 11 months ago, # ^ |   0 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, # |   +68 Special prize goes for ksun48 for solving F in $O(N^2)$.(Sorry, we missed bitset solutions...)
•  » » 11 months ago, # ^ |   +13 I have no idea how to prove my complexity, though...
•  » » » 11 months ago, # ^ |   -74 you dont have to prove the compelexity if its o(n^2) it is o(n^2)
•  » » » » 11 months ago, # ^ |   -76 you can read about complexity online
•  » » » » » 11 months ago, # ^ |   -69 there are many resources
•  » » » » » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ | ← Rev. 2 →   +48 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 failsint nstem=MAXN/2,nleaf=MAXN-nstem; int n=nstem+nleaf; assert(n<=MAXN); int m=nleaf+nstem-1; assert(m<=MAXM); printf("%d %d\n",n,m); for(int i=0;i
•  » » » 11 months ago, # ^ |   +20 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, # |   +5 Somebody pls explain why is the solution to C just checking if diameter%3==1 ?
•  » » 11 months ago, # ^ | ← Rev. 3 →   +34 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, # ^ |   0 oooh ok, thank you very much.
 » 11 months ago, # |   +13 Can we get an access to the testcases of pB?I'm doubting the correctness of the judge.
•  » » 11 months ago, # ^ |   +18 You can find the link to testcases on the homepage! But they haven't uploaded AGC033 :(
 » 11 months ago, # |   0 I am extremely sorry, butU 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, # ^ |   +7 U is moving up if you will consider classic grid $(row, column)$ coordinates.
•  » » » 11 months ago, # ^ |   -15 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, # ^ |   +43 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, # ^ |   -10 You seem to read my mind, just wanted to post that in addition :)
•  » » » » » » 11 months ago, # ^ |   +93 Ладно, слился
•  » » » » » » » 11 months ago, # ^ |   +58
 » 11 months ago, # |   +4 Can anyone explain the solution for D ?
•  » » 11 months ago, # ^ | ← Rev. 3 →   +10 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, # |   +5 Could someone explain the solution for B? TIA.
• »
»
11 months ago, # ^ |
+8

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, # ^ |   0 Thank you.
 » 11 months ago, # |   +17 Sorry for the delay, now the editorial is ready.