That's one way to look at the probabilistic formulation. If you have broader probability space, for example, if operations are also chosen randomly, then the probability of big set being in the operation can be small, and I think it won't be O(n^2). I'm not sure how to show it, but my solution passed in the beginning, until they added a counterexample as yours, so if tests were generated using random at first, I think it shows that average complexity is not so bad.

Oh, that makes sense, thanks

Btw, in E merging without “smallest to biggest” optimization somehow passes the tests :)

a small correction

First note that any possible circular value consists of the ...”

Thats not true

Consider 5 elements and leave a3 element two times, then the circular value is a1 + a5

I dont think it matters though

Lol)

I'm not sure if anyone really uses policy based data structures, it is quite easy to write cartesian tree or segment tree etc. if you had done it enough times, or even write once, copypaste and modificate to the particular problem you solve. Of course you are welcome to do it if you want. Although it is quite feasible not to use bits/stdc++.h to reduce compile time (or even use autoimport tools, but I'm not familiar with such for c++)

Well, not all of your data structures are static. You have set ms; and you insert n elements in it, so in the first cases there is enough memory for your program. Why 1e6? You have ll dp[SIZE][30]; So you allocated 30 * SIZE = 3 * 1e7.

So what's wrong? You were trying to allocate more than 256 MB memory (3 * 10^7 long long array is 230 MB).

Is there a normal solution for Div.2 C that has complexity like O(len^2)? My only thought was to use bitsets with O(len^3 / 64)...

I felt that B was a really bad problem...

OMG really??? I've spent so much time thinking what's wrong!

In C problem: Why can't Bob choose 653, so he will get 653+141?

IF we have string with 'a' and n 'b'-s, it becomes 2*n 'b'-s and one 'a' after n operations. Then start from the end of the string and every time you will have string of this type, so you count operations you need and new number of 'b'-s