TREEMIN - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Lavish Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Depth first search, trees, dynamic programming (dp)

PROBLEM:

Given a rooted tree (at vertex 1) with N vertices with each vertex i having value A_i, two players Alice and Bob play a game. The game is played alternatively with Alice starting first with a pointer at vertex 1. In each turn, the player (who is currently at vertex i) can move the pointer to a child vertex of i and adds the value of that child vertex to that score. The game ends when a player is unable to make a move. Alice wants to minimize the score and Bob wants to maximize the score. Now we need to find out what would be the final score at the end if each player can skip their move atmost K times.

QUICK EXPLANATION:

  • The final answer is always independent of K because if one player makes a skip in order to favour them, the other player can always make a skip right away in order to avoid such scenario.

  • Thus, let us solve for the modified problem where there is no option to skip a move.

  • Now the problem can be solved by 2D dp. Let player 0 be Alice and player 1 be Bob. dp_{i,j} be the total score obtained when player j starts the game with the pointer at vertex i.

  • dp_{i,0} = \min_{\forall c \in children(i)} (dp_{c,1} + A_c)

  • dp_{i,1} = \max_{\forall c \in children(i)} (dp_{c,0} + A_c)

  • The final answer will be dp_{1,0} .

EXPLANATION:

First let us solve the problem with having K=0 i.e, no player can skip their moves. Let us assume player 0 is Alice and player 1 is Bob. Let us also assume that children(i) is the list consisting of every child of veretx i.

The key idea to solve this is by using dynamic programming. We need to define a state. Let dp_{i,j} denote the final score obtained if the game starts with player j and the pointer is at vertex i. Here 1 \leq i \leq N and 0 \leq j \leq 1.

The base case will be as follows: When the vertex i is a leaf, dp_{i,0} = dp_{i,1} = 0.

If the vertex i is not a leaf, we can perform the transitions as follows:

  • dp_{i,0} = \min_{\forall c \in children(i)} (dp_{c,1} + A_c) . This is because person 0 wants to minimize the score and therefore we find the minimum over all the children that person can move the pointer to.

  • dp_{i,1} = \max_{\forall c \in children(i)} (dp_{c,0} + A_c) . This is because person 1 wants to maximize the score and therefore we find the maximum over all the children that person can move the pointer to.

Doing dfs on tree will help us compute all the dp values. dp_{1,0} will be the answer for this case.

Now let us come back to our original problem: What happens if K>0 ? I claim that even if K>0, our final answer is the same as the case with K=0. We can argue about this in the following way:

Suppose Alice need to make a move when the pointer is at vertex i. Assume no skips by any player happened till now. Now consider a scenario where Alice makes a skip that reduces the total score. I claim that this scenario cannot happen as Bob can always make a skip right away in order to avoid such scenario.

Similarly, we can argue that Bob cannot make the first skip.

Therefore, the final answer is dp_{1, 0} which is independent of K.

TIME COMPLEXITY:

O(N) for each testcase.

SOLUTION:

Editorialist's solution

#include<bits/stdc++.h>
#define int long long int
using namespace std;

void dfs(int i,int p,vector<int>& a,vector<vector<int>>& tree,vector<vector<int>>& dp)
{
    int min1=INT64_MAX, max1=INT64_MIN;
    for(int child: tree[i])
    {
        if(child==p)
        continue;

        dfs(child,i,a,tree,dp);
        min1=min(min1,dp[child][1]+a[child]);
        max1=max(max1,dp[child][0]+a[child]);
    }

    if(min1==INT64_MAX)
    {
         dp[i][0]=dp[i][1]=0;
         return;
    }

    dp[i][0]=min1;
    dp[i][1]=max1;

}

int32_t main()
{
    int tests;
    cin>>tests;
    while(tests--)
    {
        int n,k;
        cin>>n>>k;
        
        vector<int> a(n+1);
        vector<vector<int>> tree(n+1);
        vector<vector<int>> dp(n+1,vector<int>(2)); //0 means Alice 1 means Bob

        for(int i=1;i<=n;i++)
        cin>>a[i];

        for(int i=1;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            tree[x].push_back(y);
            tree[y].push_back(x);
        }

        dfs(1,-1,a,tree,dp);
        cout<<dp[1][0]<<endl;

    }
    return 0;
}

Setter's solution
#define ll long long
#define dd long double
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#define tll tuple<ll ,ll , ll> 
#define pll pair<ll ,ll> 
#include<bits/stdc++.h>
/*#include<iomanip>   
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<bitset>*/
dd pi = acos(-1) ;
ll z =  1000000007 ;
ll inf = 100000000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 =  202976689 ;
ll mod2 =  203034253 ;
ll fact[100] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ;    return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 , g; g = e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return g ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r|| (n < 0) || (r < 0)) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
ll seed;
mt19937 rnd(seed=chrono::steady_clock::now().time_since_epoch().count()); // include bits

