IARANK - Editorial

Prerequisite : Ordered Set or BruteForce

Problem :- There are N rich merchants who continuously visit the king’s hall. Print the rank of each merchant based on their wealth, relative to the previous merchants who visited the hall.

Solution :- There are two approaches for solving this problem: one is the brute force method, and the other is the optimized version.
BruteForce Logic :-
Expected time complexity O(n*n)
Space Complexity O(N)
For each merchant, iterate over the previously visited merchants, check the number of merchants with more wealth, and assign rank as the wealthier merchant’s rank plus one.

Optimized Logic : -
Expected time complexity O(n*logn)
Space Complexity O(N)

We can optimize this code using an ordered set.
Ordered set is a policy based data structure that keeps the unique elements in sorted order. It performs all the operations as performed by the set data structure in STL in log(n) complexity and performs two additional operations also in log(n) complexity .
order_of_key (k) : Number of items strictly smaller than k .
find_by_order(k) : K-th element in a set (counting from zero).
Logic: Store the wealth of merchants in an ordered set. When a new merchant arrives, use the ‘order_of_key’ function to find the number of merchants with less wealth than our current merchant. Subtract this value from the size of the ordered set to determine the rank of our merchant.
C++ Solution :-
Brute Force code:

#include <bits/stdc++.h>
using namespace std;

int main() {
    // your code goes here
    int n;
    cin>>n;
    vector<int>v1;
    for(int i=0;i<n;i++){
    	int n1;
    	cin>>n1;
    	int rank = 1;
    	for(auto e:v1){
        	if(e>n1)rank++;
    	}
    	cout<<rank<<"\n";
    	v1.push_back(n1);
    }

}

Optimized Code :

include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin>>n;
	ordered_set s;
	int a[n];
	for ( int i = 0 ; i < n ; i++ )
	{
	cin>>a[i];
    	s.insert(a[i]);
    	cout<<( s.size() - s.order_of_key(a[i]))<<”\n”;
	}
	return 0;
}

In python, we can use this code -

m = []
def bisect(i, l, r):
    if l > r:
        return l
    c = (l+r)//2
    if m[c] < i:
        return bisect(i, l, c-1)
    else:
        return bisect(i, c+1, r)
for _ in range(int(input())):
    r = int(input())
    if not m or m[-1] >= r:
        m.append(r)
        print(len(m))
    else:
        pos = bisect(r, 0, len(m)-1)
        m.insert(pos, r)
        print(pos+1)