PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY:Simple PREREQUISITES:Greedy algorithm PROBLEM:There are two arrays, $A$ and $B$, each of size $N$. You can make the following operation at most $K$ times:
What is the maximum possible value of $\sum_{i=1}^N A_i B_i$? (We'll call this the interaction of $A$ and $B$.) QUICK EXPLANATION:The answer is $\left(\sum_{i=1}^N A_i B_i\right) + K\cdot \max_i B_i$. ($\max_i B_i$ is the maximum increase we can get with one operation, which we will perform $K$ times.) EXPLANATION:We must find ways to reduce the number of cases we need to check. (Otherwise, the number of cases becomes too many, even for the first subtask.) First, let us understand the effect of one operation to the interaction $\sum_{i=1}^N A_i B_i$. Suppose we increase $A_j$ by $1$. Then the summands of $\sum_{i=1}^N A_i B_i$ will remain the same except for the $j$th summand, which will become $(A_j + 1)B_j$ instead of $A_jB_j$. In other words, the $j$th summand will increase by $B_j$ (because $(A_j + 1)B_j = A_jB_j + B_j$). Thus, the effect of adding $1$ to $A_j$ is to increase the interaction by $B_j$, regardless of the value of $A_j$. Similarly, the effect of subtracting $1$ to $A_j$ is to decrease the interaction by $B_j$, regardless of the value of $A_j$. Now, remember that we want to maximize the interaction. This means:
In other words, we can (and must) be greedy with our choice of operations. This greatly reduces the number of cases we need to check! Specifically, since there are $2N$ distinct operations ($N$ possible indices, and choosing whether to increment or decrement), it means we only need to check $2N$ cases. Here are sample implementations. C++:
Python:
In both codes, Both codes simply try out all $2N$ operations. Since computing the interaction between the two arrays takes $O(N)$ time, the overall complexity is $2N\cdot O(N) = O(N^2)$. This passes the first two subtasks, but is too slow for the final subtask. Actually, with a simple trick, this approach can be optimized to pass the final subtask. Suppose we know the interaction between the two arrays $\sum_i A_iB_i$ before some operation. After performing an operation, it's very easy to update this interaction! Specifically:
Similarly, incrementing $A_j$ a total of $K$ times increases the interaction by $K\cdot B_j$, and decrementing it $K$ times decreases the interaction by $K\cdot B_j$. This update can be done very quickly. More importantly, it doesn't require us to perform another $O(N)$ loop to compute the new interaction; the update runs in $O(1)$ time. Thus, we can iterate through everything in $2N\cdot O(1) = O(N)$ time instead, which passes the time limit for the final subtask! The following is a Python implementation:
Finally, we can simplify this even further. Instead of checking all $2N$ operations, we can simply find the best operation and perform it $K$ times. Finding the best operation is easy: Just find the maximum value among $B_1, B_1, B_2, B_2, B_3, B_3, \ldots, B_N, B_N$. (This maximum value is equivalent to $\max_i B_i$.) This allows for a much shorter code such as the following:
Tip: If you've been getting wrong answers for some reason, you might be getting arithmetic overflow, which means your variables are too small to contain the intermediate values or the result. This could happen certainly in the final subtask because the answer could reach values greater than $10^{14}$, which is too large for a 32bit variable (such as C++'s Time Complexity:$O(N)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Mar '16, 14:24

Hello,my solution has failed for large inputs,it is giving only WA ,no info at all,got 60 points https://www.codechef.com/viewplaintext/9622503 please review this Regards Samuel answered 15 Mar '16, 18:36

What I did is that I first calculated the product of input used sort(b,b+n) and found if the magnitude of b[0] was greater or lesser than magnitude of b[n1].If abs(b[0]) was greater I performed product=productb[0]k else I performed product=product+b[n1]k. I got AC but my question is whether this technique is efficient ?? answered 15 Mar '16, 20:57

Hi can any one please tell me where my solution is failing ,it's not working for large inputs and i have tried with long long int also but of no use answered 16 Mar '16, 00:06

Hello, I implemented the solution in PHP. Here are 2 of my implementations: https://www.codechef.com/viewsolution/9663823 https://www.codechef.com/viewsolution/9681748 The first one was during the contest, and the second one after reading the editorial. Both of them fail only one test case of Subtask 3. I'm suspecting that the implementation is correct, but the result overflows max integer limit for 32bits integers (used by php). Can anyone, please, point me if my supposition is correct or not? Thank you in advance, Nicu answered 16 Mar '16, 01:03

maximum interactions.Two ways either (add +K, or subtract K ) to each and every element or array A[]. Iterate through the array and remove the original (a[i]*b[i]) and ( add (a[i]k * b[i]) or (a[i]+k * b[i]). Till now you have all the maximum interactions of every element stored. Sort them & check the maximum out of them, will be your answer. Check my solution https://www.codechef.com/viewsolution/9656098 . Remove the comments in my code & run it in IDE. answered 16 Mar '16, 11:28
