Problem A: Maximum Value Boundary Analysis

In this problem, we need to calculate the sum of counts $f(k)$ for pairs $(i, j)$ that satisfy specific boundary conditions related to two arrays $A$ and $B$. Let $f(k)$ represent the number of valid pairs where the second index $j$ equals $k$. We define $last\_k$ as the index where the maximum value of either array $A$ or $B$ transitions. The recurrence can be expressed as:

f[k] = f[last_k] + (B[k] >= A[k] ? (k - last_k) : 0)

To efficiently determine $last\_k$, we employ monotonic stacks to track indices where the current element is greater than the maximum of both arrays encountered so far in their respective ranges.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve_boundary_problem() {
    int n;
    if (!(cin >> n)) return;

    vector<ll> val_a(n + 1), val_b(n + 1), max_ref(n + 1);
    for (int i = 1; i <= n; ++i) cin >> val_a[i];
    for (int i = 1; i <= n; ++i) cin >> val_b[i];
    for (int i = 1; i <= n; ++i) max_ref[i] = max(val_a[i], val_b[i]);

    stack<int> s_a, s_b;
    vector<ll> dp_count(n + 1, 0);
    ll total_ans = 0;

    for (int i = 1; i <= n; ++i) {
        while (!s_a.empty() && val_a[i] > max_ref[s_a.top()]) s_a.pop();
        while (!s_b.empty() && val_b[i] > max_ref[s_b.top()]) s_b.pop();

        int boundary;
        if (val_b[i] >= val_a[i]) {
            boundary = s_b.empty() ? 0 : s_b.top();
            dp_count[i] = dp_count[boundary] + (i - boundary);
        } else {
            boundary = s_a.empty() ? 0 : s_a.top();
            dp_count[i] = dp_count[boundary];
        }

        total_ans += dp_count[i];
        s_a.push(i);
        s_b.push(i);
    }
    cout << total_ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve_boundary_problem();
    return 0;
}

Problem B: Divisibility Pair Counting

This problem asks us to find pairs of indices such that the sum of two integer quotients equals a target value $T$. For constraints where $N$ is small, we can precalculate all possible values of $A[i] / A[j]$ and store their frequencies in a hash map. Then, for every unique quotient $q$ in the map, we check if $T - q$ also exists in the map and multiply their frequencies to update our modular result.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

void compute_quotient_pairs() {
    int n, target;
    long long mod_val;
    cin >> n >> target >> mod_val;

    vector<int> elements(n);
    for (int i = 0; i < n; ++i) cin >> elements[i];

    map<int, long long> freq_map;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            freq_map[elements[i] / elements[j]]++;
        }
    }

    long long total_count = 0;
    for (auto const& [quotient, count] : freq_map) {
        int complement = target - quotient;
        if (freq_map.count(complement)) {
            long long contribution = (count % mod_val) * (freq_map[complement] % mod_val);
            total_count = (total_count + contribution) % mod_val;
        }
    }
    cout << total_count << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    compute_quotient_pairs();
    return 0;
}

Problem C: Matrix Construction via GCD

The objective is to construct an $N \times M$ matrix where the product of the $i$-th row equals $A[i]$ and the product of the $j$-th column equals $B[j]$. A greedy approach using the Greatest Common Divisor (GCD) works well here. For each cell $(i, j)$, we asign the value $GCD(A[i], B[j])$. After assignment, we update $A[i]$ and $B[j]$ by dividing them by the assigned value. Finally, we must verify if the cumulative products of the rows and columns in our constructed matrix match the original inputs.

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

typedef long long ll;

ll get_gcd(ll x, ll y) {
    return y == 0 ? x : get_gcd(y, x % y);
}

void solve_matrix_construction() {
    int rows, cols;
    if (!(cin >> rows >> cols)) return;

    vector<ll> row_req(rows), col_req(cols);
    vector<ll> row_orig(rows), col_orig(cols);

    for (int i = 0; i < rows; ++i) {
        cin >> row_req[i];
        row_orig[i] = row_req[i];
    }
    for (int j = 0; j < cols; ++j) {
        cin >> col_req[j];
        col_orig[j] = col_req[j];
    }

    vector<vector<ll>> res_mat(rows, vector<ll>(cols));

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            ll common = get_gcd(row_req[i], col_req[j]);
            res_mat[i][j] = common;
            row_req[i] /= common;
            col_req[j] /= common;
        }
    }

    // Validation
    for (int i = 0; i < rows; ++i) {
        ll p = 1;
        for (int j = 0; j < cols; ++j) p *= res_mat[i][j];
        if (p != row_orig[i]) {
            cout << -1 << endl;
            return;
        }
    }
    for (int j = 0; j < cols; ++j) {
        ll p = 1;
        for (int i = 0; i < rows; ++i) p *= res_mat[i][j];
        if (p != col_orig[j]) {
            cout << -1 << endl;
            return;
        }
    }

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cout << res_mat[i][j] << (j == cols - 1 ? "" : " ");
        }
        cout << "\n";
    }
}

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