PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: q_ed
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Sets, binary search
PROBLEM:
You’re given a histogram of length N, with the i-th bar having height A_i.
In one move, you can increase the height of any bar by one unit.
Find the minimum number of moves needed to end up with a histogram with perimeter \le K, or decide that it’s not possible.
EXPLANATION:
Let’s analyze how exactly the perimeter of a (connected) histogram can be computed.
Each part of the perimeter is either a vertical or a horizontal segment, so we can separately add up vertical and horizontal parts.
The horizontal parts are quite easy to analyze: for each 1 \le i \le N, there’s a bottom segment spanning [i-1, i] on the x-axis, and a top segment also spanning [i-1, i] at a height of A_i.
This means each i contributes two horizontal segments of length 1, and so the overall length is just 2N.
As for the vertical segments: for each x-coordinate 0 \le i \le N, there will be a single contiguous vertical segment that’s part of the perimeter at this coordinate.
The length of this segment will be:
- A_1, if i = 0
This is the left border of the shape. - A_N, if i = N
This is the right border. - |A_i - A_{i+1}| for each 1 \le i \lt N
These correspond to the upward/downward movements along the shape, when moving from one rectangle to the next.
That is, the overall perimeter equals
It can also be seen that the minimum perimeter we can ever attain equals 2N + 2\cdot\max(A)).
The 2N part is constant, and the 2\cdot\max(A)) part comes from the vertical segments: we’ll cover a length of (at least) \max(A) vertically to the left of the maximum element, on our way to reach its peak; and the same applies to its right.
Since we can only increase elements of A, \max(A) cannot be reduced - so 2N + 2\cdot\max(A)) is a lower bound on the perimeter.
It’s not hard to see that it’s possible to attain this lower bound: a simple construction is to just set every A_i to \max(A), forming a rectangle.
So, if K \lt 2N + 2\max(A), we can immediately say that it’s impossible to achieve our goal of making the perimeter \le K.
Otherwise it’s always possible, so now we turn to minimizing the number of moves.
Now, consider what happens when we increase some element A_i by 1.
Analyzing the perimeter formula shows that this will change the perimeter by either 0, -2, or +2, depending on the relation of A_i to its neighboring elements.
Specifically, the perimeter can change by -2 if and only if A_i is strictly smaller than both its neighbors.
This gives us the idea of a greedy solution: pick an element that’s smaller than both its neighbors, and repeatedly increase it by 2 till it equals one of its neighbors.
Each such move will reduce the perimeter by 2, which is definitely optimal.
However, we now run into an issue: what if there are no such elements?
For example, if A = [2, 1, 1, 2], there’s no element that’s strictly smaller than both its neighbors.
However, it’s still possible to reduce the perimeter by 2, by using two operations to obtain [2, 2, 2, 2].
This leads to a generalization of the earlier idea: rather than work with single elements, we work with segments of equal elements.
That is, we can take a contiguous segment [l, r] such that A_l = A_{l+1} = \ldots = A_r, that also satisfies A_{l-1} \gt A_l and A_r \lt A_{r+1}, and increase each element of the segment by 1 each.
This will reduce the perimeter of the figure by 2, with a cost of (r-l+1).
The next question that comes up is: if there are multiple segments to choose from, which one should we pick?
The answer to that is simple: choose whichever segment has the lowest cost, i.e. the lowest length.
This gives us the skeleton of a solution: repeatedly choose the shortest segment [l, r] with equal elements that’s smaller than both its borders, and increase all of the elements here by 1.
Repeat this till the perimeter becomes \le K, which is always doable (in particular, it can be proved that if no valid segment to perform this operation exists, then the perimeter is exactly 2N + 2\max(A) which we already know is \le K.)
Of course, a direct implementation of the above algorithm takes \mathcal{O}(N^2\cdot \max(A)) time, since each move takes \mathcal{O}(N) time and reduces the perimeter by 2; and it’s possible to have the initial perimeter be of the order \mathcal{O}(N\max(A)) while requiring it to end up at \mathcal{O}(\max(A)).
So, we need to figure out a way to speed things up.
One simple observation that helps here is that, if we decide to operate on the segment [l, r], then we can in fact repeatedly operate on it till it ends up equal to one of its neighbors, i.e. till A_l = A_{l-1} or A_r = A_{r+1} holds.
Or, more specifically, we can operate on the segment [l, r] exactly \min(A_{l-1}, A_{r+1}) - A_l times before it merges into a larger segment.
This allows us to simulate the process using a couple of sets.
That is, let’s store two sets S_1 and S_2 of segments.
- S_1 will store all segments of equal elements in the current array, sorted left to right.
For example, if A = [5, 5, 3, 1, 1, 1, 3, 2, 2, 4], then we’ll have S_1 = \{[1, 2], [3, 3], [4, 6], [7, 7], [8, 9], [10, 10]\}, where each [l, r] \in S_1 represents a maximal equal segment of elements. - S_2 will store only those segments that are smaller than their borders.
These will be sorted by their length in increasing order (so that the first element of S_2 is always the segment we want to operate on).
In the example of the above array, we’ll have S_2 = \{[8, 9], [4, 6]\}.
Note that [8, 9] comes first because its shorter.
If we have S_1 and S_2, we can repeat the following process:
- Extract the first element of S_2, say [l, r].
Perform as many operations as possible with a cost of (r-l+1), till either the perimeter becomes \le K or this segment reaches one of its border values. - If it equals one (or both) of its border values, we now need to merge the segments together.
This can be done by just erasing the corresponding segments from S_1 and/or S_2, and inserting the merged one wherever applicable.
To make this a bit simpler, you can note that whenever [l, r] \in S_2, its neighboring segments can never be in S_2, so you don’t have to worry about adjusting for them in S_2. - Continue this till the perimeter becomes \le K.
Let’s analyze the time complexity of this algorithm.
In each step, we process a single segment of the array.
The actual work done is only \mathcal{O}(\log N) - we only perform a constant number of segment insertions/deletions from S_1 and/or S_2, and do \mathcal{O}(1) work to update the answer.
So, the time complexity is \mathcal{O}(X \log N), where X is the number of intervals processed.
It’s not hard to see that because we’re merging intervals, X is \mathcal{O}(N).
This is because we start off with \le N intervals, and then each time we process an interval, it is merged with one or both of its neighbors into a strictly larger interval.
This means, after no more than N merges, we’ll be left with an interval that’s just the entire array; so the process must definitely have ended by then.
This means we create no more than 2N intervals ever, which proves the earlier claim of the number of processed intervals being \mathcal{O}(N\log N).
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
ll k; cin >> k;
vector a(n, 0ll);
for (auto &x : a) cin >> x;
if (2*n + 2*ranges::max(a) > k) {
cout << -1 << '\n';
continue;
}
ll cur = 2*n + a[0] + a[n-1];
for (int i = 0; i+1 < n; ++i) cur += abs(a[i] - a[i+1]);
if (cur <= k) {
cout << 0 << '\n';
continue;
}
set<array<ll, 3>> segments;
set<array<ll, 3>> active;
for (int i = 0; i < n;) {
int j = i;
while (j < n and a[i] == a[j]) ++j;
segments.insert({i, j-1, a[i]});
if (segments.size() >= 3) {
auto [l, r, x] = *next(rbegin(segments));
if (a[l] < a[l-1] and a[r] < a[r+1]) active.insert({r-l, l, r});
}
i = j;
}
ll ans = 0;
while (cur > k) {
auto [len, l, r] = *active.begin();
active.erase(active.begin());
auto it = segments.lower_bound({l, 0, 0});
auto [l1, r1, x1] = *prev(it);
auto [l2, r2, x2] = *next(it);
segments.erase(it);
int reach = min(x1, x2);
// len moves to reduce by 2
int steps = min(reach - (*it)[2], (cur - k + 1)/2);
ans += 1ll * steps * (len+1);
cur -= 2ll * steps;
if (x1 == reach) {
segments.erase({l1, r1, x1});
segments.insert({l1, r, reach});
l = l1;
}
if (x2 == reach) {
segments.erase({l, r, reach});
segments.erase({l2, r2, x2});
segments.insert({l, r2, reach});
r = r2;
}
// Now [l, r]
it = segments.lower_bound({l, 0, 0});
if (it != begin(segments) and next(it) != end(segments)) {
int px = (*prev(it))[2];
int py = (*next(it))[2];
if (reach < px and reach < py) active.insert({r-l, l, r});
}
}
cout << ans << '\n';
}
}