Problem 1: Equalizing Elements via Modulo

Problem Statement

Given an array of integers, determine if it is possible to make all elements equal by repeatedly applying a modulo operation with an integer $x \ge 2$. In each step, every element $a_i$ is replaced by $a_i \bmod x$.

Analysis

The core constraint lies in the behavior of small numbers under modulo operations. Specifically, 0 and 1 remain unchanged when modulo $x \ge 2$ is applied. Consequently, if the array contians both 0 and 1, equality is impossible. Furthermore, if the array contains the value 1 and any pair of adjacent elements (in sorted order) differs by exactly 1, the sequence cannot be equalized. This is because the gap of 1 cannot be bridged without eliminating the 1, which is immutable under the allowed operations.

Implementation

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

using namespace std;

void solve() {
    int n;
    cin >> n;

    vector<int> values(n);
    bool hasOne = false;
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
        if (values[i] == 1) hasOne = true;
    }

    sort(values.begin(), values.end());

    for (int i = 1; i < n; ++i) {
        if (values[i] == values[i - 1] + 1 && hasOne) {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

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

Problem 2: Reconstructing Range Game Moves

Problem Statement

Alice and Bob play a game involving intervals. Initially, the set contains $[1, n]$. In each turn, Alice picks an interval $[l, r]$, and Bob chooses an integer $d$ within it. The interval is replaced by $[l, d-1]$ and $[d+1, r]$ (if valid). Given the list of all intervals Alice picked (unordered), determine the integer $d$ Bob chose for each interval.

Analysis

The process removes exactly one number from the coverage of the current interval. By processing intervals from largest to smallest, we can determine which number was removed. For a specific interval $[l, r]$, the chosen $d$ is the only number within that range not covered by any subsequent smaller intervals. A difference array combined with prefix sums efficiently tracks coverage counts.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct Range {
    int l, r, id;
};

void solve() {
    int n;
    cin >> n;
    vector<Range> ranges(n);
    for (int i = 0; i < n; ++i) {
        cin >> ranges[i].l >> ranges[i].r;
        ranges[i].id = i;
    }

    sort(ranges.begin(), ranges.end(), [](const Range& a, const Range& b) {
        return (a.r - a.l) > (b.r - b.l);
    });

    vector<int> result(n);
    for (int i = 0; i < n; ++i) {
        int currentL = ranges[i].l;
        int currentR = ranges[i].r;
        
        vector<int> diff(n + 2, 0);
        for (int j = i + 1; j < n; ++j) {
            diff[ranges[j].l]++;
            diff[ranges[j].r + 1]--;
        }

        int coverage = 0;
        for (int k = currentL; k <= currentR; ++k) {
            coverage += diff[k];
            if (coverage == 0) {
                result[ranges[i].id] = k;
                break;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << ranges[i].l << " " << ranges[i].r << " " << result[i] << "\n";
    }
    cout << "\n";
}

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

Problem 3: Maximizing Integer Purchase

Problem Statement

Find the largest integer $i$ such that $A \cdot i + B \cdot d(i) \le X$, where $d(i)$ represents the number of digits in $i$.

Analysis

The cost function is monotonically increasing with respect to $i$. This property allows us to use binary search over the possible range of integers $[0, 10^9]$. For each candidate mid-value, we calculate the digit count and verify the cost constraint.

Implementation

#include <iostream>
#include <string>

using namespace std;
using i64 = long long;

int countDigits(i64 num) {
    if (num == 0) return 1;
    int count = 0;
    while (num > 0) {
        num /= 10;
        count++;
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 A, B, X;
    cin >> A >> B >> X;

    i64 left = 0, right = 1000000000;
    i64 best = 0;

    while (left <= right) {
        i64 mid = left + (right - left) / 2;
        i64 cost = A * mid + B * countDigits(mid);
        if (cost <= X) {
            best = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    cout << best << "\n";
    return 0;
}

Problem 4: Dynamic String Construction

Problem Statement

Manage a string under two operations: reverse the entire string, or add a character to the front or back. Output the final string after all operations.

Analysis

Physically reversing the string repeatedly is inefficient. Instead, maintain a boolean flag indicating the current orientation. When adding characters, swap the "front" and "back" logic based on the flag. Finally, reverse the string once if the flag indicates it is upside down.

Implementation

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int q;
    cin >> q;

    bool isReversed = false;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            isReversed = !isReversed;
        } else {
            int pos;
            char c;
            cin >> pos >> c;
            // pos 1 means front, 2 means back relative to current view
            if (isReversed) {
                if (pos == 1) s += c;       // View front is actual back
                else s = c + s;             // View back is actual front
            } else {
                if (pos == 1) s = c + s;    // View front is actual front
                else s += c;                // View back is actual back
            }
        }
    }

    if (isReversed) reverse(s.begin(), s.end());
    cout << s << "\n";

    return 0;
}

Problem 5: Combinatorial Flower Selection

Problem Statement

Calculate the number of ways to select a subset of $n$ distinct flowers such that the subset size is neither $a$ nor $b$. Output the result modulo $10^9 + 7$.

Analysis

The total number of subsets is $2^n$. We subtract the combinations where the size is exactly $a$ or exactly $b$. The formula is $2^n - \binom{n}{a} - \binom{n}{b}$. Since $n$ can be large, combinations are computed using modular arithmetic and modular inverses for the denominator.

Implementation

#include <iostream>
#include <vector>

using namespace std;
using i64 = long long;

const i64 MOD = 1e9 + 7;

i64 modPow(i64 base, i64 exp) {
    i64 res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

i64 modInverse(i64 n) {
    return modPow(n, MOD - 2);
}

i64 nCr_large_n(i64 n, i64 r) {
    if (r < 0 || r > n) return 0;
    i64 num = 1;
    for (i64 i = 0; i < r; ++i) {
        num = (num * ((n - i) % MOD)) % MOD;
    }
    i64 den = 1;
    for (i64 i = 1; i <= r; ++i) {
        den = (den * i) % MOD;
    }
    return (num * modInverse(den)) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n, a, b;
    cin >> n >> a >> b;

    i64 total = modPow(2, n);
    i64 subA = nCr_large_n(n, a);
    i64 subB = nCr_large_n(n, b);

    i64 ans = (total - subA - subB) % MOD;
    // Handle negative modulo result
    ans = (ans + MOD) % MOD; 
    // The problem implies non-empty subsets usually, but based on formula 2^n includes empty.
    // Original code subtracted 1 extra, assuming non-empty requirement or specific contest logic.
    // Aligning with original logic:
    ans = (ans - 1 + MOD) % MOD; 

    cout << ans << "\n";
    return 0;
}

Problem 6: Counting Valid Permutations

Problem Statement

Construct permutations of length $n$ satisfying $m$ constraints. Each constraint $(X, Y, Z)$ dictates that among the first $X$ elements of the permutation, at most $Z$ elements can be less than or equal to $Y$.

Analyssi

This problem can be modeled using Dynamic Programming with bitmasking. The state represents the set of numbers already placed in the permutation. For each state, we verify if adding a new number violates any constraints regarding the count of small numbers in the prefix. We iterate through all masks and transition by adding one bit at a time.

Implementation

#include <iostream>
#include <vector>
#include <array>

using namespace std;
using i64 = long long;

struct Constraint {
    int x, y, z;
};

int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<Constraint> rules(m);
    for (int i = 0; i < m; ++i) {
        cin >> rules[i].x >> rules[i].y >> rules[i].z;
    }

    vector<i64> dp(1 << n, 0);
    dp[0] = 1;

    for (int mask = 0; mask < (1 << n); ++mask) {
        if (dp[mask] == 0) continue;

        int currentLen = countSetBits(mask);
        
        // Check validity of current state against rules
        bool valid = true;
        for (const auto& rule : rules) {
            if (currentLen <= rule.x) {
                // Count how many numbers <= rule.y are in the mask
                // Numbers are 0-indexed in mask, representing 1..n
                int countSmall = 0;
                for (int k = 0; k < rule.y; ++k) {
                    if ((mask >> k) & 1) countSmall++;
                }
                if (countSmall > rule.z) {
                    valid = false;
                    break;
                }
            }
        }

        if (!valid) {
            dp[mask] = 0;
            continue;
        }

        for (int i = 0; i < n; ++i) {
            if (!((mask >> i) & 1)) {
                dp[mask | (1 << i)] += dp[mask];
            }
        }
    }

    cout << dp[(1 << n) - 1] << "\n";
    return 0;
}

Problem 7: Lexicographically Smallest Concatenation

Problem Statement

Select exactly $K$ strings from a given set of $N$ strings and concatenate them to form the lexicographically smallest possible result.

Analysis

To minimize the lexicographical order of concatenated strings, we sort the strings using a custom comparator: $A + B < B + A$. After sorting, we use Dynamic Programming to select exactly $K$ strings. The DP state $dp[j]$ stores the smallest string formed by selecting $j$ strings from the processed subset.

Implementation

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<string> strs(n);
    for (int i = 0; i < n; ++i) {
        cin >> strs[i];
    }

    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a + b < b + a;
    });

    const string INF = string(1000, 'z' + 1);
    vector<string> dp(k + 1, INF);
    dp[0] = "";

    for (int i = 0; i < n; ++i) {
        for (int j = k; j >= 1; --j) {
            if (dp[j - 1] != INF) {
                string candidate = strs[i] + dp[j - 1];
                if (candidate < dp[j]) {
                    dp[j] = candidate;
                }
            }
        }
    }

    cout << dp[k] << "\n";
    return 0;
}