this ??

What's the meaning of 'sofa'? I can't understand

and also no time conflict

The overlap is like 5 minutes and there's usually nothing to do in the last x minutes of the contest, so it's not that bad.

You can still take it instead.

Done. :p

I believe you have plenty of time to eat during the contest.

It is also giving tle for just insert and erase in multiset. The submission which is correct gives tle and submission which is logically incorrect is accepted. This makes no sense.

See this https://en.wikipedia.org/wiki/Langford_pairing

I think B appears at least yearly in one contest (it's been part of the Romanian folklore for at least 12 years). In mathematics it's even better known. I find it very odd that atcoder would use such a problem. Also, B was significantly easier than C, I find it strange they had the same score

Here's a simple way to solve the problem:

Let's first say Vertex $$$N+i$$$ as $$$i$$$ for simplicity, and all we need to do is place 2 vertexes with value $$$i$$$ such that it forms the required tree, where the weight of each vertex is its value.

Now, take the first case when $$$N$$$ is odd, Place $$$1$$$ as the root of the tree, and for each $$$i$$$ where $$$i$$$ is even, connect with $$$1$$$ the following $$$2$$$ branches, $$$(i+1)-i-$$$ and $$$i-(i+1)-$$$. This would complete the requirement for all $$$i$$$ and $$$i+1$$$ such that $$$i$$$ is even. Next, we are only left to satisfy $$$1$$$ which could be simply done by connecting it to the leaf of any of the branches connected to $$$1$$$.

Next case, when $$$N$$$ is even, We can do the above process to satisfy each vertex up to value $$$N-1$$$. Now, we just need to satisfy the criterion for vertex $$$N$$$ as well. We could show that these two vertexes must not be on the same branches, otherwise we wouldn't be able to satisfy vertex $$$N$$$, let's say they are on different branches, then, 1 must lie on the path between them, So, $$$1 \oplus x = N$$$ where $$$x$$$ is the weight of other vertexes on path, so, $$$x = N+1$$$. Another observation would be the following, that $$$N$$$ must be connected to the direct children of $$$1$$$. So, All we need to do is find two vertexes $$$j$$$ and $$$k$$$ $$$(1 \lt j,k \lt N)$$$. such that $$$j \oplus k = N+1$$$.

Good question. It took me probably over an hour to figure it out.

If $$$N$$$ is a power of $$$2$$$, there's obviously no solution. Otherwise, there is a solution. For $$$N$$$ odd, it's easy, just make paths $$$(2k+1)-(2k)-1-(2k+1+N)-(2k+N)$$$ and add $$$N+1$$$ somewhere to the bottom.

For $$$N$$$ even, we have to do something with the $$$(N, 2N)$$$ pair. For example, a path $$$(N)-(N+1-2^k)-(1)-(2^k)-(N+N)-(N+N+1-2^k)-(N+1)-(N+2^k)$$$ can do it, where the $$$k$$$-th bit in $$$N$$$ is $$$1$$$ ($$$k > 0$$$). This means we can't add all the remaining pairs $$$(2k, 2k+1)$$$ just like for $$$N$$$ odd, since we broke the pairs $$$(2^k, 2^k+1)$$$ and $$$(N-2^k, N+1-2^k)$$$. Fortunately, we can add $$$(2^k+1, N+2^k+1)$$$ from the first pair as $$$(2^k+1)-(1)-(2^k)-(N+2^k+1)$$$ and $$$(N-2^k, N+N-2^k)$$$ from the second pair as $$$(N-2^k)-(N+1-2^k)-1-(N+N-2^k)$$$, and the rest can be handled like for $$$N$$$ odd.

sir, can u plz explain in detail(easier version) , i'm new in cp... thanks!!

From the editorial, it seems to me like this wasn't intended to pass, with or without prewritten code.

Wow, checked tourist's solution and it was apparently possible to squeeze NTT in.

You probably already checked the editorial, but the intended solution is just one loop in linear time, and the NTT solution misses a key idea, so maybe the opposite should've been done and constraints raised further to disallow all kinds of NTT?

Sorry we didn't know the existence of such solutions. Our intended solution is simple $$$O(n log n)$$$.

Simple reduce to $$$O((N + M)log(N + M))$$$ by Taylor: $$$(\sum(\frac{n - i + 1}{i!}x^i)^m = (\sum(\frac{n + 1}{i!})x^i-\sum(\frac{1}{i!})x^i)^m=(n + 1 - x)^me^{mx}$$$.

Easily to apply NTT here.

If I had to be really picky, I would object to B and C being constructive graph problems. But you're right, I enjoyed every single one that I solved and also loved revealing the secrets of F.

I can't comment on E or F and I liked C and (in principle) D, but B shouldn't have been used, since it's too standard. Also, A and maybe D allowed me to get an unfairly high place.

That's the limitation of system test format. Unless we expect such solutions in advance, we can't prepare counter-tests for them.

Uploaded.

I haven't played for so long... it seems like a card effect, which one?

And another one

Let $$$f(k)$$$ be the number of recursive calls of Go when you call Go once with $$$to - from = k$$$.

Then $$$f(k) = 1 + 2(f(1) + ... + f(k-1))$$$ and $$$f(k) = 3^{k-1}$$$.

May be slightly easier solution. Consider two cases: (a) the sequence begins with 2 equal numbers, (b) the sequence begins with 2 different numbers. In first case the sequence will look like: "x x 0 x x 0 ..." and in the second case it looks like "a b c a b c ...". Now the only thing is to handle the "last number = first number". But instead of that, you can observe that, "if you pick two unequal numbers from the given numbers, they will always be adjacent". So pick the largest number X and the smallest number Y (if all the numbers are equal, following solution still works). Consider them as first two numbers, and try to find all the next N — 2 numbers. Now just check if the count of the numbers in this sequence matches with the input. Also check if the last two numbers yield the first number.

Oh, I found it was wrong. Here is a hack data:

4
1 1 2 2

Obviously it is impossible.

It can be solved in $$$\mathcal O(n)$$$ though. You can simply answer No once the map has $$$4$$$ elements.

i visited the vertices in the order of their new degrees, pls some testcase for which my algorithm fails?

The same place as the Japanese one

Protip: Read the sentence in red.

Me neither, couldn't figure out how to do transition concerning the last dimension of the dp state in the tutorial.

This is pretty tricky to get right. Think of this that way. Every cycle of desired shape has some start and end which are of the same parity. It contains all elements with the same parity that are between them and moreover some more consecutive elements of the other parity which are symmetrical with respect to the middle of the cycle. We will "detect" such cycle just after the end of the other parity part.

We are at some position $$$p$$$. Assume that x is the number of last positions with the same parity as $$$p$$$ that were deleted. That is $$$p, p-2, p-4, \ldots, p-2x+2$$$ were deleted, but $$$p-2x$$$ wasn't. Assume that y denotes the same but for the other parity, that is $$$p-1, p-3, \ldots, p-2y+$$$1 were deleted, but $$$p-2y-1$$$ wasn't. Assume x>y. This is the moment where we want to bound number of consecutive appearances of deleted positions for the future in order to omit the forbidden cycle. If $$$y=0$$$ then we won't get here any hypothetical cycle, so we don't have to do anything. If $$$y \ge 1$$$ and $$$2x \ge k+3$$$ then we know that if we delete next $$$\frac{k - 2y + 1}{2}$$$ elements with the same parity as $$$p$$$ then we get this forbidden cycle, so we keep $$$x + \frac{k - 2y + 1}{2}$$$ as the bound on the length of current length of consecutive deleted elements with the same parity as $$$p$$$.

One more thing to note is that this is one bound for one parity, but what about the other parity? Maybe it has some bound on its length as well, so we should keep two bounds in state? Actually it is not necessary since we can keep the bound just for the parity that currently has longer suffix of deleted elements.

Maybe my code can help: https://atcoder.jp/contests/agc035/submissions/6384104 but I used a bit different naming there. $$$b$$$ corresponds to $$$x$$$, $$$c$$$ to $$$y$$$, $$$d$$$ to that bound, prefix $$$prv_$$$ means it is from previous state, prefix $$$n$$$ stands for $$$\texttt{new}$$$ and stands for new value of that variable. $$$\texttt{dp[i][b][c][d]}$$$ stands for the number of states so that I considered $$$i$$$ positions, $$$x=b$$$, $$$y=c$$$ and the bound on the length of longer sequence of deleted elements is $$$d$$$ (meaning that, if it reaches $$$d$$$ then the cycle is completed, so $$$dp[i][d][c][d]=0$$$). I did this dp in "forward" manner instead of more popular "backward" manner. Ignore any ifs regarding debugs because they are successfully polluting this.

Hope I helped.

Ok, that explains why my heuristic solution is fast enough, this is the worst case for it. It deals with much fewer states, but at least it's "much fewer than Catalan numbers" instead of "much fewer than factorial".

Nonisomorphic ways of doing this process indeed correspond to binary trees with n-1 leaves, so it indeed is some Catalan number. It can be seen by marking spaces between elements and when we are removing some element we are merging two consecutive spaces.

I noted this during competition, but somehow didn't realize that this is only 35 mlns...