CHECKADJSUM - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

For an array B of length N, define f(B) = \sum_{i=1}^{N-1} (B_i + B_{i+1}).

You’re given an array A and Q queries on it.
Each query gives you a value X. Find any rearrangement of A such that f(A) = X, or report that no such rearrangement exists.

EXPLANATION:

It is recommended that you first solve MAXADJSUM (or at least read its editorial, since this one will continue from there).

Recall that after a bit of simplification, we have

f(A) = S - A_1 - A_N

where S denotes twice the sum of A.

Now, suppose we want f(A) = X.
This means S - A_1 - A_N = X should hold; or A_1 + A_N = S - X.
In other words, we want two different elements of A that add up to S-X.

If you’re able to find such a pair, place one of them at the front of the array, the other one at the back, and everything else inbetween (in any order).
The only thing left is to actually find such a pair.

The constraints are low enough that this can be done with a simple bruteforce algorithm!
That is, simple iterate across all pairs (i, j) (with 1 \leq i \lt j \leq N), and check if A_i + A_j = S-X. Stop once you have a valid pair.

This is \mathcal{O}(N^2) per query, which is fast enough since T, N, Q \leq 50.
Faster solutions exist, but are not necessary to get AC on this problem.

TIME COMPLEXITY:

\mathcal{O}(N^2 Q) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n, q; cin >> n >> q;

    vector <int> a(n);
    for (auto &x : a) cin >> x;

    int sum = accumulate(a.begin(), a.end(), 0);
    sum *= 2;
    while (q--){
        int x; cin >> x;
        x = sum - x;
        bool print = false;

        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                if ((a[i] + a[j]) == x && !print){
                    print = true;
                    cout << a[i] << " ";
                    for (int k = 0; k < n; k++) if (k != i && k != j) cout << a[k] << " ";
                    cout << a[j] << "\n";
                }
            }
        }
        if (!print) cout << -1 << "\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    S = 2*sum(a)
    for k in range(q):
        x = int(input())
        p, q = -1, -1
        for i in range(n):
            for j in range(i+1, n):
                if S - a[i] - a[j] == x:
                    p, q = i, j
        if p == -1:
            print(-1)
            continue
        ans = [a[p]] + a[:p] + a[p+1:q] + a[q+1:] + [a[q]]
        print(*ans)
1 Like
2

Faster solutions exist, but are not necessary to get AC on this problem. But Why?
And why Codechef is showing wrong answer on the testcase 1 2 3 3 6 8 9 10, which is supposed to be -1 3 6 -1, as given in the sample testcase also.

Here is my code:

#include <bits/stdc++.h>
using namespace std;
int main() {	
    int t;
    cin>>t;
    while(t--) {
        int n, q, x, l, r;
        cin>>n>>q;
        vector<int> v(n);
        for(int i = 0; i < n; i++)  cin>>v[i];
        long long total = 0, target;
        for(int i = 0; i < n; i++) total += v[i];      
        while(q--) {
            cin>>x;
            target = 2*total - x;
            l = 0, r = n-1;
            while(l < n && r >= 0 && l < r) {
                if(v[l] + v[r] > target) {
                    r--;
                } else if(v[l] + v[r] < target) {
                    l++;
                } else {
                    break;
                }
            }
            if(l >= r || r < 0 || l >= n) {
                cout<<-1<<endl;
            } else {
                cout<<v[l]<<" ";
                for(int i = 0; i < n; i++) {
                    if(i != l && i != r) {
                        cout<<v[i]<<" ";
                    }
                }
                cout<<v[r]<<endl;
            }
        }
    }
}
3

f(A) should be equal to 2*S - A1 - A2.
Or S should represent twice the sum of A

4

Ah right, thanks for pointing that typo out.
In the editorial for the first version I’ve defined S to be twice the sum of the array so I’ll continue that notation here too.

5

It’s a clever implementation, and certainly has a N*Q complexity.

It fails because it assumes the array is sorted, just like the ones in the sample testcase.
Just sort it before receiving the queries and will work.

6

Yes! I got it. Thank you.

7

but we are not trying to maximize here, isn’t it? so, why do we need to sort? [considering A1 and A2 represents minimum element and second minimum element]