CF 1995E1 - Let Me Teach You a Lesson (Easy Version)

Rating: 2700
Tags: 2-sat, data structures, dp, matrices, two pointers
Solve time: 2m 39s
Verified: no

Solution

Problem Understanding

We have 2n knights arranged around a circle. Desk i contains knights (2i-1, 2i), so every desk contributes a sum of two intelligence values.

The only operation allowed is swapping opposite positions in the circle. For every k from 1 to n, positions k and k+n form an opposite pair. We may independently decide whether to swap that pair or leave it unchanged.

After performing any number of such swaps, every desk obtains some total intelligence. Our goal is to make these desk totals as balanced as possible, meaning we want to minimize:

$$\max(\text{desk sums})-\min(\text{desk sums})$$

The input contains several test cases. The easy version has a very small global constraint: the sum of all n is at most 2000. That immediately suggests that an $O(n^2)$ or even $O(n^2 \log n)$ solution is perfectly acceptable, while anything exponential in n is impossible.

The subtle part of the problem is that the swap decisions are not independent per desk. A single opposite-pair swap changes two positions simultaneously, so one decision can affect two different desk sums.

A few edge cases are easy to overlook.

Consider:

n = 1
a = [10, 17]

There is only one desk. Its sum is always 27, regardless of swaps. The correct answer is 0.

A second trap appears when different desks share variables indirectly.

n = 3
a = [1, 10, 1, 10, 1, 10]

Every desk can be m