rng_58's blog

By rng_58, history, 3 years 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. agc, Comments (42)
 » Open the problemset, read problem AMulti-source BFS •  » » Not sure I understand usage of this meme. Could you elaborate? Do you suggest that this was hard as for problem A?
•  » » » This problem was harder than usual A in AGC (the number of AC is also lower than usual A in AGC).
•  » » » » 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)
•  » » » » » 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.
•  » » » » » » 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)
•  » » » » » » » 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?
 » 3 years ago, # | ← Rev. 2 →   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
•  » » How to solve B correctly, after the idea of seperating coordinate?
•  » » » Go backwards and maintain a segment of positions which are winning for the second player.
•  » » 3 years ago, # ^ | ← Rev. 2 →   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.
•  » » » 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Oh my god. If this rejudged (I don't think so, though), I will get overwhelmingly worst performance of atcoder in my life.
•  » » » 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.
•  » » What were some of the wrong solutions?
•  » » » 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.
 » Special prize goes for ksun48 for solving F in $O(N^2)$.(Sorry, we missed bitset solutions...)
•  » » I have no idea how to prove my complexity, though...
•  » » » you dont have to prove the compelexity if its o(n^2) it is o(n^2)
•  » » » » » there are many resources
•  » » » » » »
•  » » 3 years ago, # ^ | ← Rev. 2 →   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
•  » » » 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.
 » Somebody pls explain why is the solution to C just checking if diameter%3==1 ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   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.
•  » » » oooh ok, thank you very much.
 » Can we get an access to the testcases of pB?I'm doubting the correctness of the judge.
•  » » You can find the link to testcases on the homepage! But they haven't uploaded AGC033 :( » 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?
•  » » U is moving up if you will consider classic grid $(row, column)$ coordinates.
•  » » » 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
•  » » » » If so, 'U' is naturally $(x,y) \to (x,y+1)$ as it appears in the coordinate system. Why $(x+1,y)$?
•  » » » » » You seem to read my mind, just wanted to post that in addition :)
•  » » » » » » Ладно, слился
•  » » » » » » » » Can anyone explain the solution for D ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   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)$.
 » Could someone explain the solution for B? TIA.
• »
»

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.

•  » » » Thank you.
 » Sorry for the delay, now the editorial is ready.