Perfect Partition

Moderate
0/80
profile
Contributed by
5 upvotes
Asked in company
Uber

Problem statement

In the Ninja world, assets owned by a person are represented by a tree, where the total asset value is equal to the sum of all its vertices.

A wealthy father wants to split all his assets between his two children, he has appointed you to help him. You are given a tree containing ‘N’ vertices, vertices are numbered from 0 to N-1, you are also given an array ‘Assets’ denoting the asset-value of ith vertex.

Splitting of assets can simply be done by removing an edge from the tree, this results in the formation of two trees. You have to remove an edge such that the partition is as fair as possible. In a fair partition, the difference between the assets of the children should be as small as possible.

Return the minimum possible difference between the asset values of the children after partition.

For Example : 
If N = 5 and Assets = { 10, 20, 30, 40, 50 } and tree is denoted as:


Then we have 4 choices of deletion:
Edge 0-1 is deleted: now, the one of the tree contains node-1 and node-3, and the other contains node-0, node-2 and node-3, subtree difference is = 90 - 60 = 30
Edge 1-3 is deleted: subtree difference is = 110 - 40 = 70
Edge 0-2 is deleted: subtree difference is = 80 - 70 = 10
Edge 2-4 is deleted: subtree difference is = 100 - 50 = 50


Clearly removing the edge between node-0 and node-2 leads to the most optimal partition where the difference is equal to 10. Hence we return the value 10.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the number of assets.

The next line contains N integers, where Assets[i] denotes the asset-value of the ith asset.

The next N-1 lines each contain two integers ‘U’ and ‘V’ denoting that there is an edge between node-U and node-V.
Output Format : 
For each test case, print the lowest possible difference between assets after splitting.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
2 ≤ N ≤ 200
0 ≤ Assets[i] ≤ 10^6
0 ≤ U, V ≤ N-1

Time limit: 1 sec
Sample Input 1 :
2
5
10 20 30 40 50
0 1
2 0 
1 3
4 2
2
10 10
0 1
Sample Output 1 :
10
0
Explanation For Sample Input 1 :
For test case 1 : 
We will return 10 because:
Edge 0-1 is deleted: subtree difference is = 90 - 60 = 30
Edge 1-3 is deleted: subtree difference is = 110 - 40 = 70
Edge 0-2 is deleted: subtree difference is = 80 - 70 = 10
Edge 2-4 is deleted: subtree difference is = 100 - 50 = 50


For test case 2 : 
We will return 0 because:
If the only edge, that is the edge between node-0 and node-1 is deleted, both the children get assets of the same worth.
Sample Input 2 :
2
2
50 50
1 0
2
0 100
0 1
Sample Output 2 :
0
100
Hint

Try removing edges one by one to find the optimal answer.

Approaches (2)
Brute Force

Try to remove the edges one by one to find the optimal partition.

 

The steps are as follows :

  • Initialize “total” equal to 0 to store the total sum of all the assets, calculate “total” equal to the sum of all the values in array ‘Assets’.
  • Initialize “ans” equal to INT_MAX to store the minimum possible difference.
  • Run a for loop for variable “remove” from 0 to N-1, and run an inner loop for variable “i” from 0 to N-1, Now build an adjacency list each time and don’t include the removeth node in it. Call DFS function, to sum up the values for one of the partitions, the sum will denote the asset value that child-1 will get, update “ans” if needed.
  • Finally, return the value of “ans”.
Time Complexity

O( N ^ 2 ), where N denotes the number of assets

 

We remove the edges one by one, and each time calculate the sum of one of the partition trees formed. Consider a bamboo tree (tree in form of a straight-chain), we will be applying operations of the order of ~N each time to calculate the sum of one of the partitions for each edge removal. 

Hence the time complexity is O( N^2 ).

Space Complexity

O( N ^ 2 ), where N denotes the number of assets

 

We remove edges one by one, and each time create an adjacency list of order ~N to apply DFS.

Hence the space complexity is O( N^2 ).

Code Solution
(100% EXP penalty)
Perfect Partition
Full screen
Console