Need help in solving

help
1

an array consists of height of n bars.
there is robot which picks all the bars that are taller than the one to its immediate left in each step.
the robot does this step until no bars can be picked.
find the number steps so that no bars can be picked after that.

sample testcase:
5 1 4 2
after 1st step: 5 1 2
after 2nd step: 5 1
after 2nd step no more bars can be picked
answer: 2

what is the efficient approach to solve this question? @carre @ssjgz @l_returns @mgch @chenreddy @dardev @ssrivastava990

2

Longest decreasing subsequence (LDS) will be the remain after all operation.
so answer will be n-size(LDS) .

1 Like
3

BRo can you tell whats s error in my code lead game
#include
#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
cin >> n;
int p1 ;
int p2 ;
int l1=0;
int l2=0;
int c1=0;
int ct1=0;
int ct2=0;
int j = 0;
int k=0;
int a[n],c[n];
for (int i = 0;i< n;i++)
{
l1=0;
l2=0;

 cin >>p1 >>p2 ;//5 //3;//5 //6
if (p1>p2)
{
    l1 = (p1-p2);//2//0
    ct1++;//1
}
else 
{
    l2 = (p2-p1);//0//1
    ct2++;//1
}




    if(l1>l2)
    {
    for (;j<ct1;)
 {  
     a[j]=l1;//a0=2
 

  j++;//1
 }
    }
    else{
    for (;k<ct2;)
 { 
    c[k]= l2;//c[0] =1;
    
    k++;//1
   }
   }

}
sort (a,a+ct1);
sort (c,c+ct2);
//cout <<“j=”<<j<<endl<<“k=”<<k;
if (a[j-1]>c[k-1])
cout << “1” << " "<< a[j-1]<<endl;
else
cout << “2” << " "<< c[k-1]<<endl;

}

4

the question is to find the number of steps… not number of remaining elements.

5

do you know any approach to find the number of steps required to reach the final state?

6

He is correct, the number of steps are n-size(LDS) because we will remove all rest elements that are n-size(LDS) in number

8

No.
consider this below example:
3 5 2 5 1

after 1st step 3 2 1
no more bars can be removed
the answer is 1

n - size (LDS) = 5 - 3 = 2

they are not same

9

I think the problem can be broken down to chunks of increasing and non-increasing substrings. I need to think more about how to proceed after that. Will let you know if I am able to solve.

1 Like
11

I think the following could work
From left to right determine the step when the bar can be picked in this way:

  1. find the first bar from the left that can be removed in step 1, and assign 1 to it; You can use step=-1 to flag bars that can’t be removed

  2. while moving to the right if the bar is greater than previous its step is 1, otherwise you need to find the closer previous bar lower than this. Let say that the current index is i and the index with the previous lower bar is j, then the step for i bar is the maximum step between the steps of bar in range [j+1,i-1] plus one

You can use a map (EDIT, a simple vector should work) to store the visited heights and a segment tree to find the maximum step in the range
Obviusly the answer is the maximum step that is not infinity

1 Like