Infosys || OA || DSE || Power Programmer || 24th April || 2022

Question

Answer 1

The solution involes game theory + dynamic programming on tree . 

Code(C++) : 

//Author : Kumar K
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ; 
vector <ll> G[200000];
ll alice[200000];
ll bob[100005];
ll parent[200005];
vector <ll> used(100005,0);
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
 
        if (hash1 != hash2) {
            return hash1 ^ hash2;             
        }
         
        // If hash1 == hash2, their XOR is zero.
          return hash1;
    }
};

unordered_map<pair<ll, ll>, ll, hash_pair> um;

void dfs(ll node){
    used[node] = 1 ; 
   // cout<<node<<" ";
    for(auto u : G[node]){
        if(used[u]==0){
            parent[u] = node ; 
            dfs(u);
        }
    }
    ll ww = 0 ; ll qq = 1e18 ; 
    ll ans = 0 ; 
    for(auto children : G[node]){
        
        if(children!=parent[node]){
            ww = max(ww,um[{children,node}] + bob[children]) ; 
            qq = min(qq,-1*um[{children,node}] + alice[children]) ; 
        }
    }
    alice[node] = ww ; 
    if(qq==1e18){
        bob[node] = 0 ; 
    }
    else
    {
        bob[node] = qq ; 
    }
    //cout<<node<<" "<<alice[node]<<" "<<bob[node];cout<<endl;
}

int main() {
    int N ; 
    cin>>N ; 
    int i = 1 ; parent[i] = -1;
    while(i<=N-1){
        int x,y,z ; 
        cin>>x>>y>>z ; 
        G[x].push_back(y);
        G[y].push_back(x);
        um[{x,y}] = z; 
        um[{y,x}] = z ; 
        i++;
    }
    dfs(1);
    cout<<alice[1];
    return 0;
}

 

Input : 

6 
1 2 9 
1 3 5
3 4 5
3 5 4
6 2 3 

Output : 6