Crossing Blocks Problem Code: CROSBLKSubmit

Read problem statements in Mandarin, Bengali, Russian, and Vietnamese as well.

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}, \dots, 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 < j$
$A_{i} \geq A_{j}$
for all $k$ ( $i < k < 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.

Input Format

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$ .
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

For each test case, print a single line containing one integer --- the minimum number of moves or $- 1$ if it is impossible to reach the last block.

Constraints

$1 \leq T \leq 100$
$2 \leq N \leq 10^{5}$
$0 \leq A_{i} \leq 10^{5}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

Subtasks

Subtask #1 (30 points):

$2 \leq N \leq 1, 000$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{4}$

Subtask #2 (70 points): original constraints

Sample Input 1

2
5
9 15 8 13 8
9
20 16 13 9 17 11 15 8 7

Sample Output 1

-1
4

Explanation

Example case 1: There is no way to move from the first block (with height $9$ ) to any other block.

Example case 2: The only sequence of $4$ moves is $20 \to 17 \to 15 \to 8 \to 7$ . For example, in the first move, all the heights between $20$ and $17$ do not exceed $17$ , so all conditions are satisfied.

Solution in C++

#include<bits/stdc++.h>
#define int long long int 
#define pb push_back
using namespace std;
int fastpower(int x, int y, int modd)
{
    int res = 1;
    x = x % modd;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1){
         res = (res*x) % modd;
        }
        y = y>>1;
        x = (x*x) % modd;
    }
    return res;
}
int GCD(int a,int b){
 while(b!=0){
  int rem=a%b;
  a=b;
  b=rem;
 }
 return a;
}
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int start=a[0];
    for(int i=1;i<n;i++){
        if(a[i]>start){
            cout<<-1<<endl;
            return;
        }
    }
    stack<int>s;
    for(int i=1;i<n;i++){
        while(s.size() and s.top()<=a[i]){
            s.pop();
        }
        s.push(a[i]);
    }
    int ans=0;
    while(!s.empty()){
        ans++;
        s.pop();
    }
    cout<<ans<<endl;
}
signed main()
{
 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 int TESTS=1;
 cin>>TESTS;
 while(TESTS--)
 {
  solve();
 }
 
 return 0;
}

Search This Blog

Code with Kianae

Crossing Blocks Problem Code: CROSBLK Codechef Solutions