const int N = 100005 ;
ll val[N] ;
ll vis[N] ;
ll dp[N][2] ; // {min , max}
vector<ll> adj[N] ;

void dfs(vector<ll> adj[], ll u)
{
    vis[u] = 1 ;
    ll flag = 0 ;
    ll mini = inf , maxi = -inf ;
    fo(i , adj[u].size())
    {
        ll v = adj[u][i] ;
        if(vis[v] == 1)
            continue ;
        dfs(adj , v) ;
        flag = 1 ;

        mini = min(mini , dp[v][1]) ;
        maxi = max(maxi , dp[v][0]) ;
    }

    if(flag == 0)
    {
        dp[u][0] = 0 ;
        dp[u][1] = 0 ;
    }
    else
    {
        dp[u][0] = mini ;
        dp[u][1] = maxi ;
    }
    dp[u][0] += val[u] ;
    dp[u][1] += val[u] ;
    return ;
}

void solve()
{
    ll n , k ;
    cin >> n >> k ;
    fo(i , n)
        adj[i].clear() ;
    
    fo(i , n)
    {
        cin >> val[i] ;
        vis[i] = 0 ;
        dp[i][0] = inf ;
        dp[i][1] = -inf ;
    }

    
    fo(i , n-1)
    {
        ll u , v ;
        cin >> u >> v ;
        u-- ; v-- ;
        adj[u].pub(v) ;
        adj[v].pub(u) ;
    }
    dfs(adj , 0) ;
    cout << dp[0][0] << endl ;
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
  
    
 
        ll t ;
        cin >> t ;
        fo(i , t)
            solve() ;
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> dfs(int x, int pr, vector<int> tr[], ll a[]){
  ll mx = LLONG_MIN;
  ll mn = LLONG_MAX;
  for(int i = 0; i < tr[x].size(); i++){
    int y=tr[x][i];
    if(y != pr){
      vector<ll> temp = dfs(y, x, tr, a);
      mx = max(mx, temp[0]);
      mn = min(mn, temp[1]);
    }
  }
  if(mx == LLONG_MIN){
    mx = 0;
    mn = 0;
  }
  mn += a[x - 1];
  mx += a[x - 1];
  return {mn, mx};
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int n, k;
    cin>>n>>k;
    ll a[n];
    for(int i = 0; i < n; i++){
      cin>>a[i];
    }
    vector<int> tr[n+1];
    for(int i = 0; i < n - 1; i++){
      int u, v;
      cin>>u>>v;
      tr[u].push_back(v);
      tr[v].push_back(u);
    }
    cout<<dfs(1, 0, tr, a)[0]<<"\n";
  }
  return 0;
}


Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

3 Likes

can anyone help
https://www.codechef.com/viewsolution/51464094

TLE in Task#1

I have an idea for a second version of this problem and I would like to share it for an upcoming contest. Where can I do this properly?

Problem Link attached redirects to a different problem, kindly fix this.

1 Like

2nd DP state is actually redundant since we know on which level who will be operating. code

1 Like

Thanks. Fixed!

#include<bits/stdc++.h>
using namespace std;

void dfs(int node,vector<vector> &adj,vector<vector> &dp,vector&cost){

//agar me yaha se shuruat karta hu toh mujhe kya milega bas yahi pata karna hai

if(dp[node][0]!=-1){
    return;
}

else if(adj[node].size()==0){
    dp[node][0]=cost[node];
    dp[node][1]=cost[node];
    return;
}


int maximum=INT_MIN;
int minimum=INT_MAX;

for(int i=0;i<adj[node].size();i++){
    
    int child=adj[node][i];
    
    //yaha se shuru karte hai toh kya milega
    dfs(child,adj,dp,cost);  //is child ke liye set ho gaya hoga
    minimum=min(minimum,dp[child][1]);
    maximum=max(maximum,dp[child][0]);
    
}


dp[node][0]=cost[node]+minimum;
dp[node][1]=cost[node]+maximum;

}

int main(){
int t;
cin>>t;

while(t--){
    
    int n,k;
    cin>>n>>k;
    
    vector<int> cost(n);
    
    for(int i=0;i<n;i++){
        cin>>cost[i];
    }
    
    //i am assuming that they will give me the right thing
    
    vector<vector<int>> adj(n);
    vector<vector<int>> dp(n,vector<int>(2,-1));  //0 for alice and 1 for bob
    
    
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        adj[u].push_back(v);                                                                                                                                    
    }
    
    dfs(0,adj,dp,cost);
    cout<<dp[0][0]<<endl;
}

return 0;

}

/**
This code is failing for the task#7, i am unable to find any mistake in the code, please help me find the mistake.
Thanks

**/

I am getting WA on test case-7;
can any help what I am missing

submission link

  1. I am using a simple post-order traversal of on the tree +
  2. using the level of the tree to identifying the move