# CROSBLK - Editorial

Author: Rahul Kumar
Tester: Anay Karnik
Editorialist: Mohan Abhyas

Easy

None

# PROBLEM:

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;
}

5 Likes
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
std::cin >> t;
while(t--){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
bool flag=1;
for(int z=0;z<n;z++){
if(arr[z]>arr[0]){
flag=0;
}
}
int right[n];
right[n-1]=arr[n-1];
int ans=0;
for(int q=n-2;q>=0;q--){
if(arr[q]>right[q+1]){
right[q]=arr[q];
ans++;
}
else{
right[q]=right[q+1];
}
}
if(arr[0]==arr[n-1]){
std::cout << 1 << std::endl;
continue;
}
if(flag==1){
cout << ans << endl;
}
else{
cout<< -1 <<endl;
}

}
return 0;
}


why its not working?

u havenâ€™t considered the test cases where duplicates are also present.
Ex: 8,8,8,6,5,5,4,4

your code fails when the maximum element in the array has duplicates, instead of running a loop from n-2 to 0, run a loop for n-2 to 1 (inclusive) find out the answer and add 1 to the answer at last, and print it.

I submitted your code with this modification and got accepted. Hope it clears

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
std::cin >> t;
while(t--){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
bool flag=1;
for(int z=0;z<n;z++){
if(arr[z]>arr[0]){
flag=0;
}
}
int right[n];
right[n-1]=arr[n-1];
int ans=0;
for(int q=n-2;q>=1;q--){
if(arr[q]>right[q+1]){
right[q]=arr[q];
ans++;
}
else{
right[q]=right[q+1];
}
}
if(arr[0]==arr[n-1]){
std::cout << 1 << std::endl;
continue;
}
if(flag==1){
cout << ans +1<< endl;
}
else{
cout<< -1 <<endl;
}

}
return 0;
}


I am getting a WA on some test cases? What I am missing can someone please help me.

void solve()
{
ll n;
cin>>n;

vl a(n);
for(int i=0; i<n; i++)cin>>a[i];

ll ans = 0;
stack<ll> s;
for(int i=0; i<n; i++)
{
if(s.empty() == true)
s.push(a[i]);
else
{
while(s.empty() == false && s.top()<=a[i])
s.pop();
s.push(a[i]);
}
}

ll x = -1;
ans = s.size()-1;
if(ans == 0)ans++;

while(s.size()>0)
{
x = s.top();
s.pop();
}

if(x != a[0])
cout<<"-1"<<endl;
else
cout<<ans<<endl;

}strong text


@samrat2825 consider this test case
1
5
5 4 3 5 1
It gives 1 as output but the ans is 2
You may refer to my answer , same approach Solution: 50304205 | CodeChef

Why is my code not working, if anyone can help me out?

#include<iostream>
using namespace std;
int get(int arr[],int n)
{
int curr=n-1;
int ans=1;
int curr_in=arr[n-1];
for(int i=n-2;i>=0;i--)
{
if(arr[i]>curr_in)
{
ans++;
curr_in=arr[i];
curr=i;
}
}
if(curr!=0)
{
return -1;
}
else
{
return ans-1;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<get(arr,n)<<endl;
}
}

1 Like

take the test case :
5,5,3,2,1
but your answer will be -1 which is wrong bcz it may be possible u get a[0] element duplicates before index 0 (where ur curr !=0). Try to take this hint nd correct ur answer, if not check(curr_in ==a[0] && curr!=0 then ans++) for -1 (check if(curr_in!=a[0]) then -1).

3 Likes

Thank you so much, I almost took 1 hour to debug this still didâ€™nt understand my mistake and now when you told me it seems a very silly mistake

Thank you so much

2 Likes

Can anyone tell me why my code is giving WA on TC 2 ?? I have tried all possible cases but it looks fine to me.

// Author : shreyas
// McMurdo Station, Antartica
// Pengiun Intelligence Agency
// Date :

#include <bits/stdc++.h>
using namespace std;

#define fast                    ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define time                    cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n"  ;
#define F                       first
#define S                       second
#define pb                      push_back
typedef long long int           ll  ;

void solve() {

ll n ;
cin >> n ;
vector<ll>arr(n) ;

for(ll i = 0 ; i<n; i++){
cin >> arr[i]  ;
}

reverse(arr.begin(), arr.end())  ;
ll maxi = *max_element(arr.begin() , arr.end())  ;

ll cnt= 0  ;

for(ll i = 0 ; i <n-1 ; i++){
if(arr[i] <= arr[i+1]){
// trace(i,i+1)  ;
continue;
}
else{
cnt++ ;
}
}

if(arr[n-1] == maxi){
cnt++ ;
}
else{
cout << -1  <<"\n"  ;
return ;
}

cout << cnt+1 <<"\n";
}

int32_t main() {

fast ; time;

int t = 1;
cin >> t;

while (t--) {
solve()  ;
}

return 0  ;
}



