Codevita Previous Questions | Min Product Array

Min Product Array

LEVEL:Beginner

Description

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
Constraints:
1 ? N ? 10^5
0 ? |A[i]|, |B[i]| ? 10^5
0 ? K ? 10^9

Output Format

Output the minimum sum of products of the two arrays

Example 1:

Input

3 5
1 2 -3
-2 3 -5

Output

-31

Example 2:

Input

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

Output

Example 3:

Input

3 5
1 3 3
-8 3 -5

Output

-94

Approach

Since we need to minimize the sum of products, we find the maximum product and reduce it. By taking some examples, we can observe that making 2*k changes to only one element is enough to get the minimum sum. Based on this observation, we consider every element as the element on which we apply all k operations and keep track of the element that reduces the result to minimum.

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Beginner

Min Product Array

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Codevita Previous Questions

Beginner