MAXISUM - Editorial

editorial
march16
simple

#1

PROBLEM LINK:

Contest
Practice

Author: Praveen Dhinwa
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

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:

  • In a single operation, you can increase or decrease any of the elements of A by 1.

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:

  • We should pick the operation which gives us the greatest increase in the interaction.
  • We must perform this best operation K times.

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++:

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long int
#define INF (1LL<<60) // some really large number
#define N 100111

ll a[N];
ll b[N];
int n;
ll k;
ll interaction() {
    ll res = 0;
    for (int i = 0; i < n; i++) res += a* * b*;
    return res;
}
ll max_interactions() {
    ll res = -INF;
    for (int i = 0; i < n; i++) {
        // try incrementing k times
        a* += k;
        res = max(res, interaction());
        a* -= k; // cancel

        // try decrementing k times
        a* -= k;
        res = max(res, interaction());
        a* += k; // cancel
    }
    return res;
}
int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a*;
        for (int i = 0; i < n; i++) cin >> b*;
        cout << max_interactions() << endl;
    }
}

Python:

def interaction(a,b):
    return sum(x*y for x,y in zip(a,b))

def interactions(k,a,b):
    for i in xrange(n):

        # try incrementing k times
        a* += k
        yield interaction(a,b)
        a* -= k # cancel

        # try decrementing k times
        a* -= k
        yield interaction(a,b)
        a* += k # cancel

for cas in xrange(input()):
    n, k = map(int, raw_input().strip().split())
    a = map(int, raw_input().strip().split())
    b = map(int, raw_input().strip().split())
    print max(interactions(k,a,b))

In both codes, interaction returns the interaction between the two arrays a and b.

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:

  • After incrementing some value, say A_j, the interaction simply increases by B_j.
  • After decrementing some value, say A_j, the interaction simply decreases by B_j.

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:

def interactions(k,a,b):
    interaction = sum(x*y for x,y in zip(a,b))
    for i in xrange(n):
        # try incrementing k times
        yield interaction + k*b*

        # try decrementing k times
        yield interaction - k*b*

for cas in xrange(input()):
    n, k = map(int, raw_input().strip().split())
    a = map(int, raw_input().strip().split())
    b = map(int, raw_input().strip().split())
    print max(interactions(k,a,b))

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:

for cas in xrange(input()):
    n, k = map(int, raw_input().split())
    a = map(int, raw_input().split())
    b = map(int, raw_input().split())
    print sum(x*y for x,y in zip(a,b)) + k*max(map(abs, b))

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 32-bit variable (such as C++'s int) to hold. To fix this, use a 64-bit variable for the final result (long long int in C++, long in Java, etc.) AND for K and the arrays A and B (because you’ll be multiplying these values).

Time Complexity:

O(N)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester


#2

Simple solution :slight_smile: link text


#3

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


#4

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[n-1].If abs(b[0]) was greater I performed product=product-b[0]*k else I performed product=product+b[n-1]*k. I got AC but my question is whether this technique is efficient ??


#5

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


#6

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


#7

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**b*) and ( add (a*-k * b*) or (a*+k * b*).
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.