CROSBLK - Editorial

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;
}
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
correct answer is 4
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 

Please help why does this fail?

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)
answer become 4;
Please try to read and examine the problem once again.

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 .