Hey, at least your region isn't doing worse than NA.

Congratulations to EDG!

LCK remains to be very strong over the years and the final is a close game that everyone was so nervous. Many thanks to both teams for presenting such an excellent game to us. I am pretty sure most contestants in CCPC Guilin were influenced by it because of staying up late though (oops).

GP of DRX when?

div.2 Contest Link: https://official.contest.yandex.ru/opencupXXII/contest/31242

std::set to store !9

I maintained segments of equal digits in std:;set(l,r,digit). Didn't have to debug tho

Yes.

the number of states in DP and the number of initial states in D&C affect the running time much :<

Exactly, I had a solution in the same complexity, but was afraid of constant factor from the very beginning and indeed my fears were justified cause I couldn't optimize it to pass :/ I hoped that optimizing from O(n^3 log n) to O(n^3) would be enough, but it wasn't :(

I've read the model solution (the one I've read was ugly as hell, don't recommend that) and understood the idea that I lacked to cut down the constant factor by 4. Basically in my D&C solution I was iterating through 4n intermediate states. n comes from iterating with one endpoint, 4 comes from iterating over cases which endpoints are bought. That 4 factor can be removed, because you can assume that you go through a state where the endpoint which is fixed is not bought, while the one you iterate with is bought (if your dp is appropriately written, because in the way I wrote it I needed a bit more sophisticated fix).

Here's what I did in J: build a suffix array for $$$S$$$, answer all the queries offline in order of increasing $$$k$$$.

Consider all substrings of length $$$\ell$$$ in the suffix array. All strings with shorter lengths can be considered as gaps, while all other suffixes will be split into several consecutive segments will equal prefixes of length $$$\ell$$$. Store these segments in a set (better yet, a treap).

Consider some $$$k$$$. If the number of segments in the set is less than $$$k$$$, we need to increase the current length $$$\ell$$$ (and reduce $$$k$$$ accordingly, since we've skipped some substrings). When increasing $$$\ell$$$, one suffix will be removed, and some segments will be divided into parts, we just need to find places with $$$\texttt{lcp} = \ell$$$. The last thing to do is to find the $$$k$$$-th segment in this set. It can be done by a treap or the built-in order statistics tree.

Since C is never placed above A we can decide each ? separately by comparing the number of (A/?) above each node with the number of (C/?) below. If we store the difference between these two at each node, we need to support operations subtree increment/decrement, path to root increment/decrement, and maintain sum of positive nodes. We can turn these into interval increment/decrement with the HLD/euler tour layout trick and use sqrt blocks to maintain.

There are at most $$$3^{n/3}$$$ shortest paths, so brute force.

You can iterate over the edges of smaller polygon in CCW and do two pointers to solve in $$$O(N+M)$$$.

Suppose we're on the edge $$$p\rightarrow q$$$. If you extend this segment indefinitely, it'll partition the larger polygon into left and right piece. The contribution of the current edge to the answer is $$$len(pq) * len(RightPiece) / len(LargerPolygon)$$$. Let $$$l$$$ be the index of the most CCW-point on the left piece, and $$$r$$$ on the right piece. These two indices can be maintained with two pointers. If you maintain the prefix sum of length of edges of the larger polygon, you can find the sum of length of edges between $$$l$$$ and $$$r$$$ in constant time. Then find the intersection between $$$pq$$$ and the edges containing $$$l$$$ and $$$r$$$ to account for the first and last edges being cut. If it's still unclear, you can refer to the code.

Did you mean E? I used $$$n$$$ Dijkstras as well. And right, even though it passed in the first attempt, I used more than 0.75*TL

Yes

180039582