827. k Stripes That Must Not Go Down
A belt carries n buckets in a line, bucket i holding a[i] units. The belt has k
lanes, and bucket i shares a lane with bucket i - k, bucket i - 2k and so on. The belt is
acceptable when, within every lane, the amounts never go down:
a[i - k] <= a[i] for every i with k <= i < n
One repack replaces the contents of one bucket with any integer, positive, zero or negative. Print the fewest repacks that make the belt acceptable.
buckets 5 4 3 2 1, k = 2 -> 3
buckets 4 1 5 2 6 2, k = 3 -> 2
buckets 1 5 2 6 3 7 4 8, k = 2 -> 0
## Split by lane, then count what you keep
The condition never compares two buckets in different lanes, so the k lanes are independent.
Lane r is the subsequence a[r], a[r+k], a[r+2k] and so on, and it must end up
non-decreasing.
Counting repacks directly is awkward, because changing one bucket changes what its neighbours are allowed to be. Count what you KEEP instead. Since a repack may write ANY integer, any set of buckets you decide to keep can be made to work as long as the kept values are already non-decreasing in lane order, filling each gap with a value between its neighbours. So the fewest repacks in a lane is
length of the lane - length of its longest NON-DECREASING subsequence
and the answer is that total over all lanes. Problem 478 makes the same move for the case
k = 1 with STRICTLY increasing as the goal, which needs the extra step of subtracting the
index first; here the goal is non-decreasing, so no shift is needed.
## Where the binary search is
It is not over the answer. This problem is in this block because it is where a binary search appears INSIDE the check, and the cost of the whole solution is the cost of that inner search multiplied by the number of times it runs.
The longest non-decreasing subsequence is found with the patience method of problem 599. Keep a
list tails, where tails[j] is the smallest value that can end a non-decreasing subsequence
of length j + 1 seen so far. For each new value v:
find p = the first position with tails[p] > v (an upper bound)
if p == length of tails: append v
else: tails[p] = v
and the answer for the lane is the final length of tails.
The upper bound is the detail that carries the whole difference between this and problem 599.
Problem 599 wants a STRICTLY increasing subsequence and uses a LOWER bound, the first position
with tails[p] >= v, which refuses to extend on an equal value. Using a lower bound here would
count 2 2 2 as length 1 instead of 3. One comparison, three times the answer.
tails is non-decreasing at all times, which is what makes the search legal, and the standard
lower-bound loop from problem 241 with < swapped for <= computes the upper bound.
## Why the counting is correct
Any acceptable belt agrees with the original on some set of buckets, and within each lane that set must be non-decreasing, so it is at most the longest non-decreasing subsequence. Conversely, given such a subsequence, every other bucket in the lane can be rewritten to a value between the kept ones on either side, since any integer is allowed. So the bound is achieved.
## What is printed when nothing needs doing
A belt that is already acceptable has every lane non-decreasing, so each lane's longest
non-decreasing subsequence is the whole lane, and the answer is 0. Two of the tests are
already acceptable, one of them because k equals n and every lane holds a single bucket.
## Size of the numbers
The amounts reach 10^9 and are only ever compared against each other inside the patience
list, never added, so nothing overflows a signed 32-bit integer. The answer is a count of
buckets and reaches 10^5. The reference solutions accumulate that count in a 64-bit type
for uniformity with the rest of this block, not out of necessity.
## Cost
Time O(n log n): each bucket is handled once and costs one binary search inside its lane.
Space O(n).
Constraints - `1 ≤ k ≤ n ≤ 100000` - `1 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k, the number of buckets and the number of lanes.
The second line contains n integers a[0] ... a[n-1], the amounts in belt order.
Output
Print one integer, the fewest bucket repacks needed to make every lane non-decreasing. Print it alone on one line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.