PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh_07
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have an array A, on which two types of moves can be performed:
- Subtract 1 from some prefix, all of whose elements are \gt 0; or
- Set an element to 0.
What’s the minimum number of moves needed to make every element of the array 0?
EXPLANATION:
First, note that all moves of the second type (setting a single element to 0) can be performed at the very end.
Further, it’s easy to see that the answer is bounded above by N: just set each element individually to 0.
This means, in any optimal solution, we use the prefix decrementing move less than N times.
Suppose we use it exactly x times. What’s the largest number of 0 elements we can obtain? (The other elements can then be set to 0 using the type 2 operation.)
To answer this, observe that if there are indices i and j (1 \leq j \lt i \leq N) such that A_j \lt A_i, then A_i can never be set to 0 using only prefix moves.
This is because any prefix containing index i also contains j, and A_j will thus reach zero before A_i does (after which it isn’t allowed to include j in a prefix move).
In other words, A_i can be set to 0 using some prefix moves only if nothing before it is smaller than it — meaning A_i should be a prefix minimum!
So, let M denote the prefix minimum array of A.
For instance, if A = [4, 5, 3, 4, 1, 3, 2, 1] then M = [4, 3 ,1, 1].
Then, with x prefix moves, the maximum number of elements we can set to 0 is exactly the elements of M that are \leq x. Let this be Z_x.
Computing Z_x quickly isn’t hard: for example, if x is processed in ascending order Z_x will correspond to some increasing suffix of M which can be maintained with a pointer; or you can use the fact that M is sorted and binary search.
Either way, once Z_x is known for a fixed x, we know that the total number of moves needed (including making x prefix moves) is x + (N - Z_x).
The final answer is thus the minimum of (x + N - Z_x) across all 0 \leq x \lt N.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
// we can make any element 0 using first type of operation when its prefix minima
// its optimal to make a suffix of the prefix minimas 0
int mn = INF;
vector <int> b;
int ans = n;
for (auto &x : a){
mn = min(mn, x);
if (mn == x){
b.push_back(x);
}
}
reverse(b.begin(), b.end());
for (int i = 0; i < b.size(); i++){
ans = min(ans, n - i - 1 + b[i]);
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mins = []
for x in a:
if not mins or x <= mins[-1]: mins.append(x)
ans = len(mins)
for i in range(len(mins)):
ans = min(ans, mins[i] + i)
print(ans + n - len(mins))