SPOJ - Nested Dolls (MDOLLS)

Problem Statement:
SPOJ - Nested Dolls (MDOLLS)

Summary:
Given a list of dolls with width[i] and height[i] such that doll[i] can be nested inside doll[j] if width[i] < width[j] and height[i] < height[j]. Find the number of minimum resulting nested dolls possible.

Solution:
It is a very interesting (and difficult) problem. I thought it was something to do with longest increasing subsequence (by the way the problem is phrased haha) but actually formally this problem is that of bipartite matching, and there is a greedy approach to solve this problem based on the following observations:

1. Firstly sort all dolls such that the heights are in decreasing order. We will first assume that each heights are unique (later we will extend our approach to the case where there are same heights)
2. We maintain another array nested[i]. Starting from the tallest doll down to the shortest, we will try to fit in the doll to nested[i], by finding a nested doll in nested[i] in which its width is bigger than that of our current doll. Not only that, we want to place it in the one with the minimum width. We then place the doll inside that nested doll and update its new height and weight. Why the minimum one? Because if we place the doll on another one with width bigger than that of minimum width, we can apply the following exchange argument:
Let's assume there exist an optimal arrangement such that current doll doll[i] is not placed on nested[m] of minimum width that satisfy the above requirement. Suppose doll[i] is placed on nested[n], and another doll[j] is placed on nested[m] instead. Then since doll[j] can fit in nested[n], it can also fit in nested[m], and hence we can swap doll[i] and doll[j]. By performing the exchange to all such dolls at all stage, we can transform this optimal arrangement to our greedy arrangement. Hence our greedy arrangement is also optimal.
3. Inductively, we can proof that the dolls in nested[i] is always sorted in increasing width.
4. Lastly, in the case that there are doll with same heights, we sort the widths in increasing order so as to maintain the sortedness of nested[i]

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;


pair<int,int> doll[20003];
vector<pair<int,int> > v;
int N;

bool fn(const pair<int,int>& L, const pair<int,int>& R){
    if(L.first == R.first){
        return L.second > R.second;
    } else {
        return L.first < R.first;
    }
}

void solve(){
    sort(doll, doll+N, fn);
    v.clear();
    v.push_back(doll[N-1]);
    for(int i=N-2;i>=0;--i){
        int hi = v.size()-1, lo = 0, mid;
        while(lo <= hi){
            mid = (hi+lo)/2;
            if(v[mid].first == doll[i].first
            || v[mid].second <= doll[i].second){
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        if(lo == v.size()){
            v.push_back(doll[i]);
        } else {
            v[lo].second = doll[i].second;
            v[lo].first = doll[i].first;
        }
    }
    printf("%d\n", (int) v.size());
}

int main(){
    int tc, u, v;
    scanf("%d", &tc);
    while(tc--){
        scanf("%d", &N);
        for(int i=0;i<N;++i){
            scanf("%d %d", &u, &v);
            doll[i] = make_pair(u,v);
        }
        solve();
    }
    return 0;
}