JTSARTR - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author: Manish Tanwar
Tester: Rahul Dugar
Editorialist: Ritesh Gupta

DIFFICULTY:

Easy-Medium

PREREQUISITES:

DFS, Dynamic Programming, Binary Search, Back-Tracking

PROBLEM:

You are given a tree of N nodes which is rooted at 1. Each node associated a positive integer value with it. The quality of any node is defined as the sum of the size of two subarrays can be found such that:

  • They should belong to the array that can be constructed using the node values from root to that node in the same order.
  • Both the subarrays should be non-decreasing.
  • The concatenation of them also gives a non-decreasing array.

Find the maximum quality over all the nodes.

QUICK EXPLANATION:

  • It could be seen that it is a LIS problem but we are only allowed to have two continuous portions of the array.
  • If you consider this problem for a simple array, it can be solved by idea similar to N*logN LIS DP.
  • To do this in tree, we can first pre-compute the two values for each node x:
    • The longest non-decreasing path that ends at x.
    • The longest non-decreasing path that starts from x.
  • Now, we can do the dfs again and compute whether the second subarray starts from the current node then what would be the best possible length of the subarrays. For this, we already have the answer of one subarray which starts from this index, we need to find the other subarray which has ended somewhere from it. It could be calculated by dynamic programming using backtracking.

EXPLANATION:

Let’s first try to create a precomputation mentioned in the quick explanation which can be done by a single dfs. Start the dfs from the root node and then compute the answer increasing\_upto[i] and increasing\_from[i].

increasing\_upto[i] = the length of non-increasing subarray that ends at node i.

increasing\_from[i] = the length of non-increasing subarray that starts from node i.

Now, let’s try to do the next dfs to find the answer for the problem. For each node, we calculate the longest non-decreasing subways that start from here and others which occur from root to up to this node and concatenating them, we also get non-decreasing sequences.

The one subarray which starts from here, already calculated in previous dfs and other can be calculated by dynamic programming. Now, let’s see how dynamic programming can be applied here.

We can make a 1D table T in which indices represent the length of the non-decreasing array and value present at these indices is equal to the minimum value of last element possible between all possible arrays which have i as a length.

Lemma: If we are filling i-th index then all the index which occurs before it should be filled and table T always has sorted entries.

Proof: As i-th index is filling that means there is a non-decreasing subarray with size i, which means that for any index j (<= i) there should be some value present from this subarray or from some other subarray(as we are storing the minimum value) and it is easy to prove now that the values always in non-decreasing order in table T. It could be easily proved by contradiction.

So, we can use this to compute the answer for the first subarray and we can have binary search over it as the values are in sorted order always. The index value is the size for the first non-decreasing subarray, we are looking for.

We have to modify the table T accordingly and at any point of time, it should have an answer for any single path containing root to some node.

To find the answer for the problem, we just need to take the maximum value of the length of subarray, we are calculaing in the second dfs.

TIME COMPLEXITY:

TIME: O(N * logN)
SPACE: O(N)

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
 
const int M = 5e5+1;
const int inf = (1e9) + 1;
 
int N, A[M], ans;
vector<int> adj[M];
int dp_in[M], dp_out[M];
int DP[M];
 
void dfs1(int v, int p){
	dp_in[v] = 1;
	if(p != -1 && A[v] >= A[p]) dp_in[v] += dp_in[p];
 
	for(int u : adj[v]){
		if(u != p) dfs1(u, v);
	}
 
	dp_out[v] = 1;
	for(int u : adj[v]){
		if(u != p && A[u] >= A[v]){
			dp_out[v] = max(dp_out[v], dp_out[u]+1);
		}
	}
}
 
void dfs2(int v, int p){
	int j = upper_bound(DP+1, DP+N+1, A[v]) - DP;
	j--;
 
	if(j>0) ans = max(ans, dp_out[v] + j);
	
	// make change in DP and store the change
	int index = dp_in[v];
	int old_val = DP[index];
	DP[index] = min(DP[index], A[v]);
 
	for(int u : adj[v]){
		if(u != p){
			dfs2(u, v);
		}
	}
	
	// reverse the change done at this node
	DP[index] = old_val;
}
 
