You are not logged in. Please login at www.codechef.com to post your questions!

×

# STACKS - Editorial

Author: Kanstantsin Sokal
Tester: Jingbo Shang
Editorialist: Lalit Kundu

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 top-most 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:

• If there is at least one stack such that Mike can put the current disk on the top of the stack without making it invalid, then he chooses the stack with the smallest top disk radius strictly greater than the radius of the current disk, and puts the current disk on top of that stack.
• Otherwise, Mike makes a new stack containing only the current disk.

Your task is to output the set of the stack top disk radii after the algorithm is done in non-decreasing order.

# QUICK EXPLANATION:

======================
We build our solution incrementally and at each step we maintain an sorted array $S$ storing the top radii of all the stacks present. Using binary search, we can find the correct stack for a new disk. After replacing the top radii of such a stack, array $S$ still remains sorted.

# EXPLANATION:

================
We are going to build our solution incrementally. That is, at each step we'll store the stacks we already have formed and then find the correct position for a disk and put it there.

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_{j-1} \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.

A[N] = input
S[N]
current_size = 0

for i=0 to N-1:
// find the first idx in the sorted array S, such that S[idx] > a[i].
// this can be done using a simple binary search.
int idx = binarySearch(size, a[i]);

S[idx] = A[i]

if(idx==size) size++;

for i=0 to size-1:
print S[i]

//searches for first index idx such that S[idx] > val
int binarySearch(size, val):
int lo = 0, hi = size - 1;
int ans = size;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (a[mid] > x) {
ans = mid;
hi = mid - 1;
}
else {
lo = mid + 1;
}
}
return ans;
}

You can also use built-in 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:

A[N] = input
Data Structure DS;

for i=0 to N-1:
x = Find in DS smallest number greater than A[i]

if no such number:
DS.insert(A[i])
else:
//we place A[i] on the stack with top radii x
DS.delete(x)
DS.insert(A[i])

print DS in sorted order

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. A[N] = input multiset <int> myset; multiset <int>::iterator it; for i=0 to N-1: //here we first insert and then we find smallest number greater than A[i] myset.insert(A[i]) it = myset.find(A[i]) //right now, it points to A[i] //since multiset keeps elements ordered //so, next element should be the element we are looking for //also, sets have bidirectional iterators and can be incremented/decremented easily it++; //no such element present if it == myset.end(): DS.insert(A[i]) else: myset.erase(it) //traverse over multiset to print values //values inside multiset are already sorted for(it=myset.begin(); it!=myset.end(); it++) print (*it) # COMPLEXITY: ================$O(N \text{log} N)$, since each operation on multiset takes$O(\text{log}N)$, or in case of binary search, it takes$O(\text{log}N)$at each step. # PROBLEMS TO SOLVE: ================ Problems involving binary search: STRSUB ASHIGIFT STETSKLX Problems involving STL containers: Running Median ANUMLA # AUTHOR'S, TESTER'S SOLUTIONS: This question is marked "community wiki". asked 19 Sep '15, 19:10 3.0k93162187 accept rate: 12% 0★admin ♦♦ 19.0k348495531 11 Answers:  1 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++; answered 21 Sep '15, 16:19 5★yash_15 518●1●7●16 accept rate: 2%  0 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 6★likecs 3.4k●13●56 accept rate: 9% 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)  0 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 176●1●7 accept rate: 4% 2 You have two level of 'for' loop in line 54 and 61. The complexity is O(n^2). (21 Sep '15, 00:30)  0 How can we use the multiset approach in JAVA? answered 21 Sep '15, 01:22 1●1 accept rate: 0% 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)  0 @agarwalaayush In java i used TreeMap : 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 11●1 accept rate: 0%  0 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 answered 21 Sep '15, 09:22 893●2●9●33 accept rate: 10% O(n^2) wont pass. As editorial says you need to Have a binary search to find a valid stack to be Piled. (21 Sep '15, 20:45)  0 Very nice problem, taught many things :) answered 21 Sep '15, 13:39 101●1●6 accept rate: 0%  0 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 942●1●8 accept rate: 8%  0 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 5★bohuss 21●3 accept rate: 0% 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<int> 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; } } answered 22 Apr '16, 19:20 2★vickycod 21112 accept rate: 6%  0 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 3★moodies 21●1 accept rate: 0%  toggle preview community wiki: Preview ### Follow this question By Email: Once you sign in you will be able to subscribe for any updates here By RSS: Answers Answers and Comments Markdown Basics • *italic* or _italic_ • **bold** or __bold__ • link:[text](http://url.com/ "title") • image?![alt text](/path/img.jpg "title") • numbered list: 1. Foo 2. Bar • to add a line break simply add two spaces to where you would like the new line to be. • basic HTML tags are also supported • mathemetical formulas in Latex between$ symbol

Question tags:

×14,366
×995
×810
×52
×8

question asked: 19 Sep '15, 19:10

question was seen: 5,407 times

last updated: 21 Sep '16, 02:22