PROBLEM LINK:
Author: Vitaliy Herasymiv
Tester: Anton Lunyov
Editorialist: Anton Lunyov
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
You are given an array R[0], R[1], …, R[N-1] and two integers K and M such that 1 ≤ M ≤ K ≤ N. We call array bad if there exists i from 0 to N-K, inclusive, such that for at least M different values of j from i to i+K-1, inclusive, we have R[j] = max{R[i], R[i+1], …, R[i+K-1]}. You can choose some subset of elements of this array and increase each element of this subset by 1 (it is the simplest and the most clear reformulation of the part where we can apply several operations, but at most one operation for each element). You need to find the smallest size of such subset which leads to not bad array.
EXPLANATION:
After figuring out subset reformulation the solution is straightforward. We just need to iterate over all subsets of the set of indexes {0, 1, …, N-1}, increase by 1 elements of the array corresponding to this subset, and check the new array for badness strictly by definition.
But let’s consider implementation of this in detail. At first let’s see how we could check that the array is bad. For this we need to loop over i from 0 to N-k according to definition. For each such i we at first find maximum among numbers R[i], R[i+1], …, R[i+K-1] and then in one additional pass we calculate how many of them equal to this maximum. See tester’s first solution as a reference of clear and commented implementation of isBad() routine.
Now when we have such check with us we only need to iterate over all subsets as mentioned above. The usual and convenient way to do this is represent subset as a binary integer which is usually called mask. Namely, the element R[i] is included to the subset if and only if the i-th bit in binary is set in mask (i-th bit corresponds to 2i). Now to iterate over all subsets we just need to loop over all numbers from 0 to 2N − 1, inclusive. To check that R[i] belongs to the subset we need to check whether (mask & 1 << i) is non-zero (using C/C++/Java notation). Here & is bitwise “and” operation and << is a left bitwise shift, so 1 << i equals to 2i. Now the pseudo code for this could be like this:
for mask = 0 to 2N − 1 do
for i = 0 to N − 1 do
if (bitwise "and" of mask and 2i is non-zero) then
newR[i] = R[i] + 1
else
newR[i] = R[i]
if (not isBad(newR, K, M)) then
update the answer
To update the answer we need to count the number of ones in binary form of mask (which is the size of the subset), compare it with existing answer and update the answer if it is larger. To find the number of ones in binary we could use the similar loop over i as above. Alternatively we could use some advanced bitwise magic to calculate this number faster in general. See tester’s first solution as a reference. See also the heuristic there that helps to skip some subsets in general.
The complexity of the above solution is O(2N * (N − K + 1) * K). Here multiplier 2N corresponds to the loop over subsets, N − K + 1 corresponds to the loop over values of i in the badness check and K corresponds to the loop over j for the fixed i in the badness check.
WHEN IS THE ANSWER EQUAL TO -1?
Note that when M = 1 the answer is always -1 as mentioned in the explanation of the example case 4 in the problem statement. But in this solution we don’t use this check in order to keep it clear. We have received many comments during the contest asking whether answer -1 could be for other values of M. As you see, our solution doesn’t care about this fact, hence we did not answer on this question during the contest. But for curious minds I will answer on it finally:
The answer could be -1 for M > 1.
Probably the simplest test with this effect has the form
8 4 2 0 0 1 1 1 1 0 0
The explanation could be like that. In order to satisfy the segment [0 0 1 1] 1 1 0 0 we need to increase one of the ones on it. The same is true for the segment 0 0 1 1 [1 1 0 0]. But then on the segment 0 0 [1 1 1 1] 0 0 we will have at least two twos and we can’t fix this since we can apply operation to each element at most once.
Actually when M = 2 the answer -1 happens more or less often on the tests having R[i] equals to 0 or 1. But we did not find any such test for M = 3. So it is an open question whether such test exists.
ALTERNATIVE SOLUTION:
The problem can be solved using recursive backtracking instead of iteration over all subsets. In this way we will obtain much more efficient solution that solves the problem (with the current test data) in no time. See tester’s second solution as a reference. It contains explanatory comments to the approach.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s first solution can be found here.
Tester’s second solution can be found here.
