PROBLEM LINK:
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. 