PROBLEM LINK:Author: Kanstantsin Sokal DIFFICULTY:Simple PREREQUISITES:binary search, data structures PROBLEM:Mike likes to compose his disks in stacks, but there's one very important rule: The disks in a single stack must be ordered by their radiuses in a strictly increasing order such that the topmost disk will have the smallest radius. Mike initiates an empty set of disk stacks. Mike processes the disks in the given order $A_1, A_2, ..., A_N$ using the following pattern:
Your task is to output the set of the stack top disk radii after the algorithm is done in nondecreasing order. QUICK EXPLANATION:====================== EXPLANATION:================ Now, from the example, given in the problem statement, it should be pretty clear that we need not store all the radii present in a stack. Since, we just need to output the top radii, and also where a new disk goes also depends on the top radii, we can just store the top radii of each of the stack currently formed. Let's say we have an array $S_1, S_2, ..., S_k$ which currently stores the top radii of all stacks currently formed in sorted order. And now, we want to insert a new disk with radius $x$ into this structure. So, we need to find smallest $S_j$(i.e. smallest $j$, since $S$ is sorted) such that $S_j > x$. And we update $S_j = x$. We know that $S_{j1} \le x$ and $S_{j+1} \gt x$, so array $S$ still remains sorted after the update. So, at each step we apply binary search to find such an index $j$ and update the value $x$. If there is no such index found, we just create a new entry at the end of the array.
You can also use builtin function $\text{upper\_bound}$ instead of binary search. Also, we can solve this problem using multiset. We just have to perform simulation. So, first, let's try to write our algorithm in pseudo code first and then we'll try to think about what kind of data structure do we need to implement that algorithm efficiently:
Now, we just need to think what kind of data structure DS is. It should efficiently insert values, delete values and for a given value find smallest number greater than value. If you know STL, set is such a data structure which keeps its elements sorted and can insert, delete, find operations in O(\text{log}(size))$. But, set doesn't keep duplicates, while we need to keep duplicates, so we use multiset. A multiset allows duplicate values.While deleting in a multiset, if you delete by value, all occurences of value are deleted. So, we should first find a value, which will return an iterator and then we'll delete by iterator.
COMPLEXITY:================ PROBLEMS TO SOLVE:================ Problems involving STL containers: AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Sep '15, 19:10

Solved Exactly using the technique as given in editorial using multiset in C++. Here is link to the solution https://www.codechef.com/viewsolution/8216627 answered 21 Sep '15, 00:11
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)
(21 Sep '15, 02:12)

I tried that multiset approach. I got TLE. IDK where I went wrong. I then tried it with the first method using an array/vector that worked. I guess the multiset solution is slow. Here is my solution : https://www.codechef.com/viewsolution/8213947 answered 21 Sep '15, 00:21

How can we use the multiset approach in JAVA? answered 21 Sep '15, 01:22
You can use TreeMap instead of TreeSet using value as counter. http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html
(21 Sep '15, 01:52)

@agarwalaayush In java i used TreeMap<int, int=""> : the keys will be the radius and the values will be the number of time a key appears. Have a look @ my code: https://www.codechef.com/viewsolution/8217289 answered 21 Sep '15, 01:53

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 :P answered 21 Sep '15, 14:21

The procedure simulated in this question is exactly what is used for finding the longest increasing subsequence!!
answered 21 Sep '15, 16:19

Why can't we submit for practice: https://www.codechef.com/problems/STACKS ? nevermind, I found the link: https://www.codechef.com/submit/STACKS answered 22 Sep '15, 14:48

I got TLE. Help include <bits stdc++.h="">define min(a,b) (a<b?a:b)define INF 100000000define MOD 1000000007define ll long longdefine 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_backdefine MP make_pairusing namespace std; typedef map <string,int> Map; typedef pair < int, string > Pair; typedef vector<int> V; int binarysearch(int size,int value,int s[]) { int ans=size,low=0,high=size1; while(low<=high) { int mid=(low+high)/2; if(s[mid]>value) { ans=mid; high=mid1; } 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; } } answered 22 Apr '16, 19:20

why i am getting TLE here my sol >>https://www.codechef.com/viewsolution/11581905 and when i use array instead of stacks using STL, it works answered 21 Sep '16, 02:22
