LIS #1 LIS on Trees

F - LIS on Tree

Problem Statement: here

Solution:

There is more than one way to solve this problem. We shall see two different implementations. 

The first implementation is an easy version and it uses LIS in O(nlogn) approach. We will apply dfs from the root node and insert each element as if we do it in a linear array. But, the only difference is, once the subtree query is finished, replace the old version for the next subtree.

The second implementation involves using segment trees to answer the LIS in O(nlogn) approach. I will include this approach and its brief explanation as to my next post in the series on segment trees.

So, stay tuned with it! 

To learn how to compute LIS in O(nlogn) check my this post

Using the Vector for LIS:  AC in 121mS

V(ll) adj[200005]; ll n,k; ll val[200005]; ll dp[200005]; V(ll) v; // declaring vector void dfs(ll node, ll parent){ ll rep = -1; auto it = lower_bound(all(v),val[node]); ll ind = it - v.begin(); if (it != v.end()) { rep = *it; *it = val[node]; } else v.PB(val[node]); dp[node] = v.size(); for(ll child:adj[node]){ if (child != parent){ dfs(child,node); } } if (rep != -1){ v[ind] = rep; } else{ v.pop_back(); } } void solve() { cin >> n; rep(i,1,n+1) cin >> val[i]; rep(i,0,n-1){ ll x,y; cin >> x >> y; adj[x].PB(y); adj[y].PB(x); } dfs(1,-1); rep(i,1,n+1) cout << dp[i] << endl; }

Using a Set for LIS: AC in 175mS

V(ll) adj[200005]; ll n,k; ll val[200005]; ll dp[200005]; set<ll> s; void dfs(ll node, ll parent){ ll rep = -1; auto it = s.lower_bound(val[node]); if (it != s.end()) { rep = *it; s.erase(it); } s.insert(val[node]); dp[node] = s.size(); for(ll child:adj[node]){ if (child != parent){ dfs(child,node); } } s.erase(val[node]); if (rep != -1){ s.insert(rep); } } void solve() { cin >> n; rep(i,1,n+1) cin >> val[i]; rep(i,0,n-1){ ll x,y; cin >> x >> y; adj[x].PB(y); adj[y].PB(x); } dfs(1,-1); rep(i,1,n+1) cout << dp[i] << endl; }

Using a multi set for  LIS: AC in 186mS

V(ll) adj[200005]; ll n,k; ll val[200005]; ll dp[200005]; multiset<ll> s; void dfs(ll node, ll parent){ ll rep = -1; auto it = s.lower_bound(val[node]); if (it != s.end()) { rep = *it; s.erase(it); } s.insert(val[node]); dp[node] = s.size(); for(ll child:adj[node]){ if (child != parent){ dfs(child,node); } } s.erase(s.find(val[node])); if (rep != -1){ s.insert(rep); } } void solve() { cin >> n; rep(i,1,n+1) cin >> val[i]; rep(i,0,n-1){ ll x,y; cin >> x >> y; adj[x].PB(y); adj[y].PB(x); } dfs(1,-1); rep(i,1,n+1) cout << dp[i] << endl; }

Questions to look ahead?

1. https://open.kattis.com/problems/neverjumpdown 
1. I will upload the solution to this soon.
2. You can leave a comment if you find some exciting problems on LIS over trees

Understanding the NlogN Approach for LIS

O(nlogn) algorithm for The LIS

We already know about the quadratic time LIS approach using Dynamic Programming.

Today, we gonna see and understand the shortest O(nlogn) approach for LIS.

Let the sequence be A = {3,6,5,4,7,10}

We know the LIS lengths for each index is {1,2,2,2,3,4}

Approach:

We will loop over the array and store the LIS at each index in a separate vector. If the incoming element is smaller than any element in our LIS, then we take the lower bound to find the next greater element and replace it with the current element. This is because replacing the element will not change the LIS length and also if a smaller element is added to LIS, then we can get more advantages from future elements. 

For example let our sequence be just S ={ 3, 6, 4, 5}

If we consider the LIS for the first index = {3}

If we consider the LIS for the Second index = {3,6}

But, when we consider the LIS for the third index, we have two options: {3,6} or {3,4}.

We will choose {3,4} because 4 is less than 6. The advantage will be clear on the very next index.

When we consider the LIS for the fourth index = {3,4,5}. But, if we had chosen {3,6} on the third index, we would have missed the 5 because {3,6,5} is not LIS. 

So, at every possible index, we just find the lower_bound of the current element and if it exists in the vector of LIS, we replace that with our element. If it does not exist, we simply push our element because it is the largest element in our LIS. 

To know the LIS at any particular index, we can simply check out the size of our vector.

vector<int> v;
for (int i = 0; i < n; i++) {
    auto it = lower_bound(v.begin(), v.end(), a[i]);
    if (it != v.end()) *it = a[i];
    else v.push_back(a[i]);
}
return v.size();

This finds a strictly-increasing LIS, but you can easily modify it to find the longest nondecreasing sequences by changing lower_bound to upper_bound.

Questions for Practice ??

1. https://www.spoj.com/problems/LMIS/
2. https://www.spoj.com/problems/ELIS/