AFAIK it is 5 hours long, right? :P

bump

There will be live grading ?

When will you publish results?

UPD: Published already

Is there a reason why tests are given in groups? It feels a little disappointing getting 12/100 points when only 2 testcases failed...

Thanks for the contest anyway, the problems were interesting as usual.

What was the solution of Ogledala?

I've implemented O((N + Q)(logM)²) solution but it turned out to be too slow, probably due to giant constant factors :(.

I used bellman-ford to solve a system of difference constraints in problem Kovanice. It seems it's too slow and got TLE.

Can anyone tell me how to solve it correctly? Thanks very much.

Waiting for the official editorial...

The third problem is so difficult. I only came up with a very naive solution that uses balanced tree and heap, which runs in , obviously will get TLE

UPD: I've got the way to reduce a log factor. Notice that when an interval breaks we get two new intervals of same length or with difference 1. And it's easy to see that if every sub intervals break again there will be still at most two possible lengths. Then, we only need to record how many intervals have a certain length, while the exact place could be found further separately(the new subproblem is what is the K-th insertion for an interval originally have length x), also need to pay attention of that slight difference of one: one shorter interval appears at front may generate length N-1 and N, while a little bit longer one after it may got N and N+1, and we need to be especially careful when dealing that length N.

My solutions for SIR and CVENK (the two medium problems):

SIR: First, we find the convex hull of peppers in and discard all other peppers. We can use 3 pointers now; two of them are endpoints of the cut and if we move one endpoint E₁ ccw along the perimeter of the cheese, we can recalculate the first possible choice for the other endpoint E₂ (since the cheese is convex, it means the choice with the maximum area). The third pointer P is at the pepper that makes it impossible to make the area bigger by moving E₂ — if we look at the peppers from E₁, it's the leftmost vertex we see. The initial value of P and then of E₂ for some choice of initial E₁ (E₂ depends on P, P doesn't depend on E₂, so we always re/calculate them in this order) can be found using vector cross products — see my code for details, the area A of the correct part of the cheese can also be found using them; as we move E₁ ccw, P and therefore E₂ never move cw, which means we only need to recalculate them in O(N + M). As we move E₂ or E₁, we also need to recalculate A by adding/subtracting the area of some triangle.

CVENK: The fractal is a tree, so we want a compressed version of it that contains all tourists. When we know the tree, we can just root it, count the number of tourists in the subtree of each vertex, find the vertex that doesn't have more than N / 2 tourists in any of its sons' subtrees or outside of its own subtree (if it did, then one of its neighbours gives a smaller answer); that is the centroid and it's sufficient to take either if there are two (there are at most 2), it's the optimal vertex and we just need one DFS from it to compute the answer. It's a well-known problem. For finding the tree, I rewrite the binary representation of (x, y) to a sequence of straight paths from (0, 0), alternating down and right. If we store the sequences that change direction or end at a vertex v of the so far constructed tree, we can look at all that change direction to horizontal, store the lengths of these straight horizontal paths in a set, make new vertices at their endpoints and store for each sequence that it changes direction at a new vertex, with one less straight path in it; similarly for vertical ones. The tree can be constructed recursively this way. Time complexity: there are at most 30N straight paths in each sequence; plus some log-factors from STL map/set, it's . Finding the answer then only takes linear time.