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:
First line of the input contains n and k delimited by whitespace. Second line contains the Array A (modifiable array) with its values delimited by spaces. 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 ≤ N ≤ 10^5
0 ≤ |A[i]|, |B[i]| ≤ 10^5
0 ≤ K ≤ 10^9
Example 1
Input:
3 5
1 2 -3
-2 3 -5
Output:
-31
Explanation:
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.
Example 2
Input:
5 3
2 3 4 5 4
3 4 2 3 2
Output:
25
Explanation:
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.
Solution: In C
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int minproduct(int a[], int b[], int n, int k)
{
int diff = 0, res = 0;
int temp;
for (int i = 0; i < n; i++) {
int pro = a[i] * b[i];
res = res + pro;
if (pro < 0 && b[i] < 0)
temp = (a[i] + 2 * k) * b[i];
else if (pro < 0 && a[i] < 0)
temp = (a[i] - 2 * k) * b[i];
else if (pro > 0 && a[i] < 0)
temp = (a[i] + 2 * k) * b[i];
else if (pro > 0 && a[i] > 0)
temp = (a[i] - 2 * k) * b[i];
int d = abs(pro - temp);
if (d > diff)
diff = d;
}
return res - diff;
}
int main()
{
int n,k,a[100],b[100];
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);
for(int i = 0; i < n; i++)
scanf("%d",&b[i]);
printf("%d",minproduct(a, b, n, k));
return 0;
}
Solution: In Java
import java.util.Scanner;
import java.math.*;
class MinProduct {
static int minproduct(int a[], int b[], int n, int k)
{
int diff = 0, res = 0;
int temp = 0;
for (int i = 0; i < n; i++) {
int pro = a[i] * b[i];
res = res + pro;
if (pro < 0 && b[i] < 0)
temp = (a[i] + 2 * k) * b[i];
else if (pro < 0 && a[i] < 0)
temp = (a[i] - 2 * k) * b[i];
else if (pro > 0 && a[i] < 0)
temp = (a[i] + 2 * k) * b[i];
else if (pro > 0 && a[i] > 0)
temp = (a[i] - 2 * k) * b[i];
int d = Math.abs(pro - temp);
if (d > diff)
diff = d;
}
return res - diff;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int a[] = new int[n], b[] = new int[n];
for(int i = 0; i < n ; i++)
a[i] = sc.nextInt();
for(int i = 0; i < n ; i++)
b[i] = sc.nextInt();
System.out.println(minproduct(a, b, n, k));
}
}
Solution: In Python 3
def minproduct(a,b,n,k):
diff = 0
res = 0
for i in range(n):
pro = a[i] * b[i]
res = res + pro
if (pro < 0 and b[i] < 0):
temp = (a[i] + 2 * k) * b[i]
elif (pro < 0 and a[i] < 0):
temp = (a[i] - 2 * k) * b[i]
elif (pro > 0 and a[i] < 0):
temp = (a[i] + 2 * k) * b[i]
elif (pro > 0 and a[i] > 0):
temp = (a[i] - 2 * k) * b[i]
d = abs(pro - temp)
if (d > diff):
diff = d
return res - diff
n,k = [int(x) for x in input().split()]
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(minproduct(a, b, n, k))
Also Checkout