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