I followed the same approach but it didn’t occur to me that the stack is sorted by default. I called sort() everytime I made any changes to the stack. This gave TLE
Very nice problem, taught many things 
I used the technique explained in the quick explanation part. My solution :
https://www.codechef.com/viewsolution/8217058
Nice problem and nice algo to arrange discs on the stack 
1 Like
The procedure simulated in this question is exactly what is used for finding the longest increasing sub-sequence!!
pos=distance(arr,upper_bound(arr,arr+ans,v));
arr[pos]=v;
if(pos==ans)
ans++;
2 Likes
Why can’t we submit for practice:
?
nevermind, I found the link: CodeChef: Practical coding for everyone
I got TLE. Help
#include <bits/stdc++.h>
#define min(a,b) (a<b?a:b)
#define INF 100000000
#define MOD 1000000007
#define ll long long
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(A,value) memset(A,value,sizeof(A))
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
using namespace std;
typedef map <string,int > Map;
typedef pair < int, string > Pair;
typedef vector V;
int binarysearch(int size,int value,int s[])
{
int ans=size,low=0,high=size-1;
while(low<=high)
{
int mid=(low+high)/2;
if(s[mid]>value)
{
ans=mid;
high=mid-1;
}
else
low=mid+1;
}
return ans;
}
int main()
{
int T;
cin >> T;
while(T–)
{
int a[100001],stack[100001],i,j,n;
cin >> n;
FOR(i,0,n)
cin >> a[i];
stack[0]=a[0];
int size=1;
for(i=1;i<n;i++)
{
sort(stack,stack+size);
int idx=binarysearch(size,a[i],stack);
stack[idx]=a[i];
if(idx==size) size++;
}
cout<<size<<" “;
for(i=0;i<size;i++)
cout<<stack[i]<<” ";
cout<<endl;
}
}
why i am getting TLE here my sol >>CodeChef: Practical coding for everyone and when i use array instead of stacks using STL, it works
You have two level of ‘for’ loop in line 54 and 61. The complexity is O(n^2).
2 Likes
You can use TreeMap instead of TreeSet using value as counter.
http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html
it can be done using simple vector for each new element insertion we can cal for upper bound(using binary search) for this element if it is exit change that value to new value other wise just put at last of stack…
now you are done…O(N*logN)
2 Likes
O(n^2) wont pass.
As editorial says you need to Have a binary search to find a valid stack to be Piled.
I didn’t understand why are we using multiset when vectors are doing the same work? what am I missing?
Hello
Can the binary search method be implemented using recursion?
No restriction as such. I used this approach may be it will be helpful
https://www.codechef.com/LRNDSA04/submit/STACKS
Hey! in which year you are in bmsce ?
I’m in first semester ISE…
i am in second year EEE
1 Like
it will be my pleasure…if we met in clg.
yeah same here bro… soon we will meet
Can anyone tell me why I am getting WA . I have used binarySearch method from Collections in java to get upper bound
My Code