C: Possible leaders are those who have at least (n — 1)/2 edges. Now if leader is fixed, it's optimal to put every his friend to separate team and to put others we may find matching in O(NM). There are at most O(m / n) leaders so overall complexity is O(m^2)

My explanation is probably hard to understand but anyway:

F: notice that letter at position i goes to either i/2 or (i — 1)/2 + n / 2. Now if you will see it in reverse it is from i to 2i mod (n — 1).

Now we have letters on the cycle in s and letters in t in same positions. We need to get possible cyclical shifts that will move string generated from s to string generated from t. Using prefix function (or probably z function works too) we get possible shifts (they give some reminders module len of the cycle which is divisor of phi(n — 1)

Code

Choose x such that no matter what happens, the value decreases to at most (2 / 3)S.

so we pre-compute these values in double. You should be very careful to avoid precision issues.

What did you do to avoid precision issues? I used a lot of computer time to generate tests where one division result is very close to a whole number... (I am the author)

B looks quite easy idea-wise. Let (u, v) be an edge, and let T(u, v) be a tree rooted at v we get when we remove the edge. Note that T(u, v) and T(v, u) are different.

Then, find the probabilistic distribution of the depth of T(u, v). This can be done by some integrations, and it will be piecewise polynomial.

To compute the answer, for each edge (u, v), find the expected depths of T(u, v), T(v, u), and the expected length of the edge (u, v), given that the midpoint of the diameter lies on this edge. Again this can be done by some integrations.

Note that we need "all-direction DP" to achieve O(N⁴).

Could please explain how to apply sqrt? To requests and store best pairs(max staircase 1, max staircase 2)?

Intended solution for J is O(n log n) btw, though with a huge constant. I'll describe it in comments later.

Notice that WLOG we can assume that the a_i are the inner n - 1 points of the broken line graph, because there should a change of slope in a point a_i if it's λ_i is nonzero.

Also, we can easily calculate the needed λ_i-s from the changes of slope of the broken line. Now, just check if the graph of the sum using those λ_i-s and a_i-s is indeed the broken line from the input. You can check only two points from each linear segment and ray, because two linear functions are equal when they agree on two points. Equality checking can be done exactly or with high probability using fraction arithmetic or some other methods.

What interests me the most about this problem is the weird nature of the precision issues we have been experiencing when using floating point operations. Why exactly is it bad to choose the a_i-s for checking the equality of the functions? What is the maximum error in calculations and how to make sure it isn't reached?

The intended solution utilizes the following fact. Consider the sequence of contiguous groups of people from the same team. Then it is true that this sequence is modified only via extending one of the existing groups by a new person from the same team, or by creating a new single-person group at the end of the line.

Now store two data structures: a segment tree keeping sizes of all groups in order from head of the queue to its tail, and a vector of group indices for each of the teams. When a new person comes, first find the group he would get into if there was no restriction of having a neighboring teammate, and then, using a single lower bound query in the corresponding team vector, move to the closest group of people from his team.