B: the cumulative distribution function of the answer is when , you need to calculate it multiplying polynomials with divide&conquer. Then you find in linear time.

There were two intended approaches for problem J. One of them is to precalculate count of jimp numbers on blocks of length  ≈ 10⁷ and count the rest using the segmented sieve of Eratosthenes. The second approach is quite complicated. It involves dynamic programming which does sort of "sieve of Eratosthenes" to calculate how many numbers are either prime or not multiple of any of the first k primes. More details may appear later; we would also appreciate if the teams shared ideas of their accepted solutions without precalc.

Basically, you just need to run the segmented (or block) sieve of Eratosthenes. You can read more about it, for example, here. It works about 20 minutes for the authors to do all precalculations. Note that it's not necessary to calculate primes of form 4k + 1 and 4k + 3 separately, but just all jimp numbers together.

Did you write binary search + segment tree with arithmetic progression update for TLE solution?

Some implementation issues, I presume? The authors' solutions have complexity , too, and we do not know faster solutions. If someone does, please tell us here.

Our solution with dynamic CHT + parallel binary search also failed the time limit. After about 6 unsuccessful attempts of changing the number of iterations on the binary search, we decided to implement stack-like CHT + parallel binary search, which fit into time limit (even though it's the same complexity, binary searching on array vs set is faster).

Is it really necessary to put such tight TL constraints, so that one O(Nlog(N)log(1 / eps)) solution fails and another O(Nlog(N)log(1 / eps)) solution passes? (especially as the intended complexity of the solution was this)

E: The sum of distances is minimized on the centroid of the tree. So if an edge splits the tree into components of size k and n - k it adds min(k, n - k) to the cost. There are ways to split the vertices in 2 sets of size k and n - k, and k^k - 2(n - k)^{n - k - 2}k(n - k) trees with an edge connecting those 2 sets. For each such tree we add min(k, n - k) to the answer. The solution works in . It seems that the only reason for n ≤ 5000 is so I spend half the contest optimizing solution.

Could you please tell which particular problems had errors in their samples? We are only aware of typos in Notes section in problem C, where 3 values in sample explanation are wrong. But it seems that it didn't cause any troubles for many teams in passing problem C. (UPD: Div2 problems had some typos, too.)

Anyway, sorry for the inconvenience, we'll be more careful next time.

First, ask about all the vertices. Then for each i ask about all the vertices except the i-th one. If the area decreases, then i-th vertex is the vertex of convex hull. Notice that vertices of convex hull are in the same order as the vertices of the polygon. Now we know that convex hull is p₁, p₂, ..., p_k. To find the area of the polygon we need to subtract from area of convex hull areas of polygons of the form p_i, p_i + 1, ..., p_i + 1 - 1, p_i + 1. We can find those areas recursively with the same idea.

Will the problems be added to GYM?