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

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

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.

What were some of the wrong solutions?

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

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

int 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<nstem-1;++i) { int a=i,b=i+1; printf("%d %d\n",a+1,b+1); }
for(int i=0;i<nleaf;++i) { int a=nstem-1,b=nstem+i; printf("%d %d\n",a+1,b+1); }
for(int i=0;i<nleaf;++i) { int a=0,b=nstem+i; printf("%d %d\n",a+1,b+1); }
for(int i=0;i<nstem-1;++i) { int a=i,b=i+1; printf("%d %d\n",a+1,b+1); }

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

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.

You can find the link to testcases on the homepage! But they haven't uploaded AGC033 :(

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

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

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.