Reminder: Contest starts in 1 hours. Now # of registerants is 351.

Were you the writer?

I used binary search to find element on day d1.

If both left and right sum will turn out larger than needed, decrease high, and vice versa for smaller. If one is larger, the other smaller no solution is possible.

Left and right sum with one given element can be checked by computing min and max possible sum with n*(n+1)/2

Instead of moving tokens one by one at each time, you can imagine you move all tokens simultaneously, since if two tokens cross while moving, you can just uncross them.

Here's the max flow graph.

Create two nodes for every (node, time) pair (let's denote this a(n, t), b(n, t), meaning node n at time t). Create a source and sink. All edge capacities in the following will be 1.

• For every node x with a token, connect source to a(x, 0).
• For every node x without a token, connect b(x, t) to the sink.
• For every edge in the graph (x, y) and every time j, 0 ≤ j < t, connect b(x, j) to a(y, j + 1) (and similarly b(y, j) to a(x, j + 1).
• For every node x and every time j, 0 ≤ j < t, connect a(x, j) to b(x, j), and b(x, j) to a(x, j + 1).

The max flow in this graph is the answer.

You need two classes of nodes a, b because you need to encode the constraint "every node only has 1 token at each time".

I will try to give a hint. Probably, that will be enough.

Every time you see a large problem space, you don't want to go through all of that space, but you want to consider only special points.

In the case of this problem the space is the days: [1, 2, 3, ..., d1 + d2].
We don't want to go through all of that space, but we want to consider only one special place.

Good question! One (admittedly weak) reason is that it is a natural way to reduce the number of edges in your flow graph, which helps in doing worst-case analysis for the maxflow algorithm (Dinic runs in time E^(3/2) for unit-capacity networks, for example).

Vary the number of words (say d1) learnt on the last day of the sem1 from 0 to w1. Let the number of words learnt in the first day of the sem2 be d2. Given d1 words learnt on the last day, let the maximum number of words learnt in sem1 be hi, and minimum be lo. For w1 words to be learnt in the first sem, the sufficient condition is hi >= w1 >= lo. For each d1 vary d2 from d1-1 to d1+1. Find a similar hi and lo here as well for sem2 and check conditions.

To find hi and lo for a given w [words read on first day(or last)] and d [the number of days], hi = w + w+1 + .. (w+d-1)/2. And lo is w + w-1 + .. max(w-i+1, 0) ..d terms. So you get hi and lo in O(1). So the only thing that takes time is varying d1 from 0 to w1.