MAXIINT - Editorial

editorial
,
1

PROBLEM LINK:

Contest

Author: Tejus Kaw
Tester: Rahul Sharma Tejus Kaw
Editorialist: Tejus Kaw

DIFFICULTY:

Easy

PREREQUISITES:

Math , Greedy Approach

PROBLEM:

Given two arrays A and B , you need to maximize the A[i]*B[i] such that i ranges from 1 to N. You can increase or decrease any element of A by one in one operation and you can do only K operations.

QUICK EXPLANATION:

Find the maximum element of B and use all K operations to increase that element in answer.

EXPLANATION:

You have to convert the form of the required answer in order to get closer to answer.
For Example : (3*x) + (6*y) + .. is equivalent to
x+x+x+y+y+y+y+y+y so we can say that the required answer is basically the sum of B[i] , A[i] number of times.
Now if all the elements of B[i] have been positive then we just need to simply choose the maximum element of array B and add K times that element to the required answer but since it can be negative too so we need to change approach.
since we know that multiplication of two numbers will not change even if we multiply both numbers with -1 because -1*-1=1.
So using this, we will try to make the element of B positive so that we can use our above approach.
so if element of B is negative at i index just multiply both A[i] and B[i] with -1.
then find the maximum element of B and simply add K*max_B to the required sum.:slight_smile:

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
int main() {
	int t;t=1;
	while(t--){
	    long long int n,k;std::cin >> n>>k;
	    long long int arr[n];
	    for(long long int i=0;i<n;i++){std::cin >> arr[i];}
	    long long int brr[n];
	    long long int max=INT_MIN;
	    long long int answer=0;
	    for(long long int i=0;i<n;i++){
	        std::cin >> brr[i];
	        if(brr[i]<0){
	            brr[i]*=-1;
	            arr[i]*=-1;
	        }
	        answer = answer + (arr[i]*brr[i]);
	        if(brr[i]>max){
	            max=brr[i];
	        }
	    }
	    long long int add = max*k;
	    answer += add ;
	    std::cout << answer << std::endl;
	}
	return 0;
}
Author Solution (in python) 
n , k = map(int, input().strip().split() )
arr = list(map(int,input().strip().split()))
brr = list(map(int,input().strip().split()))
answer = 0
maximum = -1
for i in range(n):
	if brr[i]<0 :
		brr[i] *= -1
		arr[i] *= -1
	answer += (arr[i]*brr[i])
	if brr[i]>maximum :
		maximum = brr[i]
 
add = maximum*k
answer += add
print(answer)
1 Like