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 duration: TBD (around 2 hours)

The point values will be announced later.

Let's discuss problems after the contest.

Open the problemset, read problem A

Multi-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 — 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)

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)

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?

I think many solutions for problem B are incorrect.

The counter-test for wrong solutions is:

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.

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.

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.

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)

you can read about complexity online

there are many resources

https://en.wikipedia.org/wiki/Circular_reasoning

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 failsAs 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))$$$.

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 ?

One operation is equivalent to either:

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

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 ?

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:

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

Sorry for the delay, now the editorial is ready.