Question: GOOGLE OA | SWE Internship 2023 | Cost of Groups | Queries and Arrays | 22nd July(SET-1)

Entering edit mode

Question 1

Cost of groups

You are given an undirected tree with I nodes. Each node of the tree is assigned a
value You are required to divide the nodes into as little groups as possible, such that
no two nodes in a group are adjacent to each other.
Consider a group G. Let us consider a pair(u, w) from the group. The value of the
pair (u, v) is given as |Au - Av| where A, is value assigned to node x
(1 ≤ x ≤ N). The cost of group G is defined as the maximum sum that you can get
by pairing up the nodes of G. Each node can be used only once to make a pair. It is
possible for some nodes in G to be unpaired.
Find the sum of costs of all possible groups that can be made for the given tree.
Input format
• The first line has an integer I denoting the number of test cases.
• The first line of each test case contains an integer N denoting the number of
nodes.
• The second line of each test case contains N space-separated integers
denoting the value assigned to the nodes A1, A2, ..., An
• Next N - 1 lines of each test case contain two integers U and V denoting an
edge between the nodes U and V
Output format
For each test case, print an integer denoting the sum in a new line.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 10⁵
1 ≤ A[i] ≤10⁹
1≤ U,V ≤ N

Sample Input 
1
5
12 17 14 13 16
1 2 
1 3
1 5
2 4

Sample Output 
4

Explanation
G1: Nodes 1 and 4 can be grouped together. The cost of the group G'1 turns out to be |12 - 13| = 1, by pairing nodes 1 and 4.G2: Nodes 2, 3, and 5 can be grouped together.Pairing Node 2 and 3, we get value as |17 - 14| = 3. Node 5 is left unpaired.Pairing Node 3 and 5, we get value as |14 - 16 = 2. Node 2 Is left unpaired.Pairing Node 2 and 5, we get value as |17 - 16] = 1. Node 3 is left unpaired.The cost of the group G2 turns out to be 3.
The final answer is cost(G1) + cost(G2) = 4

Queries and Arrays

You are given three arrays A. B, and C of length N.For each index i, A[i] is greater than or equal to B[i].You can perform the given operation on this array A as many
times as you want. In each operation:

• Pick any two indices i and j and add 1 to A[i] and subtract 1
from A[j]. This operation can only be done only if A[j] is
currently greater than B[j]. The cost of this single operation
is C[j].
Note: 1 based indexing is used
Task
If you perform the operations optimally, determine the maximum possible minimum number present in the final array.A and also find the minimum cost required to make this possible.As this cost can be very large, you are supposed to find it modulo 10⁹+ 7.

Example
Assumptions
• N= 5
• A = [1,2,2,3,3,1]
• B = [1,2,1,2,1]
• C = [1,2,1,4,3]
Approach
• The only optimal approach is to choose index as i and index 5 as J and perform the operation on them.
•The array A after that will be [2, 2, 2, 3, 2].
• The maximum possible minimum number in array A is 2. The minimum cost required to do so is C[5] = 3.
• So, the required answer is [2,3]

Function description
Complete the solve function provided in the editor. The function takes the following 4 parameters and returns the required answer:
• N: Represents an integer denoting the size of the arrays A,B and C
• A Represents the array of integers A
• B: Represents the array of integers B
• C: Represents the array of integers C
Input format
Note: This is the input format that you must use to provide custom
input (available above the Compile and Test button).

• The first line contains an integer T denoting the number of test cases.

• The first line contains a single integer ~ denoting the size of the array
• The second line contains N space: separated integers denoting the elements
of the array A
• The third line contains N space-separated integers denoting the elements of the
array B.
• The fourth line contains N space- separated integers denoting the elements
of the array C.
Output Format
For each test case in a new line, print the maximum value of the minimum element present in array A and the minimum cost to make it possible modulo 10⁹+7,
in a space-separated format.

Constraints

1<=T <=10⁵
1<=N < =10⁵

1<=A[i],B[i],C[i]<=10⁹
Sum of N over all testcases < =10⁵

Sample Input 
1
4
1 99 2 9
1 97 2 98
1 5 2 2 

Sample output
3 12

Explanation
The first line contains the number of test cases. T = 1
For test case 1
Given

•N=4
• A = [1, 99, 2, 99]
• B = [1, 97, 2, 98]
• C = [1, 5, 2, 2]
Approach
• Choose i = 1,j = 2, two times and subtract 2 from 2nd Index element and add 2 in Ist index with cost 5'2 =10
• Choose i = 3, J = 4 subtract 1 from 4th index element and add fin 2nd index element with cost 2.
•After thet, the final array A will be [3, 97 3, 98].You cannot increase the value of the minimum element present in array A any more.The total cost is 12 and the maximum possible minimum value is 3 Hence, the final answer is equal to [3,12].

Sample Input 
10 
10
59 95 8 14 35 13 63 70 15 17
48 47 7 7 5 9 62 43 12 9
61 66 68 89 3 57 71 4 27 9
10 
61 61 72 25 45 77 96 100 69 8
55 53 21 24 1 65 79 93 31 3
91 18 40 16 49 18 78 62 52 77 
10
61 99 88 3 76 89 20 97 59 50
40 37 82 3 7 13 3 60 17 10
42 15 13 8 51 14 17 4 41 67
10
48 65 39 29 89 18 10 25 89 21

Sample Output
31 1827
53 3894
62 1763
37 4812
58 6384
49 3507
37 4695
61 3485
37 6370
57 4420