Um_nik told me this bubble cup problem after the pre-final contest. I camp up with this problem from a problem called Constellation in JOI2011-2012 around 2015-16 when I am in high school. So SAD...

B: lengths of borders can be grouped in $$$O(\log(n))$$$ arithmetic progressions. When you add a new character, go through them from longest to shortest. If you need to delete element, do it naively, if you don't delete the first 2 elements in arithmetic progression, you don't need to delete any elements in it, so skip it.

Solution to G was discussed in 300iq's chat a few days ago.

G: n^4 is a simple knapsack, right? In order to make it faster I do "knapsack without one element" in D&C manner in O(n^3 log n).

K: for requests with x>sqrt(n), iterate over depths d(a)+y, d(a)+y+x, ... and maintain a separate data structure for each depth (vertices go in the dfs order). For requests with x<sqrt(n), maintain a separate data structure for each (x,y) pair (vertices go in the dfs order). In both branches, we need an "imbalanced" data structure which has O(n) updates and O(n*sqrt(n)) queries, or vice versa. This can be done by splitting into sqrt(n) blocks (instead of using a Fenwick tree which we got TLE with), so that the less frequent operation is done in O(sqrt(n)), and the more frequent in O(1).

EDIT. And to avoid getting MLE, for requests with x<sqrt(n), we iterate over x on the outside so that we only O(n) memory.

On the workshop we didn't have any troubles with $$$O(n\sqrt{n} log(n))$$$ solution, it passes in half of TL. Code.

UPD: I just checked in opencup's Y.C, it is still half TL.

O(n^1.5) is the intended solution just as Petr said. We set the TL to make it difficult to let O(n^1.5logn) pass while O(n^1.5) won’t need much adjustment. I didn’t notice KAN pass it with a O(n^1.5logn) and the TL hasn’t changed in the OpenCup as far as I know.

I sent a solution with centroid decomposition, with less effort to model. blog

Ans = (n — 1) * 4 + (n — 2) ^ 2 * sqrt2

I think it refers to the start index of Sx.

Yes, you've got that right.

I'm one of the coauthors of Problem M. I'd like to share some stories behind the scene.

When we made up this problem set, we wanted to add a randomized problem simply cuz random & approx algorithms are the main research fields our TCS group. Then we just come up with color coding, which is not yet widely known in competitive programming community.

Before this problem was made, there was a problem another contest (2019 China Multi-University Training Contest) asking to find k-path. In that problem, a simple $$$O^*((2e)^k)$$$ color coding could pass, but during that contest many participants passed it with various heuristics. So we just wanted to make another color coding problem, which couldn't be easily passed by heuristics. This is M in this contest.

The basic idea of M indeed came from the $$$O^*(4^k)$$$ algorithm for finding a k-path by combining color coding and divide-and-conquer. The constraint $$$k \leq 10$$$ is mainly because of two reasons: one is we can just split to two 5-paths and perform a case analysis, thus simplifying the solution; the other is that it provides enough budget for the constraints on the # of vertices and edges.

To avoid heuristic solutions, we made it to find k-cycle and carefully tuned the constraints. We successfully hacked many common heuristics (among which the most difficult one to hack is to precompute a "relaxed" answer which allows cycles with repeated vertices and use this information to prune during exhaustive search). Actually there is still one solution we haven't hacked: compute biconnected components and use the aforementioned heuristic on each component. But we thought nobody would come up with such solution during contest. :P

Yeah, we were able to pass M with color-coding with a couple constant-factor optimizations:

1. When searching for P points it's actually ideal to assign P+1 or P+2 colors rather than P -- traveling salesman is 2x slower but probability of success is quite a bit higher.
2. Instead of initializing with a vertex and searching for the remaining K-1 points, you can initialize with an edge and search for the remaining K-2 points. Since M and N have the same bound each edge is just as likely to be part of a correct set.

It is not good that it is hard to get OpenCup login. But your logic is weird. Many people participate in OpenCup, so this blog definetely has an audience on CF. Moreover, CF is a go-to place for any cp related discussions. There are a lot of local contests (for example ICPC regionals) which are also not open for everyone and are discussed on CF. Is that bad too?