Resource Redistribution with Asymmetric Operations

Given a sequence (a) of length (n) and two positive integers (x, y) where (y \le x). You may repeatedly pick two elements and transfer resources: subtract (x) from one and add (y) to the other, provided the first remains non‑negative. Determine the maximum possible value of any element after optimal operations.

A greedy viewpoint helps: it is best to concentrate as much as possible into one target index. For any other element (a_i), keep extracting (x) from it until the remainder is smaller than (x). All the extracted units become (y) increments on the chosen element. Because (k \cdot y + d < (k+1) \cdot x) for (d < x), it is never beneficial to keep some increments on a helper element rather than transferring them. Therefore, for each candidate target (i), compute the total possible (y) contributions from the rest and add its own value. Return the maximum across candidates.

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

void process() {
    long long n, x, y;
    cin >> n >> x >> y;
    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];

    long long total_y = 0;
    for (auto v : arr) total_y += (v / x) * y;
    long long best = 0;
    for (auto v : arr) {
        long long cur = total_y - (v / x) * y + v;
        best = max(best, cur);
    }
    cout << best << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc;
    cin >> tc;
    while (tc--) process();
}

Minimal Repeating Patttern from Multiple Strings

We are given (k) strings, each of length (n), and we can form a new string (s) by picking, independently at each position, a character from any of the (k) strings at that position. The "information measure" of (s) is the length of its smallest periodic substring that repeats to form (s). The goal is to construct an (s) with the smallest possible measure.

The period (t) must be a divisor of (n). Iterate over divisors in increasing order. For a candidate divisor (d), the string consists of (d) blocks of length (n/d). Positions that are congruent modulo (d) must hold the same character. For each residue class, check whether there exists a character common to all the required positions across the (k) options. If yes, fill that character; otherwise, the period (d) is invalid. The first valid divisor yields the minimal measure.

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

void process() {
    int n, k;
    cin >> n >> k;
    vector<string> strs(k);
    for (int i = 0; i < k; ++i) {
        cin >> strs[i];
        strs[i] = "#" + strs[i];
    }

    vector<int> divs;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i != n / i) divs.push_back(n / i);
        }
    }
    sort(divs.begin(), divs.end());

    int chosen = 0;
    string pattern(n + 1, '#');
    for (int d : divs) {
        if (chosen) break;
        int block = n / d;
        bool ok = true;
        for (int r = 1; r <= d; ++r) {
            unordered_set<char> current, next;
            for (int j = 1; j <= block; ++j) {
                int pos = (j - 1) * d + r;
                for (int t = 0; t < k; ++t) {
                    char ch = strs[t][pos];
                    if (j == 1) {
                        next.insert(ch);
                    }
                    if (current.count(ch)) next.insert(ch);
                }
                swap(current, next);
                next.clear();
            }
            if (current.empty()) {
                ok = false;
                break;
            }
            pattern[r] = *current.begin();
        }
        if (ok) chosen = d;
    }

    for (int i = 0; i < n / chosen; ++i)
        for (int j = 1; j <= chosen; ++j)
            cout << pattern[j];
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc;
    cin >> tc;
    while (tc--) process();
}

Grid Partition with Balanced Ones

An (n \times m) binary matrix is given. Starting at ((1,1)), move only right or down to ((n,m)), there by splitting the matrix into two regions. Count ones in each region; maximize their product. Output the maximum product and the sequence of moves.

The key observation: for any target number of ones in the first region, there exists a cut achieving that split. The best product is obtained by dividing the total ones as evenly as possible. To construct the path, maintain a running count of ones transferred to the first region. At ((i,j)), moving down adds the ones in row (i+1) from column (j+1) to (m). If this does not exceed the target, go down; otherwise go right. Boundary cases follow the same logic.

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

