Sunday, July 31, 2016

TCS Code Vita Season-5 Round-1 set-1 Program-2

Problem : Min Product Array
The task is to find the minimum sum of Products of two arrays of the same size, given that k modifications are allowed on the first array. In each modification, one array element of the first array can either be increased or decreased by 2. 

Note- the product sum is Summation (A[i]*B[i]) for all i from 1 to n where n is the size of both arrays 
Input Format: 
1.    First line of the input contains n and k delimited by whitespace
2.    Second line contains the Array A (modifiable array) with its values delimited by spaces
3.    Third line contains the Array B (non-modifiable array) with its values delimited by spaces


Output Format: 

Output the minimum sum of products of the two arrays
 
Constraints:
1.    1 ≤ N ≤ 10^5
2.    0 ≤ |A[i]|, |B[i]| ≤ 10^5
3.    0 ≤ K ≤ 10^9



Sample Input and Output
SNo.
Input
Output
1

3 5
1 2 -3
-2 3 -5

-31
2

5 3
2 3 4 5 4
3 4 2 3 2

25


Explanation for sample 1: 

Here total numbers are 3 and total modifications allowed are 5. So we modified A[2], which is -3 and increased it by 10 (as 5 modifications are allowed). Now final sum will be
 
(1 * -2) + (2 * 3) + (7 * -5)
 
-2 + 6 - 35
 
-31
 

-31 is our final answer.
 

Explanation for sample 2:
 

Here total numbers are 5 and total modifications allowed are 3. So we modified A[1], which is 3 and decreased it by 6 (as 3 modifications are allowed).
 
Now final sum will be
 
(2 * 3) + (-3 * 4) + (4 * 2) + (5 * 3) + (4 * 2)
 
6 - 12 + 8 + 15 + 8
 
25
 

25 is our final answer.
 

Contact Form

Name

Email *

Message *