PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array A.
Every second, the following process will repeat:
- For each i from 1 to N-1, if A_i \lt A_{i+1}, set A_i to A_{i+1}.
How many seconds will it take for the array to stabilize, i.e., not be changed by the operation?
EXPLANATION:
Let’s look at the maximum element of A, say at index i_1.
If there are multiple occurrences of the maximum, choose the leftmost.
Now, note that no matter how the process actually occurs to the left of index i_1, eventually all those elements will become A_{i_1}, since they’re all smaller than it.
This will take i_1 - 1 seconds, since the value at index i_1 can propagate left only one position at a time.
Next, let’s look at indices \gt i_1.
None of them will ever affect an index at or before i_1, because A_{i_1} was the maximum element.
So, the part of the array from i_1 + 1 to N can essentially be treated as a separate array, and solved analogously: find the leftmost maximum in it, say at i_2, and then everything from I_1 + 1 to i_2 will turn into A_{i_2} eventually, in i_2 - i_1 - 1 seconds - after which the process can be repeated for [i_2+1, N], and so on.
The final answer is simply the maximum time any of these steps take.
If the indices i_1, i_2, \ldots, i_k of the maximums computed above are known, the answer is simply the maximum of (i_j - i_{j-1} - 1) across them all which is easy to find.
However, computing the indices by naively scanning the array each time is too slow.
Instead, observe that these indices are exactly the suffix maximums of A, which can be found in linear time by processing A in reverse order.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#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;
vector<int> a(n);
for (int &x : a) cin >> x;
int mx = n-1, ans = 0;
for (int i = n-2; i >= 0; --i) {
if (a[i] >= a[mx]) { // New suffix maximum
ans = max(ans, mx - i - 1);
mx = i;
}
}
ans = max(ans, mx);
cout << ans << '\n';
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
ll ans = 0;
ll mx = 0;
ll ops = 0;
rev(i,n,1){
if(a[i] >= mx){
mx = a[i];
ops = 0;
}
else{
ops++;
}
amax(ans,ops);
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}