void process() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n + 2, vector<int>(m + 2)), row(n + 2, vector<int>(m + 2)), col(n + 2, vector<int>(m + 2));
    int total = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
            if (grid[i][j]) {
                total++;
                row[i][j]++;
                col[i][j]++;
            }
        }

    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= m; ++j)
            row[i][j] += row[i][j - 1];
    for (int j = 1; j <= m; ++j)
        for (int i = 2; i <= n; ++i)
            col[i][j] += col[i - 1][j];

    int target = total / 2;
    int cur = 0, x = 1, y = 1;
    string path;
    while (x != n || y != m) {
        if (x == n) {
            path += 'R';
            ++y;
        } else if (y == m) {
            path += 'D';
            ++x;
        } else {
            int down_add = row[x + 1][m] - row[x + 1][y];
            if (cur + down_add <= target) {
                path += 'D';
                ++x;
                cur += down_add;
            } else {
                path += 'R';
                ++y;
            }
        }
    }
    int others = total - target;
    cout << target * others << '\n' << path << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc;
    cin >> tc;
    while (tc--) process();
}

Minimizing the Maximum Path Sum under a Single Sign Flip

An (n \times m) grid contains integers (positive, negative, or zero). Starting from ((1,1)) and moving right or down to ((n,m)), the sum of visited cells is (s). The natural aim is to maximize (s). However, we must first flip the sign of exactly one cell (turn (a_{i,j}) in to (-a_{i,j}); it is guaranteed some positive cell exists). After the flip, we are forced to follow the path that gives the maximal sum. We want to choose the flipped cell so that the resulting maximal sum is as small as possible. Output that minimal value.

Compute the standard DP from start to each cell ((dp_s)) and from end backwards ((dp_t), allowing only left and up moves). For a cell ((i,j)) there are two scenarios:

• The optimal path uses ((i,j)): the best sum becomes (\max(dp_s[i-1][j], dp_s[i][j-1]) - a_{i,j} + \max(dp_t[i+1][j], dp_t[i][j+1])).
• The optimal path avoids ((i,j)): it must cross from a blue cell (reachable from start) to a yellow cell (reaching the end) without stepping on ((i,j)). Precompute helpers (dp_r[i][j] = dp_s[i][j] + dp_t[i+1][j]) (down step) and (dp_c[i][j] = dp_s[i][j] + dp_t[i][j+1]) (right step). Using suffix maxima over these arrays gives the best avoidant path efficiently.

Finally, for each cell compute the maximum sum attainable after flipping that cell, and take the minimum across all cells.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = -1e18;

void process() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> val(n + 2, vector<ll>(m + 2, 0));
    vector<vector<ll>> dp_s(n + 2, vector<ll>(m + 2, NEG_INF));
    vector<vector<ll>> dp_t(n + 2, vector<ll>(m + 2, NEG_INF));
    vector<vector<ll>> dr(n + 2, vector<ll>(m + 2, NEG_INF));
    vector<vector<ll>> dc(n + 2, vector<ll>(m + 2, NEG_INF));

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> val[i][j];

    dp_s[0][1] = dp_s[1][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dp_s[i][j] = max(dp_s[i - 1][j], dp_s[i][j - 1]) + val[i][j];

    dp_t[n][m + 1] = dp_t[n + 1][m] = 0;
    for (int i = n; i >= 1; --i)
        for (int j = m; j >= 1; --j)
            dp_t[i][j] = max(dp_t[i + 1][j], dp_t[i][j + 1]) + val[i][j];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            dr[i][j] = dp_s[i][j] + dp_t[i + 1][j];
            dc[i][j] = dp_s[i][j] + dp_t[i][j + 1];
        }
    for (int i = 1; i <= n; ++i)
        for (int j = m - 1; j >= 1; --j)
            dr[i][j] = max(dr[i][j], dr[i][j + 1]);
    for (int j = 1; j <= m; ++j)
        for (int i = n - 1; i >= 1; --i)
            dc[i][j] = max(dc[i][j], dc[i + 1][j]);

    ll answer = 9e18;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            ll through = max(dp_s[i - 1][j], dp_s[i][j - 1])
                        - val[i][j]
                        + max(dp_t[i + 1][j], dp_t[i][j + 1]);
            ll avoid = max(dr[i - 1][j + 1], dc[i + 1][j - 1]);
            answer = min(answer, max(through, avoid));
        }
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc;
    cin >> tc;
    while (tc--) process();
}