Problem A: Minimum Steps to Visit All Points Given a array of distinct integers x₁, x₂, ..., xₙ and a starting position s on the number line. You can move left or right by one unit each step. Find the minimum number of steps required to visit all positions in the array, starting from position s. The optimal solution involves visiting the endpoints in the most efficient order. If s lies between the minimum and maximum values, we must traverse the entire range between them. Otherwise, we simply move to the farthest endpoint. Implementation

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

using namespace std;

void solve() {
    int n, start;
    cin >> n >> start;
    vector<int> positions(n);
    for (int i = 0; i < n; i++) {
        cin >> positions[i];
    }
    sort(positions.begin(), positions.end());
    
    if (start <= positions[0]) {
        cout << positions[n-1] - start << endl;
    } else if (start >= positions[n-1]) {
        cout << start - positions[0] << endl;
    } else {
        int leftDist = start - positions[0];
        int rightDist = positions[n-1] - start;
        cout << positions[n-1] - positions[0] + min(leftDist, rightDist) << endl;
    }
}

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

Problem B: String Division with Substring Property Given a string s of lowercase letters, determine if it can be split into three non-empty strings a, b, and c such that b is a substring of a concatenated with c. The solution checks if any character (except possibly the first and last) appears at least twice in the string. This condition guarantees we can find suitable partitions. Implementation

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

using namespace std;

void solve() {
    int length;
    string str;
    cin >> length >> str;
    
    vector<int> freq(26, 0);
    for (char ch : str) {
        freq[ch - 'a']++;
    }
    
    for (int i = 1; i < length - 1; i++) {
        if (freq[str[i] - 'a'] > 1) {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

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

Problem C: Matrix Reduction Operation Given an n×m matrix, you can perform exactly one operation: select a row r and column c, then subtract 1 from all cells in row r or column c. Find the minimum possible maximum value in the matrix after this operation. The strategy is to identify if there exists a row or column that contains all maximum values. If such a row or column exists, we can reduce the maximum by 1; otherwise, the maximum remains unchanged. Implementation

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

using namespace std;

void solve() {
    int rows, cols;
    cin >> rows >> cols;
    vector<vector<int>> matrix(rows + 1, vector<int>(cols + 1));
    
    int maxValue = 0;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> matrix[i][j];
            maxValue = max(maxValue, matrix[i][j]);
        }
    }
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (matrix[i][j] == maxValue) {
                set<int> maxColumns;
                for (int r = 1; r <= rows; r++) {
                    for (int c = 1; c <= cols; c++) {
                        if (matrix[r][c] == maxValue && r != i) {
                            maxColumns.insert(c);
                        }
                    }
                }
                if (maxColumns.size() <= 1) {
                    cout << maxValue - 1 << endl;
                    return;
                }
                
                set<int> maxRows;
                for (int r = 1; r <= rows; r++) {
                    for (int c = 1; c <= cols; c++) {
                        if (matrix[r][c] == maxValue && c != j) {
                            maxRows.insert(r);
                        }
                    }
                }
                if (maxRows.size() <= 1) {
                    cout << maxValue - 1 << endl;
                    return;
                }
                
                cout << maxValue << endl;
                return;
            }
        }
    }
}

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

Problem D: Array Sorting with Limited Operations Given two arrays a and b containing all integers from 1 to 2n exactly once, transform them using at most 1709 operations so that: both arrays are strict increasing, and aᵢ < bᵢ for all i. The approach sorts each array individually by moving elements to their correct positions, then fixes any violations where aᵢ > bᵢ by swapping those pairs. Implementation

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

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> arrA(n + 1), arrB(n + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> arrA[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> arrB[i];
    }
    
    vector<int> sortedA = arrA, sortedB = arrB;
    sort(sortedA.begin() + 1, sortedA.end());
    sort(sortedB.begin() + 1, sortedB.end());
    
    vector<pair<int, int>> operations;
    
    // Sort array A
    for (int target = n; target >= 1; target--) {
        for (int pos = 1; pos < n; pos++) {
            if (arrA[pos] == sortedA[target]) {
                while (pos < target) {
                    operations.push_back({1, pos});
                    swap(arrA[pos], arrA[pos + 1]);
                    pos++;
                }
                break;
            }
        }
    }
    
    // Sort array B
    for (int target = n; target >= 1; target--) {
        for (int pos = 1; pos < n; pos++) {
            if (arrB[pos] == sortedB[target]) {
                while (pos < target) {
                    operations.push_back({2, pos});
                    swap(arrB[pos], arrB[pos + 1]);
                    pos++;
                }
                break;
            }
        }
    }
    
    // Fix a[i] > b[i] violations
    for (int i = 1; i <= n; i++) {
        if (arrA[i] > arrB[i]) {
            operations.push_back({3, i});
            swap(arrA[i], arrB[i]);
        }
    }
    
    cout << operations.size() << endl;
    for (auto op : operations) {
        cout << op.first << " " << op.second << endl;
    }
}

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