void solve(){
	cin>>N;
	ans = 0;
 
	for(int i=1;i<=N;i++){
		cin>>A[i], adj[i].clear();
		dp_in[i] = dp_out[i] = 0;
		DP[i] = inf;
	} 
	
	for(int i=1;i<N;i++){
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
 
	dfs1(1, -1);
	dfs2(1, -1);
 
	cout<<ans<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
 
	int t; cin>>t;
	while(t--) solve();
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
const int N=500005;
set<pair<int,pii>> lol;
vi gra[N];
int a[N];
pair<int,pii> rem[N],ad[N];
int ans[N],ans2[N];
int sum_n=0,visited=0;
void dfs(int fr, int at) {
	visited++;
	auto it=lol.upper_bound({a[at],{infi,0}});
	int te=0;
	if(it==lol.end())
		te=sz(lol)+1;
	else
		te=(*it).se.se;
	ans2[at]=max(ans2[at],te);
	assert(te>=ans[at]);
	if(te==ans[at]) {
		if(it!=lol.end()) {
			rem[at]=*it;
			lol.erase(it);
		}
		ad[at]={a[at],{at,ans[at]}};
		lol.insert(ad[at]);
	}
	for(int i:gra[at])
		if(i!=fr) {
			if(a[at]<=a[i]) {
				ans[i]=ans[at]+1;
				ans2[i]=ans2[at]+1;
			}
			dfs(at,i);
		}
	if(ad[at].se.fi)
		lol.erase(ad[at]);
	if(rem[at].se.fi)
		lol.insert(rem[at]);
}
 
void solve() {
	lol.clear();
	visited=0;
	int n=readIntLn(2,500000);
//	int n;
//	cin>>n;
	fr(i,1,n) {
		ans[i]=ans2[i]=1;
		gra[i].clear();
		rem[i]=ad[i]={0,{0,0}};
	}
	sum_n+=n;
	assert(sum_n<=1000000);
	fr(i,1,n) {
		if(i!=n)
			a[i]=readIntSp(-1000000000,1000000000);
		else
			a[i]=readIntLn(-1000000000,1000000000);
//		cin>>a[i];
	}
	rep(i,1,n) {
		int u,v;
		u=readIntSp(1,n);
		v=readIntLn(1,n);
		assert(u!=v);
//		cin>>u>>v;
		gra[u].pb(v);
		gra[v].pb(u);
	}
	dfs(1,1);
	int fans=*max_element(ans2+1,ans2+n+1);
	if(fans==1)
		fans=0;
	cout<<fans<<endl;
	assert(visited==n);
}
 
signed main() {
//	freopen("lol.txt","r",stdin);
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=readIntLn(1,1000);
//	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>

#define int long long

using namespace std;
 
const int N = 500010;
 
vector <int> v[N];
int val[N], ans[N], answer;
int increasing_upto[N], increasing_from[N];
 
void dfs1(int curr, int par) {
	if(par != -1 && val[curr] >= val[par]) {
		increasing_upto[curr] += increasing_upto[par];
	}
 
	for(int child : v[curr]) {
		if(child != par) {
			dfs1(child, curr);
 
			if(val[child] >= val[curr]) {
				increasing_from[curr] = max(increasing_from[curr], increasing_from[child]+1);
			}
		}
	}
}
 
void dfs2(int curr, int par, int n) {
	int len_first = upper_bound(ans+1, ans+n+1, val[curr]) - ans - 1;
 
	if(len_first > 0) {
		answer = max(answer, increasing_from[curr] + len_first);
	}
	
	int temp = ans[increasing_upto[curr]];
	ans[increasing_upto[curr]] = min(ans[increasing_upto[curr]], val[curr]);
 
	for(int child : v[curr]) {
		if(child != par) {
			dfs2(child, curr, n);
		}
	}
	
	ans[increasing_upto[curr]] = temp;
}
 
int32_t main() {
    int t;
    cin >> t;
 
    while(t--) {
        int n;
    	cin >> n;
    	
        for(int i=1;i<=n;i++) {
			ans[i] = 1e10;
			v[i].clear();
			increasing_upto[i] = increasing_from[i] = 1;
		}
 
    	for(int i=1;i<=n;i++) {
			cin >> val[i];
		} 
		
		for(int i=1;i<n;i++) {
			int x, y;
			cin >> x >> y;
 
			v[x].push_back(y);
			v[y].push_back(x);
		}

		answer = 0;
	 
		dfs1(1, -1);
		dfs2(1, -1, n);
	 
		cout << answer << endl;
    }
} 

Video Editorial

6 Likes

https://www.codechef.com/viewsolution/38089761

Here’s my solution using a segment tree. It is similar to the editorial (the part where we calculate the length of the longest increasing subarray ending at and starting from some index i).

To get the maximum value, I’ve used a segment tree.

Can anyone help me in finding out for which case my code fails I have tried many random and edge test cases, looks like I am still missing some case link:- https://www.codechef.com/viewsolution/38127837

Does this mean that if there are 2 subarray with length 4 as A = [1,1,2,3] and B = [4,5,6,7], then while filling up the table T, what will be T[i] be storing for i = 1 to 4?