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

×

STACKS - Editorial

PROBLEM LINK:

Practice
Contest

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

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

setter
tester

This question is marked "community wiki".

asked 19 Sep '15, 19:10

darkshadows's gravatar image

5★darkshadows ♦
3.0k91161186
accept rate: 12%

edited 09 Feb '16, 17:49

admin's gravatar image

0★admin ♦♦
15.9k347484508


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

link

answered 21 Sep '15, 00:11

likecs's gravatar image

6★likecs
3.1k636
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) rcsldav20175★

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

link

answered 21 Sep '15, 00:21

dollarakshay's gravatar image

4★dollarakshay
10615
accept rate: 8%

edited 21 Sep '15, 00:22

2

You have two level of 'for' loop in line 54 and 61. The complexity is O(n^2).

(21 Sep '15, 00:30) dreamoon46★

How can we use the multiset approach in JAVA?

link

answered 21 Sep '15, 01:22

agarwalaayush's gravatar image

3★agarwalaayush
11
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) notimesea6★

@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

link

answered 21 Sep '15, 01:53

daoudakaleyire's gravatar image

3★daoudakaleyire
111
accept rate: 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

link

answered 21 Sep '15, 09:22

dragonemperor's gravatar image

3★dragonemperor
8732931
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) shivam97534★

Very nice problem, taught many things :)

link

answered 21 Sep '15, 13:39

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 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

link

answered 21 Sep '15, 14:21

xariniov9's gravatar image

6★xariniov9
93218
accept rate: 8%

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++;
link

answered 21 Sep '15, 16:19

yash_15's gravatar image

5★yash_15
5081716
accept rate: 2%

Why can't we submit for practice: https://www.codechef.com/problems/STACKS ?

nevermind, I found the link: https://www.codechef.com/submit/STACKS

link

answered 22 Sep '15, 14:48

bohuss's gravatar image

5★bohuss
213
accept rate: 0%

edited 22 Sep '15, 14:53

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; } }

link

answered 22 Apr '16, 19:20

vickycod's gravatar image

2★vickycod
21112
accept rate: 6%

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

link

answered 21 Sep '16, 02:22

moodies's gravatar image

3★moodies
211
accept rate: 0%

toggle preview
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:

×11,590
×780
×594
×52
×8

question asked: 19 Sep '15, 19:10

question was seen: 4,690 times

last updated: 21 Sep '16, 02:22