Problem E: Minimizing Digit Match Function For integers a and b, define f(a,b) as the count of matching digits at the same positions. Given l and r with equal digit lengths, find the minimum value of f(l,x) + f(x,r) for l ≤ x ≤ r. The solution processes digits from most significant to least, analyzing cases where digits differ and optimizing based on the available choices for x's digits. Implementation

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

using namespace std;

void solve() {
    int left, right;
    cin >> left >> right;
    
    vector<int> leftDigits, rightDigits;
    while (left > 0) {
        leftDigits.push_back(left % 10);
        rightDigits.push_back(right % 10);
        left /= 10;
        right /= 10;
    }
    reverse(leftDigits.begin(), leftDigits.end());
    reverse(rightDigits.begin(), rightDigits.end());
    
    for (int i = 0; i < leftDigits.size(); i++) {
        if (leftDigits[i] != rightDigits[i]) {
            if (rightDigits[i] - leftDigits[i] > 1) {
                cout << 2 * i << endl;
                return;
            } else {
                int option1 = 1, option2 = 1;
                
                // Option 1: use left digit
                for (int j = i + 1; j < leftDigits.size(); j++) {
                    if (leftDigits[j] == 9) {
                        option1 += 1 + (rightDigits[j] == 9);
                    } else {
                        if (leftDigits[j] == 8 && rightDigits[j] == 9) option1++;
                        break;
                    }
                }
                
                // Option 2: use right digit
                for (int j = i + 1; j < leftDigits.size(); j++) {
                    if (rightDigits[j] == 0) {
                        option2 += 1 + (leftDigits[j] == 0);
                    } else {
                        if (rightDigits[j] == 1 && leftDigits[j] == 0) option2++;
                        break;
                    }
                }
                
                cout << min(option1, option2) + 2 * i << endl;
                return;
            }
        }
    }
    
    cout << 2 * leftDigits.size() << endl;
}

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

Problem F: Subarrays with Sum and Maximum Constraints Count subarrays where the sum equals s and the maximum element equals x. The solution uses prefix sums with additional tracking of positions where elements exceed x or equal x. Implementation

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

using namespace std;

void solve() {
    int n;
    long long targetSum, targetMax;
    cin >> n >> targetSum >> targetMax;
    
    vector<int> elements(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> elements[i];
    }
    
    map<long long, vector<int>> prefixPositions;
    prefixPositions[0].push_back(0);
    
    long long currentSum = 0;
    long long answer = 0;
    int lastMaxPos = -1e9, lastExceedPos = -1e9;
    
    for (int i = 1; i <= n; i++) {
        currentSum += elements[i];
        
        if (elements[i] == targetMax) {
            lastMaxPos = i;
        } else if (elements[i] > targetMax) {
            lastExceedPos = i;
        }
        
        if (lastMaxPos >= lastExceedPos && prefixPositions.count(currentSum - targetSum)) {
            auto it1 = lower_bound(prefixPositions[currentSum - targetSum].begin(), 
                                  prefixPositions[currentSum - targetSum].end(), lastMaxPos);
            auto it2 = lower_bound(prefixPositions[currentSum - targetSum].begin(), 
                                  prefixPositions[currentSum - targetSum].end(), lastExceedPos);
            answer += distance(it2, it1);
        }
        
        prefixPositions[currentSum].push_back(i);
    }
    
    cout << answer << endl;
}

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

Problem G: Binary String Character Dominance For a binary string, calculate the sum of f(substring) over all substrings, where f(p) is the maximum frequency of either '0' or '1' in substring p. Implementation

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

using namespace std;

class SegmentTree {
private:
    struct Node {
        int left, right;
        long long sum, count;
    };
    vector<Node> tree;
    
public:
    SegmentTree(int l, int r) : tree(vector<Node>(((r - l + 10) << 2) + 10)) {
        build(1, l, r);
    }
    
    void pushup(int u) {
        tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
        tree[u].count = tree[u << 1].count + tree[u << 1 | 1].count;
    }
    
