2218BUnreviewed800GPT-5.5 (xhigh)

The 67th 6-7 Integer Problem

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

You are not choosing many complicated things. Since exactly $6$ numbers are negated, exactly one number keeps its original sign.

Try fixing the one number that stays unchanged. If that number is $a_k$ , every other $a_i$ contributes $-a_i$ .

S=\sum_{i=1}^{7} a_i.

a_k-(S-a_k)=2a_k-S.

2\max(a_i)-\sum_{i=1}^{7}a_i.

Editorial

Full explanation

Open this when you want the whole argument, complexity included.

Key Observation

Negating $6$ out of $7$ integers means exactly one integer is not negated.

Suppose we leave $a_k$ unchanged. Let

S=\sum_{i=1}^{7} a_i.

Then the resulting sum is

a_k-\sum_{i\ne k}a_i.

But

\sum_{i\ne k}a_i=S-a_k,

so the result becomes

a_k-(S-a_k)=2a_k-S.

Maximizing

The value $S$ is fixed for the test case, so maximizing

2a_k-S

is the same as maximizing $a_k$ .

So the optimal move is brutally simple: keep the largest number unchanged, and negate the other six.

Therefore the answer is

2\max(a_i)-\sum_{i=1}^{7}a_i.

This also handles negative numbers correctly. If all numbers are negative, the "largest" one is the least negative, which is exactly the one we should leave alone.

Complexity

For each test case, we scan $7$ numbers.

O(7)=O(1)

per test case, and

O(t)

over all test cases. Memory usage is

O(1).

Solution

Generated C++

This is the full implementation the model produced for the problem.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int sum = 0;
        int mx = -1000000000;

        for (int i = 0; i < 7; i++) {
            int x;
            cin >> x;
            sum += x;
            mx = max(mx, x);
        }

        cout << 2 * mx - sum << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int t;
    cin >> t;
    while (t--) {
        int sum = 0;
        int mx = -1000000000;

        for (int i = 0; i < 7; i++) {
            int x;
            cin >> x;
            sum += x;
            mx = max(mx, x);
        }

        cout << 2 * mx - sum << '\n';
    }

    return 0;
}

Report an issue

Something wrong with the hints, editorial, or solution? Let us know.

Review this problem

Update the review status for this problem