The ans for this test case should be 3 na OR 4 ?
As it moves from 8 â†’ 6 â€”> 5 â†’ 4 => 3 moves.

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pyes cout<<"Yes"<<endl
#define pno cout<<"No"<<endl
#define pcyes cout<<"YES"<<endl
#define pcno cout<<"NO"<<endl
#define debug(x) cout<<"# "<<x<<endl
#define all(x) (x).begin(),(x).end()
#define f(i,s,e) for(int(i)= int(s); i<int(e);i++)
#define vi vector<ll>
#define MOD 1000000007
#define srt(v) sort(v.begin(), v.end())
#define pb push_back
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
char uc[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char lc[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

//Fast exponention
// ll pw(ll a, ll b){
//   ll r;
//   if(b==0) return 1;
//   r = pw(a,b/2);
//   r = (r*r)%M;
//   if(b%2) r = (r*a)%M;
//   return r;
// }

using namespace std;

ll int mod(ll x){if(x<=0){return -x;}else{return x;}}
ll int sq(ll x){return x*x;}

ll powermod(ll x, ll y, ll p){ll res = 1;x = x % p; if (x == 0){return 0;}
while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}
return res;}

//---------Sieve of Eratosthenes-----------------------//

void SieveOfEratosthenes( vector<ll> &mem)
{ ll n = 100000 +1;

bool prime[n + 1];
memset(prime, true, sizeof(prime));

for (ll p = 2; p * p <= n; p++)
{

if (prime[p] == true)
{
for (ll i = p * p; i <= n; i += p)
prime[i] = false;
}
}

f(i,2,n)
if(prime[i]){mem.pb(i);}

}

ll fact(ll n)
{
if (n == 0)
return 1;
return n * fact(n - 1);
}

//Sort a vector of pairs by the second entry!
bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second < b.second);
}

//----------------------Solve----------------------------//

void solve(){
int n;cin>>n;
int a[n];
int s[n];
int max_ele = 0 ;
int f = 1;
f(i,0,n) {cin>>a[i];s[i]=a[i]; max_ele = max(max_ele, a[i]);}
//cout<<max_ele<<endl;
if(a[0]!= max_ele) f=0;
else
{
f(i,1,n)
{
if(a[i]==max_ele && a[i]!=a[i-1]) {f=0;break;}
}
}

int j = 1;
int t =1;
int cnt = 0;
if(f){
while(t!=n-1){
int cur_max = 0;
f(i,j,n)
{
if(a[i]>=cur_max)
{
cur_max = a[i];
t = i;
}

}
cnt++;
j = t+1;
//cout<<t<<endl;
}
}
if(f) cout<<cnt<<endl;
else cout<<-1<<endl;
}
//----------------------Main----------------------------//

int main()
{

FIO;

int t; cin>>t; while(t--)
solve();

return 0;
}
// in ceil always take float
// always look for edge cases like n == 1


try this test case : 4 4 4 4 3
correct ans should be 2, ur code gives 1

nopeâ€¦
test case: 8,8,8,6,5,5,4,4
for this movement will be from 8(initial index0) â†’ 8(index 2) ->6->5(index 5)->4(last index 7)

1 Like

Start the loop from i=1 instead of 0, leaving the 0th elemnt.
change ans = s.size()-1 to ans = s.size(), as we have not included 0th element in stack.

Pls help me @rajsrivastava that why iâ€™m getting WA. I tried all T.C

// Author : shreyas
// McMurdo Station, Antartica
// Pengiun Intelligence Agency
// Date :

#include <bits/stdc++.h>
using namespace std;

#define fast                    ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define time                    cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n"  ;
#define F                       first
#define S                       second
#define pb                      push_back
typedef long long int           ll  ;

void solve() {

ll n ;
cin >> n ;
vector<ll>arr(n) ;

for(ll i = 0 ; i<n; i++){
cin >> arr[i]  ;
}

reverse(arr.begin(), arr.end())  ;
ll maxi = *max_element(arr.begin() , arr.end())  ;

ll cnt= 0  ;

for(ll i = 0 ; i <n-1 ; i++){
if(arr[i] <= arr[i+1]){
// trace(i,i+1)  ;
continue;
}
else{
cnt++ ;
}
}

if(arr[n-1] == maxi){
cnt++ ;
}
else{
cout << -1  <<"\n"  ;
return ;
}

cout << cnt+1 <<"\n";
}

int32_t main() {

fast ; time;

int t = 1;
cin >> t;

while (t--) {
solve()  ;
}

return 0  ;
}


// Author : shreyas
// McMurdo Station, Antartica
// Pengiun Intelligence Agency
// Date :

#include <bits/stdc++.h>
using namespace std;

#define fast                    ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define time                    cerr<<"Time taken : " <<(float)clock()/CLOCKS_PER_SEC <<" secs"<<"\n"  ;
#define F                       first
#define S                       second
#define pb                      push_back
typedef long long int           ll  ;

void solve() {

ll n ;
cin >> n ;
vector<ll>arr(n) ;

for(ll i = 0 ; i<n; i++){
cin >> arr[i]  ;
}
reverse(arr.begin(), arr.end())  ;
ll maxi = *max_element(arr.begin() , arr.end())  ;

ll cnt= 0  ;
int maximum = INT_MIN;
for(ll i = 0 ; i <n-1 ; i++){
if(arr[i] <= maximum){
// trace(i,i+1)  ;
continue;
}
else{
cnt++ ;
maximum = arr[i];
}
}

if(arr[n-1]!=maxi){
cout<<"-1\n";
return;
}

cout << cnt <<"\n";
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt","r",stdin);
freopen("outputf.txt","w",stdout);
#endif
int tt;
cin>>tt;
while(tt--)	{
solve();
}
return 0;
}



Ohkayy got it. Thanks

what is my mistake in this
https://www.codechef.com/viewsolution/50416136

@anurag41682 your code fails the test cases where Ai=0
for eg
1
3
5 3 0
Here your code gives SIGSEGV .