Codeforces Round #277 (Div. 2) Problem E. LIS of Sequence

Follow Up to this post.

Problem Statement:
E. LIS of Sequence

Solution:
This problem is quite nice to think about :D. Before attempting this problem, it might be useful to have a knowledge beforehand on how to solve LIS problem in \(O(N\lg{N})\) complexity using binary search.

This problem is more or less an extension to that idea. First we have an array of stacks stack[i] which is initialized with the following conditions:
1. the size of the array is initially 1.
2. push \(a_1\) into stack[0], so stack[0] contains \(a_1\).
Now we iterate from \(a_2,\ldots\) onwards till the end of the elements:
1. find the position of the maximum element amongst all elements on top of the stacks such that \(a_i\) is equal or larger.
2. if such position exist, push our current \(a_i\) into that stack. Otherwise, we add a new stack (hence incrementing the size of the array by 1) and push \(a_i\) to that newly created stack.



From this representation, we can easily conclude for each \(i\), which are present in any of the LIS. We can think of the LIS as a path on a graph. To see whether \(i\) is in the LIS, we check whether there exist a path from \(i\) to any elements that are in the last stack. To find those who always appear in every LIS, we have to check whether the number of elements that are present in LIS at the stack occupied by \(i\) is equal to exactly one.

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

vector<vector<int> > stack;
vector<vector<int> > visited;
int val[100005];
int pos[100005];
int vis[100005];
int cnt[100005];
int N;

void arrange(){
    int hi, lo, mid, cur;
    stack.push_back(vector<int>());
    stack[0].push_back(0);
    pos[0] = 0;
    for(int i=1;i<N;++i){
        lo = 0;
        hi = stack.size()-1;
        while(lo <= hi){
            mid = (lo+hi)/2;
            cur = stack[mid].back();
            if(val[cur] < val[i]){
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        if(lo < stack.size()){
            stack[lo].push_back(i);
            pos[i] = lo;
        } else {
            stack.push_back(vector<int>());
            stack[lo].push_back(i);
            pos[i] = lo;
        }
    }
}

void check(){
    int hi,lo,mid,cur, comp;
    int M = stack.size();
    visited = vector<vector<int> >(stack.size()+3);
    for(int i=0;i<stack[M-1].size();++i){
        vis[stack[M-1][i]] = 1;
        ++cnt[pos[stack[M-1][i]]];
        visited[M-1].push_back(stack[M-1][i]);
    }
    for(int k=M-2;k>=0;--k){
        for(int j=0;j<stack[k].size();++j){
            cur = stack[k][j];
            lo = 0; hi = visited[k+1].size()-1;
            while(lo<=hi){
                mid = (lo+hi)/2;
                comp = visited[k+1][mid];
                if(cur > comp){
                    lo = mid+1;
                } else {
                    hi = mid-1;
                }
            }
            hi = visited[k+1].size()-1;
            while(lo<=hi){
                mid = (lo+hi)/2;
                comp = visited[k+1][mid];
                if(val[cur] >= val[comp]){
                    hi = mid-1;
                } else {
                    vis[cur] = 1;
                    ++cnt[pos[cur]];
                    break;
                }
            }
            if(vis[cur]) visited[k].push_back(cur);
        }
    }
}

void solve(){
    for(int i=0;i<N;++i){
        if(!vis[i]) printf("1");
        else {
            if(cnt[pos[i]] == 1) {
                printf("3");
            } else {
                printf("2");
            }
        }
    }
    printf("\n");
}

int main(){
    scanf("%d", &N);
    for(int i=0;i<N;++i){
        scanf("%d", &val[i]);
        vis[i] = cnt[i] = 0;
    }
    arrange();
    check();
    solve();
    return 0;
}