PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Rahul Kumar
Tester: Anay Karnik
Editorialist: Mohan Abhyas
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Chef is very adventurous, so he asked Bob to give him a task.
Bob gave him a sequence of blocks with heights A_1, A_2, \ldots, A_N. Chef is at the first block and he has to reach the N-th block using the minimum number of moves to complete the task.
In one move, he can jump from the i-th block to the j-th block only if the following conditions are satisfied:
- i \lt j
- A_i \geq A_j
- for all k (i \lt k \lt j), A_k \leq A_j
You have to find the minimum number of moves Chef needs to perform to reach the last block, or determine that it is impossible.
EXPLANATION:
Let’s say optimal path taken is P_1 = 1, P_2, \dots, P_l = N.
Jump from P_i to P_{i+1} => A_{P_i} \geq A_{P_{i+1}} and for all P_i < k < P_{i+1}, A_k \leq A_{P_{i+1}}.
From the above conditions, it is easy to see that A_{P_i} = max(A_{P_i},\dots,A_{P_{i+1}})
For all 0 < i < l, A_{P_i} = max(A_{P_i},\dots,A_{P_{i+1}}) => A_{P_i} = max(A_{P_i},\dots,N-1,A_{P_{l}} = N)
Also for all 0 < i < l,A_{P_i} > A_{P_{i+1}} because if A_{P_i} = A_{P_{i+1}} => optimal path is P_1 = 1, \dots P_{i-1}, P_{i+1}, \dots P_l = N with one less move
If A_i = max(A_i,\dots,A_N), P_j < i < P_{j+1} => A_i = A_{P_{j+1}}
From the above analysis it is clear that it possible to jump from block 1 to N if A_1 = max(A_1,\dots,A_N) no of moves = (no of distinct A_i such that A_i = max(A_i,\dots,A_N) ans i > 1)
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
SOLUTIONS:
[details = “Editorial’s Solution”]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,e) for(ll i = 0; i < e; i++)
void solve()
{
ll n;
cin>>n;
vector<ll> A(n);
forn(i, n) cin>>A[i];
ll ans = 0;
ll mx = -1;
for(int i = n-1; i >= 1; i--)
{
if(A[i] > mx)
{
mx = A[i];
ans++;
}
}
if(A[0] >= mx)
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
}
int main()
{
ll t=1;
cin >> t;
forn(i,t) {
solve();
}
return 0;
}