PROBLEM LINK:
Author: admin2
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak
DIFFICULTY:
Easy
PREREQUISITES:
Binary search, precomputation
PROBLEM:
Let a magic sequence of order m, denoted also by magic(m), be a sequence of a integers starting from 1 and increasing by 1 up to m and then decreasing from m to 1. For example, the magic sequence of order 5 is: 1, 2, 3, 4, 5, 4, 3, 2, 1. Notice that magic(m) has length 2 \cdot m - 1.
Given an array of h of n positive integers, denoting consecutive blocks, you want to perform the smallest number operations of reducing the high of a selected block by 1 in such a way that after all operations are performed, there exists exactly one magic sequence in h and all elements of h not included in the magic sequence are 0.
EXPLANATION:
The problem can be reformulated as follows: find the largest possible integer m, such that there can be formed a magic sequence of order m in h. You might wonder why this problem is equivalent to the one asked in the original statement. Well, let s be the sum of all integers in h. In order to form the resulting sequence magic(m) in h and set all elements in h not included in this sequence to 0, we have to perform s - m \cdot (m+1) - m = s - m^2 operations, because the sum of heights in magic(m) is m^2. Since we want to minimize the number of performed operations, we want to maximize m.
The second crucial observation is that if we can form a sequence magic(m) in h, then for each k < m, we can also for a sequence magic(k) in h. This follows from the fact that in order to transform sequence magic(m) to magic(m-1), the only thing to do is to subtract one from each of its elements and remove the left-most and the right-most elements.
Based on the above two observations, we can use binary search to find the largest m, such that sequence magic(m) can be formed in h. The lower bound for binary search should be set to 1, and the upper bound can be set to for example n, but one can also compute the more exact upper bound, although it doesn’t matter much.
Now, how for a fixed m find out if a sequence magic(m) can be formed in h, and do it in linear time?
One possible solution is to compute two boolean arrays of size n:
L[i] := true if and only if the sequence 1, 2, \ldots, m can be formed in h[i-m+1], h[i-m+2], \ldots, h[i].
R[i] := true if and only if the sequence m, m-1, \ldots, 1 can be formed in h[i], h[i+1], \ldots, h[i+m-1].
Then, sequence magic(m) can be formed in h if and only if there exists i, 1 \leq i \leq n, such that both L[i] and R[i] are true. Thus the problem is reduced to computing arrays L and R.
Let’s take a closer look on how to compute array L. Computing array R is based on the same idea.
First of all, let’s set all entries in L to false. The idea is to iterate over h from left to right (right to left if you want to compute R) while updating variable k denoting the length of the longest sequence 1, 2, 3, \ldots, k ending in the current element, where k is at most m. The below pseudocode illustrates the approach:
k = 0
for i = 1 to n:
if h[i] >= k+1:
k += 1
if k == m:
L[i] = true
k -= 1
else:
k = h[i]
The above idea is based on the fact that if we have a sequence 1, 2, \ldots, k ending in i-1, then if h[i] is at least k+1 we can extend the sequence by one, and if h[i] is at most k, then the best we can do is to set k to h[i], because a sequence 1, 2, \ldots, k ending at index i-1 can be transformed to a non-longer sequence 1, 2, \ldots, h[i] ending at index i if h[i] \leq k.
Since the computing of arrays L and R takes O(n) time, and the range over we perform binary search has length O(n), the total time complexity is O(n \cdot \log(n)).
As it was pointed out with the comments, the above method can be improved to O(n) solution by avoiding binary search. The idea is to compute arrays L and R at the beginning, without specifying m. We define L[i] (and similarly R[i]) as the maximum length of sequence 1, 2, \ldots ending in i, and compute it as follows:
k = 0
for i = 1 to n:
if h[i] >= k+1:
k += 1
else:
k = h[i]
L[i] = k
Then, after computing arrays L and R, we know that the maximum m for which magic sequence of order m exists is \max\limits_{1 \leq i \leq n} \min(L[i], R[i])
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.