You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXISUM - Editorial

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

        // try decrementing k times
        a[i] -= k;
        res = max(res, interaction());
        a[i] += k; // cancel
    }
    return res;
}
int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        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[i] += k
        yield interaction(a,b)
        a[i] -= k # cancel

        # try decrementing k times
        a[i] -= k
        yield interaction(a,b)
        a[i] += 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[i]

        # try decrementing k times
        yield interaction - k*b[i]

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

This question is marked "community wiki".

asked 13 Mar '16, 14:24

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 12 Mar '17, 20:10

admin's gravatar image

0★admin ♦♦
19.8k350498541


Simple solution :-) link text

link

answered 15 Mar '16, 15:40

s_verma's gravatar image

1★s_verma
562
accept rate: 18%

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

link

answered 15 Mar '16, 18:36

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 0%

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 ??

link

answered 15 Mar '16, 20:57

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

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

link

answered 16 Mar '16, 00:06

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

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

link

answered 16 Mar '16, 01:03

restless's gravatar image

2★restless
1
accept rate: 0%

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.

link

answered 16 Mar '16, 11:28

manishvirodhia's gravatar image

2★manishvirodhia
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,191
×192

question asked: 13 Mar '16, 14:24

question was seen: 4,728 times

last updated: 12 Mar '17, 20:10