# 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
STETSKLX

Problems involving STL containers:
Running Median
ANUMLA

### AUTHOR’S, TESTER’S SOLUTIONS:

2 Likes

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

1 Like

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

How can we use the multiset approach in JAVA?

@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

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: https://www.codechef.com/submit/STACKS

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 >>https://www.codechef.com/viewsolution/11581905 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.

Can anyone tell me why I am getting TLE . T=O(NlogN) of my solution.

My code

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?