Official

A - God Sequence Editorial by evima

If \(A \geq B\), we can make a god sequence as follows:

  • let \(E_1 = 1, E_2 = 2, \cdots, E_A = A\);
  • let \(E_{A + 1} = -1, E_{A + 2} = -2, \cdots, E_{A + B - 1} = -(B - 1)\);
  • then, let \(E_{A + B} = - \sum_{i=B}^{A} E_i = -\sum_{i = B}^{A} i = -\left(B + (B + 1) + ... + (A - 1) + A\right) \leq -B\).

if \(A < B\), we can make a god sequence as follows:

  • let \(E_1 = 1, E_2 = 2, \cdots, E_{A - 1} = (A - 1)\);
  • let \(E_{A + 1} = -1, E_{A + 2} = -2, \cdots, E_{A + B - 1} = -(B - 1)\);
  • then, set \(E_{A}\) so that the sum of the sequence is \(0\) (\(E_{A}\) will be at least \(A\)).

Sample implementation in C++: (Link)

#include <iostream>
using namespace std;

int A, B, E[1 << 18];

int main() {
    // Input
    cin >> A >> B;

    // Make "God Array"
    if (A >= B) {
        for (int i = 0; i < A; i++) E[i] = i + 1;
        for (int i = A; i < A + B - 1; i++) E[i] = -(i - A + 1);
        for (int i = 0; i < A + B - 1; i++) E[A + B - 1] -= E[i];
    }
    else {
        for (int i = 0; i < A - 1; i++) E[i] = i + 1;
        for (int i = A; i < A + B; i++) E[i] = -(i - A + 1);
        for (int i = 0; i < A + B; i++) { if (i != A - 1) E[A - 1] -= E[i]; }
    }

    // Output
    for (int i = 0; i < A + B; i++) {
        if (i) cout << " ";
        cout << E[i];
    }
    cout << endl;
    return 0;
}

Sample implementations in other languages:

posted:
last update: