Problem A Given three integers (x), (y), and (n), construct a sequence (a) of length (n) satisfying:

1. (a_1 = x), (a_n = y).
2. Sequence (a) is strictly increasing.
3. The differences (b_i = a_{i+1} - a_i) form a strictly decreasing sequence.

Start by defining the array with (a_1 = x) and (a_n = y). The key is to work backwards to assign differences (b_i). The optimal greedy approach sets (b_{n-1}=1), (b_{n-2}=2), ..., (b_{2}=n-2). This ensures the differences are strictly decreasing positive integers. Compute (a_i) for (2 \le i \le n-1) using (a_i = a_{i+1} - b_i). The sequence is valid if and only if (a_2 - a_1 \ge n-1); otherwise output -1.

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int x, y, n;
    cin >> x >> y >> n;
    vector<int> arr(n + 1);
    arr[1] = x;
    arr[n] = y;
    for (int i = n - 1, diff = 1; i >= 2; --i, ++diff) {
        arr[i] = arr[i + 1] - diff;
    }
    if (arr[2] - arr[1] >= n - 1) {
        for (int i = 1; i <= n; ++i) cout << arr[i] << " \n"[i == n];
    } else {
        cout << -1 << '\n';
    }
}

int main() {
    int cases;
    cin >> cases;
    while (cases--) solve();
    return 0;
}

---

Problem B Given a string (s) of length (n) and an integer (k) ( (k - 1 \le n) ), two operations are allowed:

1. Swap characters at positions (i) and (i + 2).
2. Reverse the substring from index (i) to (i + k - 1). Find the lexicographically smallest string obtainable after any number of operations.

Analysis of allowed operations:

• Operation 1 allows swapping characters at the same parity position (even indices with even, odd with odd). Therefore, characters at even and odd positions can be independently sorted.
• Operation 2, a reverse of length (k), changes parity interactions depending on (k).

Case breakdown:

• If (k) is odd: Parity remains fixed. The minimal string is formed by independently sorting characters at odd and even positions and merging them.
• If (k) is even and (k = n): The entire string can be reversed, swapping all odd and even positions. Two candidate strings exist: one from original parity sorting, one from reversed parity sorting. The lexicographically smaller is selected.
• If (k) is even and (k < n): Any character from an odd position can be exchanged with any from an even position. The minimal string is simply the full sorted string.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    string str(n, ' '), odd, even;
    for (int i = 0; i < n; ++i) {
        cin >> str[i];
        if (i % 2 == 0) odd.push_back(str[i]);
        else even.push_back(str[i]);
    }
    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());
    string result;
    if (k % 2 == 1) {
        for (int i = 0; i < even.size(); ++i) {
            result.push_back(odd[i]);
            result.push_back(even[i]);
        }
        if (odd.size() > even.size()) result.push_back(odd.back());
    } else if (k == n) {
        string cand1, cand2;
        for (int i = 0; i < even.size(); ++i) {
            cand1.push_back(odd[i]);
            cand1.push_back(even[i]);
        }
        if (odd.size() > even.size()) cand1.push_back(odd.back());
        reverse(str.begin(), str.end());
        odd.clear(); even.clear();
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) odd.push_back(str[i]);
            else even.push_back(str[i]);
        }
        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());
        for (int i = 0; i < even.size(); ++i) {
            cand2.push_back(odd[i]);
            cand2.push_back(even[i]);
        }
        if (odd.size() > even.size()) cand2.push_back(odd.back());
        result = min(cand1, cand2);
    } else {
        sort(str.begin(), str.end());
        result = str;
    }
    cout << result << '\n';
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

---

Problem C Given an integer (x), reduce it to 1 using operations: subtract a divisor of (x). Each divisor can be used at most twice.

The solution uses binary representation.

• Step 1: Repeatedly subtract the lowest set bit (value (x & -x)) from (x) until (x) becomes a power of two. Each bit weight is a distinct divisor, proving no divisor is used more than once.
  • Lemma: The lowest set bit (2^k) is a divisor of (x). Since (2^k | x) because all higher bits are multiples of (2^k).
• Step 2: For the power-of-two (x = 2^m), repeatedly subtract (2^{m-1}) (half of (x)), which is a divisor. This process also uses each divisor at most once.

Thus, no divisor is used more than twice in total.

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int x;
    cin >> x;
    vector<int> steps = {x};
    while (__builtin_popcount(x) > 1) {
        x -= (x & -x);
        steps.push_back(x);
    }
    while (x > 1) {
        x >>= 1;
        steps.push_back(x);
    }
    cout << steps.size() << '\n';
    for (int i = 0; i < steps.size(); ++i) {
        cout << steps[i] << " \n"[i + 1 == steps.size()];
    }
}

int main() {
    int tc; cin >> tc;
    while (tc--) solve();
    return 0;
}

---

Problem D Given an (n \times n) binary matrix, flipping a cell ((i, j)) toggles:

• The cell itself.
• Any cell ((x, y)) with (x > i) and (x - i \ge |y - j|). This forms a downward-pointing 90-degree cone. Find the minimum number of flips to achieve all zeros.

Properties of toggling:

• Each cell's state depends on its initial value and the cumulative parity of flips affecting it.
• The operation's effect is strictly downward, allowing a top-to-bottom greedy sweep. The optimal strategy flips any cell currently 1, as this greedily eliminates it without affecting previously processed rowss.

Implementation: Track cumulative effect using difference arrays for two diagonal directions. For each cell ((i, j)), maintain a 2D (tag) array representing pending toggles. When a cell is toggled (flipped), mark its effect on cells in the cone by updating tags for positions ((i+1, j-1)), ((i+1, j+1)), and ((i+2, j)). Propagate tags row by row to compute net toggle parity at each cell.

Complexity: (O(n^2)).

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n+2, vector<int>(n+2, 0)), tag(n+2, vector<int>(n+2, 0));
    for (int i = 1; i <= n; ++i) {
        string line;
        cin >> line;
        for (int j = 1; j <= n; ++j) {
            grid[i][j] = line[j-1] - '0';
        }
    }
    int flips = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // Apply pending toggles from above
            grid[i][j] ^= tag[i][j];
            // Flip if current value is 1
            if (grid[i][j]) {
                ++flips;
                tag[i][j] ^= 1;
                grid[i][j] ^= 1;
            }
            // Propagate tag downwards
            if (tag[i][j]) {
                if (i+1 <= n) {
                    grid[i+1][j] ^= 1;
                    if (j-1 >= 1) tag[i+1][j-1] ^= 1;
                    if (j+1 <= n) tag[i+1][j+1] ^= 1;
                }
                if (i+2 <= n && j-1 >= 1 && j+1 <= n) {
                    tag[i+2][j] ^= 1;
                }
            }
        }
    }
    cout << flips << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}