Intersection Calculation

Given two line segments [L1, R1] and [L2, R2], determine their overlapping length. A simple approach uses a frequency array to mark covered positions.

#include <iostream>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    int coverage[101] = {0}, overlap = 0;
    cin >> L1 >> R1 >> L2 >> R2;
    
    for (int i = L1; i <= R1; i++) coverage[i]++;
    for (int i = L2; i <= R2; i++) coverage[i]++;
    
    for (int i = 0; i <= 100; i++)
        if (coverage[i] == 2) overlap++;
    
    cout << (overlap ? overlap - 1 : 0) << endl;
    return 0;
}

Tournament Result Validation

Verify if a tournament result matrix is consistent by checking all pairs (i,j) and (j,i).

#include <iostream>
using namespace std;

bool isValid(char a, char b) {
    if (a == b && a != 'D') return false;
    if (a == 'D' && b != 'D') return false;
    return true;
}

int main() {
    int n;
    char results[1001][1001];
    cin >> n;
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> results[i][j];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && !isValid(results[i][j], results[j][i])) {
                cout << "incorrect" << endl;
                return 0;
            }
        }
    }
    cout << "correct" << endl;
    return 0;
}

File Naming with Duplicates

Generate unique filenames by appending counters to duplicates using a hash map.

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

int main() {
    int n;
    string filename;
    unordered_map<string, int> counts;
    
    cin >> n;
    while (n--) {
        cin >> filename;
        counts[filename]++;
        if (counts[filename] == 1) cout << filename << endl;
        else cout << filename << "(" << counts[filename]-1 << ")" << endl;
    }
    return 0;
}

Coin Flipping with Bonuses

Maximize earnings from coin flips with consecutive head bonuses using dynamic programming.

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

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<long long> x(n+1), c(5001), y(5001);
    vector<long long> prefixSum(n+1), bonusSum(5001), dp(n+1);
    
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        prefixSum[i] = prefixSum[i-1] + x[i];
    }
    
    while (m--) {
        int ci, yi;
        cin >> ci >> yi;
        c[ci] = yi;
    }
    
    for (int i = 1; i <= 5000; i++)
        bonusSum[i] = bonusSum[i-1] + c[i];
    
    for (int i = 1; i <= n; i++) {
        dp[i] = prefixSum[i] + bonusSum[i];
        for (int j = 0; j < i; j++)
            dp[i] = max(dp[i], dp[j] + prefixSum[i] - prefixSum[j+1] + bonusSum[i-j-1]);
    }
    
    cout << dp[n] << endl;
    return 0;
}

Bitwise Operations Sequence

Process a sequence of bitwise operations efficient using dynamic programming per bit.

#include <iostream>
using namespace std;

int main() {
    int n, c;
    cin >> n >> c;
    
    int operations[n+1], operands[n+1];
    int dp[30][2][n+1];
    
    for (int i = 1; i <= n; i++)
        cin >> operations[i] >> operands[i];
    
    for (int bit = 0; bit < 30; bit++) {
        for (int init = 0; init < 2; init++) {
            dp[bit][init][0] = init;
            for (int step = 1; step <= n; step++) {
                int mask = (operands[step] >> bit) & 1;
                switch (operations[step]) {
                    case 1: dp[bit][init][step] = dp[bit][init][step-1] & mask; break;
                    case 2: dp[bit][init][step] = dp[bit][init][step-1] | mask; break;
                    case 3: dp[bit][init][step] = dp[bit][init][step-1] ^ mask; break;
                }
            }
        }
    }
    
    for (int step = 1; step <= n; step++) {
        int result = 0;
        for (int bit = 0; bit < 30; bit++)
            result += (dp[bit][(c >> bit) & 1][step] << bit);
        cout << result << endl;
        c = result;
    }
    return 0;
}

Colored Balls Inversion Count

Calculate inversion count while ignoring same-color pairs using coordinate compression and BIT.

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

struct BIT {
    vector<int> tree;
    BIT(int size) : tree(size + 1) {}
    
    void update(int idx, int delta) {
        for (; idx < tree.size(); idx += idx & -idx)
            tree[idx] += delta;
    }
    
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx)
            sum += tree[idx];
        return sum;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> colors(n), values(n);
    vector<int> sortedValues;
    
    for (int i = 0; i < n; i++) cin >> colors[i];
    for (int i = 0; i < n; i++) {
        cin >> values[i];
        sortedValues.push_back(values[i]);
    }
    
    sort(sortedValues.begin(), sortedValues.end());
    sortedValues.erase(unique(sortedValues.begin(), sortedValues.end()), sortedValues.end());
    
    BIT globalBIT(sortedValues.size());
    vector<BIT> colorBITs(n+1, BIT(sortedValues.size()));
    vector<int> colorCounts(n+1, 0);
    
    long long inversions = 0;
    
    for (int i = 0; i < n; i++) {
        int compressed = lower_bound(sortedValues.begin(), sortedValues.end(), values[i]) - sortedValues.begin() + 1;
        int sameColor = colorBITs[colors[i]].query(compressed);
        int allColors = globalBIT.query(compressed);
        
        inversions += (i - colorCounts[colors[i]]) - (allColors - sameColor);
        
        colorCounts[colors[i]]++;
        globalBIT.update(compressed, 1);
        colorBITs[colors[i]].update(compressed, 1);
    }
    
    cout << inversions << endl;
    return 0;
}