19 months ago

pushpendra.hpx2001 • 20

Question1

Tree Decrements

Q1 PART 1

A tree can be represented as an unweighted undirected graph of t nodes nodes

numbered from 1 to t nodes and t nodes - 1 edges where the ith edge connects the

nodes numbered t_from[i] and t_to[i].

A value val[i] is associated with the h node. In a single operation, two nodes can be

selected, and their values can be decremented by 1 at a cost equal to the distance

between the two nodes, i.e., the number of edges in the simple path between them.

It is possible to select the same node for the operation and decrease its value by 2 at

the cost of 0.

Given the tree, t, and the values val, find the minimum cost to decrease the values of

all the nodes to 0. It is guaranteed that the values of all the nodes can be decreased

to exactly 0.

Example

Suppose t_nodes = 3. t_from = [1,1]. t_to = [2, 3], and val = [3, 1, 2].

The optimal strategy is to choose nodes 1 and 2 at cost 1, The values become (2, 0, 2).

Now nodes 1 and 1, followed by 3 and 3, can be chosen, each with a cost of 0. Thus

the total cost is 1 + 0 + 0 = 1,

Function Description

Complete the function getMinCost in the editor below

getMinCost has the following parameters:

Q1 Part 2

Function Description

Complete the function getMinCost in the editor below,

getMinCost has the following parameters:

int val[t_nodes]: the values of the nodes

int t_nodes: the number of nodes in the tree

int t_from[t_nodes - 1]: an end of an edge

int t_to[t_nodes - 1): an end of an edge

Returns

int the minimum possible cost to decrease all the values to 0

Constraints

• 25 ≤ nodes ≤ 10^5

• 1 ≤ t_from[i]. t.to[i] ≤ t_nodes

• 0 ≤ val[i] ≤ 100

• The input guarantees that there always exists a way to pair all the elements in val.

Input Format For Custom Testing

The first line contains an integer, nodes, which denotes the number of elements

in val.

Each line /of the n subsequent lines (where 0 ≤ / < n) contains an integer that

denotes valli.

The first line contains two space-separated integers, (edges, t nodes - 1, which

denotes the number of nodes and edges in the graph, respectively.

The next _nodes - 1 lines contain two space-separated integers _from[i and

1 toff that denotes an edge from t from and t toll.

v Sample Case 0

Sample Input For Custom Testing

STDIN

FUNCTION

val[] size n • 3

val = [2, 1,

t_nodes = 3, t edges = t_nodes • 1 •

t_from = [1, 1), t.to = [2, 3]

Sample Output

The first line contains an integer, nodes, which denotes the number of elements

in val.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer that

denotes va[i].

The first line contains two space-separated integers, t_edges, t_nodes - 1, which

denotes the number of nodes and edges in the graph, respectively.

The next_nodes - 1 lines contain two space-separated integers ( from and

t_to[i] that denotes an edge from t_from[i] and t_to[i].

Sample Input for Custom Testing

STDIN                                  FUNCTION

3                     ->                 val[]  size n = 3

2                     ->                 val = [2,1,1]

1

1

3  2                ->                   t_nodes = 3 , t_edges = t_nodes - 1 = 2 

1  2                ->                   t_from = [1,1] , t_to = = [2,3]

1  3

Sample Output

2

Q1 PART 3

The optimal strategy is to choose the nodes (1, 2) and (1, 3), respectively, in the two
operations.

STDIN                                      FUNCTION 

5                    ->                      val[] size n = 5 

3                    ->                      val = [3 , 2 , 4 , 2 ,5 ]   

2

4

2

5

5    4            ->                    t_nodes = 5 , t_edges = t_nodes - 1 = 4

1    2            - >                   t_from = [ 1, 1, 3 ,5] , t_to = [2 , 3 , 4 , 5 ]

1    3

3    4

3    5

5 Questions ( 2 MCQ + 3 Coding Questions ) MCQs were based on CSRF attack & diff between ArrayList & LinkedList.

Coding Q.1 => 2 Pointer Question Easy Q.2 => Minimum Swaps required to Sort an array Q.3 => Minimum time to complete all processes if at a particular instant we can have infinite computing capacity.

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Tree Decrements

First we make some observations:

Claim: Each node will be involved in atmost one decrement operation that is operated on two different nodes in an optimal solution.

Proof: Lets assume that node x is involved in two such operations. Then we have the following two cases:

• It is involved with the same node (say y) in both the operations. Then we can always perform the decrement operations on node x and node y separately (i.e. we decrease the values of x and y by 2 separately) with a cost of 0 which is strictly better.
• It is involved with two different nodes (say y and z) in the operations. Then we can notice that dist(y,z) <= dist(x,y) + dist(x,z). Hence we can decrease the value of node x by 2 separately and perform an operation on node y and node z for a cost of dist(y,z) which is either better or the same.

Thus it makes sense to decrease even valued nodes to 0 by performing the operation on themselves while perform exactly one operation for odd valued nodes. Since it is given that there always exists a solution, the odd numbered values must pair up (i.e. they must be even). So now we have reduced the problem to an easier problem --- "Given a tree and some special nodes, we have to find the minimum cost to pair up the special nodes such that the cost of pairing is equal to distance between two nodes."

Now to solve this, we can add the contribution of each edge in the answer, i.e., if we can determine the number of pairs for which a certain edge will be involved, we can find out the answer by summing the contribution for all the edges. Now notice that an edge will be involved in a pairing if and only if the subtree corresponding to it contains an odd number of special nodes. Thus we can find the contribution of each in a single DFS and calculate the ans in a time complexity of O(N).

16 months ago

Yash kumar yadav • 10

Mumbai

#include <bits/stdc++.h>
  using namespace std;
int n ; vector<vector < int > > g; 
vector < int > in, vis ; 
  int main() {
    int t ; cin>>t ; 
    while ( t-- ) { 
    cin >>n ; 
      g= vector < vector <int > > ( n ) ; 
    vis=  in = vector < int > ( n, 0 ) ; 
      
      for( int i =0  ; i< n; i++){
        int k ; cin>> k ;
        in[i] = k ; 
        for(int j = 0 ;j < k ;j ++){
           int a ; cin>> a; a--; 
            g[a].push_back(i); 
        }
        
      }
   int ans =0 ; 
   queue< int > q ; set < int > s ; 
   for(int i= 0; i< n;i++){ 
     if ( in[i] ==0 ) s.insert(i ) ; 
     }int cnt =0; 
     while ( true){ 
       ans++; 
    
     int f= 0 ; 
     int val= cnt;
    
     
     cnt = val; 
     int lst = -1 ; 
     
     if ( s.empty())break; 
     vector < int > sm; 
     while (!s.empty()&& *s.rbegin()>lst){
       int x = *s.begin(); 
       lst= x ; val++; 
       for(auto & ch: g[x]){
         in[ch]--; 
         if (in[ch]==0 ){   
           if(ch>lst){s.insert(ch); }
         else sm.push_back(ch); }
       }
       s.erase(s.begin()); 
     }if (cnt==val ) break; 
     else cnt = val; 
     if ( sm.empty())continue; 
     else { 
       for(auto&x : sm  )s.insert(x ) ; 
     }
     } 
     
     if ( cnt ==n ) { cout << ans -1<<endl;  } 
     else cout <<-1 <<endl;
    
  }
  }