H:

If segment is short enough (r-l <= 1500), just check all the numbers from it. Otherwise, order(a) is small enough, check all a^k.

G — find some corner square first. You can find one of it's corners as vertex with degree 2, two more corners as neighbours of this vertex, and last one as other common neighbour of vertices #2 and #3. Now do some sort of BFS — for every edge of a grid which you already have, let's say it is connecting vertices A and B, check if there exist such pair of yet unused vertices C, D, that there exist edges A-C, B-D, C-D. It will give you new square, and you can get exact position of C and D.

J: It is easy to show that the problem can be solved in O(m*2^k): iterate over all subsets of optional vertices and find MST of induced graph. Next, we generated multiple random graphs and found out that optimal subset always have <= 4 optional vertices. So our final solution is O(m*C(k, 4)).

Also, I believe I can solve F in with 2D structure, but it is so hard to implement :(

D: First do a binary search on answer, that is width. Then DP. I did DP in two steps. First precomputation and then construction. In precomputation step, DP parameter was: DP[i][j] which means: how many of log2 is required if I use j number of log1 to construct 2^i rows in total. Using, O(n^2) loop, you can construct: DP[1], DP[2] and so on.

Then you can find out your answer using binary representation of L (and corresponding DP[] array).

Let's do binary search by the answer.

Let's say we have fixed answer M and we want to check if we can achieve it. This task is solvable using dynamic programming. Let r(x,p) denote the smallest number of sticks of the second type, that we need to build exactly l blocks of size M or bigger. We will iterate through all possible number of sticks of the first type and do our transitions. Such solution works in O(n^3logN) time per test case and surprisingly passes the TL.

There exists a cool optimization, which makes our code to work in O(N^2logN) time. Let's calculate, how many iterations will our DP make in all states. This number is equal to x*l*((x*a+y*b)/l)/a. L = ((x*a+y*b)/l) is the maximum size of our block, an we will make no more then L/a iterations in each state. It's easy to show, that x*l*((x*a+y*b)/l)/a = x*x+x*y*b/a. Now let's do our trick. If b is bigger then a — let's swap them, and it's easy to see, that our DP will work in O(N^2) time in this case

For fixed binared width: dp[c1][c2] — using c1 first type, c2 second, what is maximum pair (finished rows count, remaining in last not finished row)

Binary search on the answer reduces this problem to answering whether the point (x, y) lies outside or on the border of the Minkowski sum of l copies of the convex (more like "concave" in this case) hull of the polygon formed by the points (p_x, p_y) such that ap_x + bp_y ≥ tentative_answer and this sum is homothetic to the polygon itself. The complexity is per testcase.

http://mirror.codeforces.com/blog/entry/10964

Statistics of this approach:

SPbSU Testsys:   2   /  21
OpenCup ejudge:  5   /  40
MIPT ejudge:     1+1 /  80
Yandex.Contest:  3+1 /  14
-----
Total:          11+2 / 155

Here, x+y / z means there were z OKs, x teams used this approach, and y more teams tried this after accepting a normal solution.

That's definitely an improvement comparing to my previous attempt to put an Easter Egg into an ACM-style problem, where only one team passed one test using it.

Kudos to the people who got it!

You should twice apply the operator and you will have 3 vectors and 3 points that defines a plane. Normal — is the axis. Angle you can find between vectors (from center of circle to two neighbor points on circle) Circle in this plane.

In B we had the following solution. First with FFT we calculated all deltas we have, so for each delta [0..400000] we can tell if there are xi and xj that xj — xi == delta. Now we need to find these xi and xj for each delta. We randomly generated i, j and marked the delta as found. Then we just found all other deltas (not found) naively. That is hacky but got AC. Interested in the other solutions.

O(C²) solution, where C -- maximal time in input, using bitset optimisation, worked in 0.35 seconds.

This solution got AC in upsolving.

This task is about finding such a pair of people for every difference (it can take values between 0 and 400000) that t[j] — t[i] equals this difference if there is any. Let's fix a constant K, consider a time interval 0..400000 divided into blocks of length K.
Each block we represent as bitmask (K is small enough to fit in int), where 1 means there is a person to come in this time. Next, for all pairs of blocks we precalculate array p[mask1][mask2] — a mask of differences between the first and the second blocks, which can be obtained if we concatenate blocks (it can be easily done in O(2 ^ (2 * K)) time and memory). Note that if we can find a block for given difference which contains the first element of a pair, which gives this difference, we can establish the pair in O(K). Now we iterate over all pairs of blocks, in O(1) find a mask of differences for this pair (using p for this), and try to update the answer for each found difference. To do it fast, we need firstly to iterate over all pairs with equal distances between first and second blocks. For small differences (< K) use brute force.

Complexity: O((N/K) ^ 2) + O(2 ^ (2 * K)) time and O(2 ^ (2 * K)) memory. I chose K = 12.

It is open in yandex contest from the end of the contest

Div 1

Div 2

You can speed up both parts of your solution.

For solve_interval, you can check the orders of elements instead of finding the discrete logarithm (see this thread for details).

For solve_powers, you can get rid of the unordered map and just iterate until you get 1.

Either of these changes will perhaps be sufficient.