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;
}
}