The key idea is to solve the problem without the strings "A" and then iterate over the number of them to glue to words ending with 'S'.

And that subproblem is just some tedious case-handling:

"..SA" + "D..": connect min($$$cnt_{SA}$$$, $$$cnt_{D}$$$) words to each other and subtract 1 if the set of indices of words ending with "SA" is equal to the set of indices of words starting with "D" (they got connected into a cycle). Same for "..S" + "AD..".

And the only case left is when all words got connected into one cycle. Subtract 1 more if all possible connections are made, union of sets "D.." and "AD.." is equal to union of sets "..S" and "..SA" and there were no subtractions in previous connections.

Copy-paste from recent JAG contest.

Let's emulate the specified in the statements algorithm, but instead of removing overlapped boxes on step 2, we will just skip this step and then for every processed box we will first check whether it was removed previously or not. If it "was removed" just skip it, otherwise select it.

So we need to maintain some structure that allows adding new selected boxes and checking whether the current box overlaps enough with previously added boxes.

Let's divide all the plane into square cells with side equal to $$$S$$$ and store these cells in the unordered map, i.e. for each non-empty cell we will store a vector of selected boxes inside this cell. Then to check if current box is overlapped with some other, we just need to go over 9 neighboring cells and calculate IOU with all boxes in those cells straightforwardly. The key idea is that there will be not too many boxes inside one cell because every pair of selected boxes should have $$$IOU <= threshold$$$.

It passed in 1.2 out of 10 sec.

I think I can make a case where this TLs :) Create a few loops of zeros with coprime lengths, and add zero edges from 0 to one vertex in each loop, and one edges from one vertex in each loop to 1.

here

Sounds too complicated

1. Remove all edges going to vertices having no path to 2.
2. Maintain the set of vertices you can be at aftet going through $$$k$$$ edges. It's easy to recalculate the set for $$$k+1$$$ in O(V+E), just consider all minimal edges and go through them.
3. Build the set for $$$k=V+eps$$$, if you notice during the computation that vertex 2 is in your set at some point, restore the path and break.
4. Otherwise the answer is cyclic. Restore path for any vertex in set with $$$k=V+eps$$$, and find preperiod and period there.

Integer overflow at Out function. My solution is the same as you, but I iterated $$$3n+50$$$ times.

I did the same bug, but I fixed it during contest :)

$$$dp[i][j]$$$ — the minimum price to put $$$i$$$ letters and have latest $$$j$$$ letters copied. $$$j = 0$$$ means the last move was to put a single letter.

From any state $$$dp[i][j]$$$ you can put a single letter and go to $$$dp[i + 1][0]$$$, paste the current copied string into its next occurence and go to $$$dp[nxt[i][j]][j]$$$ (filling the rest of letters by single insertions) or copy the next $$$k$$$ letters from somewhere earlier (if there was such an occurence), paste it immediately and go to $$$dp[i + k][k]$$$.

$$$nxt$$$ and occurrence checks can obviously be precomputed with z-function.

It works for all $$$n$$$. Just build a staircase:

[(1, 1)]
[(1, 2) (2, 2)]
[(1, 3) (2, 3) (3, 3)]
[(1, 4) (2, 4) (3, 4) (4, 4)]
...

(i, j) means, you place block of $$$(i, j)$$$, with $$$j$$$ in the opposite side of sight.

My solution works in 0.879s. I think it was intended O(N log N) with small-to-large.

We have just LCA + DSU that passes in 1 second. I guess you can make it sub-nlogn but idk if that will be faster :)

We didn't find anything about it, either, so we assumed this stuff can happen (and I just checked that the protobuf compiler consumes this description just fine). I don't know if I'm more relieved or surprised that such a case was not in the testset. :P

I thought that asking Snark in Telegram was most reliable, but that also didn't work today.

Let $$$v_1, v_2, \ldots, v_k$$$ be the sons of the root. Let $$$l_i$$$ be the depth of the deepest taken vertex in the subtree of $$$v_i$$$ (possibly $$$l_i = 0$$$). It turns out that the second player wins if and only if $$$max(l_1, \ldots, l_k) = max_2(l_1, \ldots, l_k)$$$. It can be proved using the fact that we can remove all vertices which are ends of some diameter (at least I thought this proof is correct during the contest). Implementation is pretty standard, complexity is $$$O(n \cdot log(n))$$$.

Code brute -> notice the pattern.

Print 2 when n or m is 1, else 2n + 2m — 4.