Idea 1: Fenwick tree

Having problem understanding the solution. Namely Why need to set k = min(k, n-k)?

assume k * 2 <= n for now…

If we connect from x to x + k - n, How much diagonals do we cross?

1. Because each diagonal has a gap of k, then any diagonal originated in (x - k, x + k), will cross our new diagonal

2. Therefore, we need to maintain prefix sum of number of digaonals from the point. Note that we keep the 1 count only for the starting , but not for ending point

3. For each new diagonal, we can calculate the interval sum with the fenwick tree, and add 1 to the point sending out to the new diagonal

Now consider k * 2 > n, the above formula, stops working, because the from and to points swapped sides clockwise! Therefore, we set k = n - k in this case, as each step, the new “shape” remaings same, except it is an mirror image, node-wise!

Idea 2

We follow the sequence of actions, every time the next index is less than the current one, we know we have rotated one round around the polygon. Therefore, from then on, the number of of polygons we will cross will be increaded by 1 compared to the previous cycle

Need to watch out the case where we first cross the cycle, and when we end up in 0 again, which is the final step.

750C: New Year and Rating

Idea 1: Math (My approach)

Maintain an upper and a lower bound. Initially they are set to (-INF, INF), as we go through the rating change in the reverse order, apply the delta to upper/lower bound as long as they are not INF. If we run into a band change, we will do a hard reset if the current value after the rating change is inconsitent with the new band

Idea 2: Bsearch

Since the problem asks for the max possible value, and input size is 20k, we can try binary search the answer directly, i.e., just use the bsearch to introduce the final answer, and run through the sequence of actions in the reverse order, and see if it is consistent with the band before the contest