tourist is Participating!

Omg, спасибо

If that was what intended then it's the first time I see such tight constraints on GCJ. I'm sure there were no solutions with wrong asymptotic authors were trying to cut off, but then why not use n <= 20?..

Nevertheless, respect to everybody who suceeded to the onsite finals.

Better than binary search:

Note that we can find s_i + K - s_i = sum_i + 1 - sum_i for any valid i; by repeating it, we can find s_i + nK - s_i. Compute , so that group spans the range [s_i + min_i, s_i + max_i]. Clearly this also means the minimum difference is max_i - min_i.

But in fact, this is almost enough; let , then the answer is either D or D + 1. To find this, compute and . If S ≤ T then the answer is D, otherwise the answer is D + 1.

The idea is like this. This might not make sense; I'm not sure how to word it.

We know that each group has a difference of minimum and maximum that we cannot change. However, we can try to arrange the groups so that their minima line up. For example, given K = 3, sum = (3, 4, 2, 5, 2), we obtain group to have s₁, s₄ = s₁ + (4 - 3), s₇ = s₄ + (2 - 5), group to have s₂, s₅ = s₂ + (2 - 4), and group to have s₃, s₆ = s₃ + (5 - 2). In other words, group spans [s₁ - 2, s₁ + 1], group spans [s₂ - 2, s₂], and group spans [s₃, s₃ + 3].

Now, we begin by lining up everything. Let s₁ = x₁ + 2, s₂ = x₂ + 2, s₃ = x₃, so that our ranges become [x₁, x₁ + 3], [x₂, x₂ + 2], [x₃, x₃ + 3]; this also means x₁ + x₂ + x₃ =  - 1.

Now, if we can use fractional temperatures, we can just set and we're done. But this is not the case, so unfortunately we have to fiddle a little. Let's begin with x₁ = x₂ = x₃ =  - 1, and we will increase two of the x_i's (may be the same) so that their sum becomes  - 1. Our intervals are [ - 1, 2], [ - 1, 1], [ - 1, 2], and we want to slide two of them to the right, trying to keep the difference between minimum and maximum as small as possible.

Unfortunately, this is impossible without making some of the upper bounds to exceed 2 (there is only one move available, the middle one moved to the right once to [ - 1, 2], [0, 2], [ - 1, 2]), so we must necessarily break the upper bound 2. But now this is always possible; after moving the maximum extent possible, we just move as many intervals as necessary (in this case one more, to [0, 3], [0, 2], [ - 1, 2]). This will never reuse the same interval if we take the starting value of x₁, x₂, x₃ to be ; that is, the largest equal value for x₁, x₂, x₃ so that their sum doesn't exceed the required sum. The difference to the required sum will be strictly smaller than K, hence why we won't increase the upper bounds. We also won't be able to get rid of the original value  - 1, since if we can that means we will increase all K intervals by at least once each, but we don't have that many moves.

After setting x₁ = 0, x₂ = 0, x₃ =  - 1, this corresponds to the solutions s₁ = 2, s₂ = 2, s₃ =  - 1, and thus follows s₄ = 3, s₅ = 0, s₆ = 2, s₇ = 0, making the sequence s = (2, 2,  - 1, 3, 0, 2, 0) which can be verified.

Had sum₅ = 3 instead, we have s₇ = s₄ - 2 (and thus s₇ = s₁ - 1), making the first interval to be [s₁ - 1, s₁ + 1] instead, so that we obtain s₁ = x₁ + 1 and x₁ + x₂ + x₃ = 0. This time we can just set x₁ = x₂ = x₃ = 0, and we're done already, giving s = (1, 2, 0, 2, 0, 3, 0).

WOAH