    void build(int u, int l, int r) {
        tree[u] = {l, r};
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    
    long long query(int u, int l, int r, bool getSum) {
        if (l > r) return 0;
        if (tree[u].left >= l && tree[u].right <= r) {
            return getSum ? tree[u].sum : tree[u].count;
        }
        int mid = tree[u].left + tree[u].right >> 1;
        long long result = 0;
        if (l <= mid) result += query(u << 1, l, r, getSum);
        if (r > mid) result += query(u << 1 | 1, l, r, getSum);
        return result;
    }
    
    void update(int u, int x, long long v) {
        if (tree[u].left == tree[u].right) {
            tree[u].count++;
            tree[u].sum += v;
        } else {
            int mid = tree[u].left + tree[u].right >> 1;
            if (x <= mid) update(u << 1, x, v);
            else update(u << 1 | 1, x, v);
            pushup(u);
        }
    }
};

void solve() {
    int n;
    string binaryStr;
    cin >> n >> binaryStr;
    
    long long answer = 0;
    
    // Count substrings where 1s >= 0s
    SegmentTree st1(-n, n);
    st1.update(1, 0, 0);
    int balance1 = 0, onesCount = 0;
    
    for (int i = 0; i < n; i++) {
        balance1 += (binaryStr[i] == '1') ? 1 : -1;
        onesCount += (binaryStr[i] == '1');
        
        answer -= st1.query(1, -n, balance1, true);
        answer += st1.query(1, -n, balance1, false) * onesCount;
        
        st1.update(1, balance1, onesCount);
    }
    
    // Count substrings where 0s > 1s
    SegmentTree st0(-n - 1, n);
    st0.update(1, 0, 0);
    int balance0 = 0, zerosCount = 0;
    
    for (int i = 0; i < n; i++) {
        balance0 += (binaryStr[i] == '0') ? 1 : -1;
        zerosCount += (binaryStr[i] == '0');
        
        answer -= st0.query(1, -n - 1, balance0 - 1, true);
        answer += st0.query(1, -n - 1, balance0 - 1, false) * zerosCount;
        
        st0.update(1, balance0, zerosCount);
    }
    
    cout << answer << endl;
}

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

Problem H: Maximum Non-Decreasing Subsequence with Bounds For each prefix length k of arrays l and r, find the maximum possible length of a non-decreasing subsequence in any array a where lᵢ ≤ aᵢ ≤ rᵢ. Implementation

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

using namespace std;

class LazySegmentTree {
private:
    struct Node {
        int left, right;
        long long maxValue, lazyTag;
    };
    vector<Node> tree;
    
public:
    LazySegmentTree(int l, int r) : tree(vector<Node>(((r - l + 10) << 2) + 10)) {
        build(1, l, r);
    }
    
    void pushup(int u) {
        tree[u].maxValue = max(tree[u << 1].maxValue, tree[u << 1 | 1].maxValue);
    }
    
    void apply(Node& node, long long value) {
        node.lazyTag += value;
        node.maxValue += value;
    }
    
    void pushdown(int u) {
        if (tree[u].lazyTag != 0) {
            apply(tree[u << 1], tree[u].lazyTag);
            apply(tree[u << 1 | 1], tree[u].lazyTag);
            tree[u].lazyTag = 0;
        }
    }
    
    void build(int u, int l, int r) {
        tree[u] = {l, r, 0, 0};
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    
    long long query(int u, int l, int r) {
        if (tree[u].left >= l && tree[u].right <= r) return tree[u].maxValue;
        pushdown(u);
        int mid = tree[u].left + tree[u].right >> 1;
        long long result = 0;
        if (l <= mid) result = query(u << 1, l, r);
        if (r > mid) result = max(result, query(u << 1 | 1, l, r));
        return result;
    }
    
    void rangeUpdate(int u, int l, int r, long long value) {
        if (tree[u].left >= l && tree[u].right <= r) {
            apply(tree[u], value);
            return;
        }
        pushdown(u);
        int mid = tree[u].left + tree[u].right >> 1;
        if (l <= mid) rangeUpdate(u << 1, l, r, value);
        if (r > mid) rangeUpdate(u << 1 | 1, l, r, value);
        pushup(u);
    }
    
    void pointUpdate(int u, int x, long long value) {
        if (tree[u].left == tree[u].right) {
            tree[u].maxValue = value;
            return;
        }
        pushdown(u);
        int mid = tree[u].left + tree[u].right >> 1;
        if (x <= mid) pointUpdate(u << 1, x, value);
        else pointUpdate(u << 1 | 1, x, value);
        pushup(u);
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> lower(n + 1), upper(n + 1);
    vector<int> compressedValues;
    
    for (int i = 1; i <= n; i++) {
        cin >> lower[i] >> upper[i];
        compressedValues.push_back(lower[i]);
        compressedValues.push_back(upper[i]);
    }
    
    sort(compressedValues.begin(), compressedValues.end());
    compressedValues.erase(unique(compressedValues.begin(), compressedValues.end()), compressedValues.end());
    
    auto getIndex = [&](int x) {
        return lower_bound(compressedValues.begin(), compressedValues.end(), x) - compressedValues.begin();
    };
    
    for (int i = 1; i <= n; i++) {
        lower[i] = getIndex(lower[i]);
        upper[i] = getIndex(upper[i]);
    }
    
    LazySegmentTree seg(0, compressedValues.size());
    
    for (int i = 1; i <= n; i++) {
        int bestEndingAtLower = seg.query(1, 0, lower[i]) + 1;
        seg.pointUpdate(1, lower[i], bestEndingAtLower);
        if (lower[i] != upper[i]) {
            seg.rangeUpdate(1, lower[i] + 1, upper[i], 1);
        }
        cout << seg.query(1, 0, compressedValues.size()) << " ";
    }
    cout << endl;
}

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