Prime Pair Search

Description

Given an even number, find two prime numbers that are closest to eachother and sum to the even number.

Approach

Precompute primes up to 100,000 using the Euler sieve. Then, for each input even number, iterate through the primes and check if both the current prime and the complement (even number minus prime) are prime. Track the pair with the smallest difference.

Code

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

vector<int> sieve_primes(int limit) {
    vector<int> primes;
    vector<bool> is_prime(limit + 1, true);
    vector<int> phi(limit + 1);
    is_prime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= limit; j++) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j]) {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            } else {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
    return primes;
}

const int MAX_N = 100000;
auto primes = sieve_primes(MAX_N);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    set<int> prime_set(primes.begin(), primes.end());
    int num;
    while (cin >> num) {
        pair<int, int> result = {0, 0};
        for (int p : primes) {
            if (p > num) break;
            if (prime_set.count(num - p)) {
                if (!result.first) {
                    result = {p, num - p};
                } else if (abs(num - 2 * p) < abs(result.first - result.second)) {
                    result = {p, num - p};
                }
            }
        }
        if (result.first > result.second) swap(result.first, result.second);
        cout << result.first << ' ' << result.second << '\n';
    }
    return 0;
}

Planar Division by Curves

Description

Given n points with each having at least two connecting curved segments, calculate the number of curve segments required to divide the plane into m regions.

Approach

The minimum configuration requires n segments. Each additional region requires one extra segment, leading to the formula n + m - 2.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll points, regions;
    while (cin >> points >> regions && points && regions) {
        cout << points + regions - 2 << '\n';
    }
    return 0;
}

Optimal Item Pairing

Description

Select 2k items from n available items such that the sum of squared weight differences between paired items is minimized.

Approach

Sort items by weight and compute squared differences between adjacent items. Use dynamic programming where dp[i][j] represents the minimum cost for the first i items with j pairs.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int total_items, pairs;
    while (cin >> total_items >> pairs) {
        vector<ll> weights(total_items + 1);
        for (int i = 1; i <= total_items; i++) cin >> weights[i];
        sort(weights.begin() + 1, weights.end());
        vector<vector<ll>> dp(total_items + 1, vector<ll>(pairs + 1, LLONG_MAX / 2));
        vector<ll> diffs(total_items);
        for (int i = 1; i < total_items; i++) {
            diffs[i] = pow(weights[i + 1] - weights[i], 2);
        }
        for (int i = 0; i <= total_items; i++) dp[i][0] = 0;
        for (int i = 2; i <= total_items; i++) {
            for (int j = 1; j <= pairs && 2 * j <= i; j++) {
                dp[i][j] = min(diffs[i - 1] + dp[i - 2][j - 1], dp[i - 1][j]);
            }
        }
        cout << dp[total_items][pairs] << '\n';
    }
    return 0;
}

Nuts Collection

Description

Calculate the total number of nuts collected where each tree yields max(0, nuts - 10).

Approach

Iterate through each input value and accumulate the excess nuts above 10.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int trees;
    cin >> trees;
    int total = 0;
    while (trees--) {
        int nuts;
        cin >> nuts;
        total += max(0, nuts - 10);
    }
    cout << total << '\n';
    return 0;
}

Subset Sum Modulo 200

Description

Given a sequence of positive integers, find two distinct non-empty subsequences with equal sums modulo 200.

Approach

Enumerate all possible non-empty subsets for sequences up to size 8. Use a map to store sums modulo 200 and their corresponding indices. If duplicate sums are found, output the subsequences.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    const int MOD = 200;
    vector<ll> values(n);
    for (auto &val : values) cin >> val;
    n = min(n, 8);
    map<int, vector<int>> sum_map;
    auto print_seq = [](vector<int> seq) {
        cout << seq.size() << ' ';
        for (size_t i = 0; i < seq.size(); i++) {
            cout << seq[i] << " \n"[i == seq.size() - 1];
        }
    };
    for (int mask = 1; mask < (1 << n); mask++) {
        ll current_sum = 0;
        vector<int> indices;
        for (int j = 0; j < n; j++) {
            if (mask & (1 << j)) {
                current_sum = (current_sum + values[j]) % MOD;
                indices.push_back(j + 1);
            }
        }
        if (sum_map.count(current_sum)) {
            cout << "Yes\n";
            print_seq(sum_map[current_sum]);
            print_seq(indices);
            return 0;
        } else {
            sum_map[current_sum] = indices;
        }
    }
    cout << "No\n";
    return 0;
}

Maximizing Condition Satisfaction

Description

Given n dishes and m conditions, maximize satisfied conditions where each condition requires two specific dishes to receive votes. k voters each choose between two dishes.

Approach

Use bitmask enumeration to test all 2^k possible voting patterns. For each pattern, count how many conditions are satisfied and track the maximum count.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int dishes, conditions;
    cin >> dishes >> conditions;
    vector<pair<int, int>> reqs(conditions);
    for (auto &[a, b] : reqs) cin >> a >> b;
    int voters;
    cin >> voters;
    vector<pair<int, int>> choices(voters);
    for (auto &[c, d] : choices) cin >> c >> d;
    int max_satisfied = 0;
    for (int mask = 0; mask < (1 << voters); mask++) {
        vector<int> votes(dishes + 1, 0);
        for (int v = 0; v < voters; v++) {
            votes[choices[v][(mask >> v) & 1]]++;
        }
        int satisfied = 0;
        for (auto [a, b] : reqs) {
            satisfied += (votes[a] > 0 && votes[b] > 0);
        }
        max_satisfied = max(max_satisfied, satisfied);
    }
    cout << max_satisfied << '\n';
    return 0;
}

Minimum Time Traversal

Description

Find the shortest time to traverse from node 1 to n in a graph where edge traversal time at time t is c + floor(d/(t+1)).

Approach

Use Dijkstra's algorithm with priority queue. For each edge, compute optimal departure time as max(current_time, sqrt(d)-1) to minimize traversal cost.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int nodes, edges;
    cin >> nodes >> edges;
    vector<vector<tuple<int, int, int>>> graph(nodes + 1);
    for (int i = 0; i < edges; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        graph[u].emplace_back(v, c, d);
        graph[v].emplace_back(u, c, d);
    }
    vector<ll> dist(nodes + 1, -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[1] = 0;
    pq.emplace(0, 1);
    while (!pq.empty()) {
        auto [time, node] = pq.top();
        pq.pop();
        if (dist[node] != time) continue;
        for (auto [neighbor, c, d] : graph[node]) {
            ll optimal_time = max(time, static_cast<ll>(sqrt(d)) - 1);
            ll new_time = optimal_time + c + d / (optimal_time + 1);
            if (dist[neighbor] == -1 || dist[neighbor] > new_time) {
                dist[neighbor] = new_time;
                pq.emplace(new_time, neighbor);
            }
        }
    }
    cout << dist[nodes] << '\n';
    return 0;
}

Counting Descendants by Depth

Description

Count nodes at specific depth that are descendants of a given node in a tree.

Approach

Perform DFS to record in-time and out-time for each node. For each query, use binary search on precomputed depth-based in-time lists to count valid descendants.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int nodes;
    cin >> nodes;
    vector<vector<int>> tree(nodes + 1);
    for (int i = 2; i <= nodes; i++) {
        int parent;
        cin >> parent;
        tree[parent].push_back(i);
    }
    int counter = 0;
    map<int, vector<int>> depth_map;
    vector<int> in_time(nodes + 1), out_time(nodes + 1);
    function<void(int, int)> dfs = [&](int node, int depth) {
        in_time[node] = counter++;
        depth_map[depth].push_back(in_time[node]);
        for (int child : tree[node]) {
            dfs(child, depth + 1);
        }
        out_time[node] = counter++;
    };
    dfs(1, 0);
    int queries;
    cin >> queries;
    while (queries--) {
        int node, depth;
        cin >> node >> depth;
        auto &times = depth_map[depth];
        auto start = lower_bound(times.begin(), times.end(), in_time[node]);
        auto end = lower_bound(times.begin(), times.end(), out_time[node]);
        cout << distance(start, end) << '\n';
    }
    return 0;
}

Minimum Digit Removal for Divisibility

Description

Find the minimum number of digits to remove from a number to make it divisible by 3.

Approach

Enumerate all possible digit removal patterns using bitmask. For each pattern, check if the resulting number is divisible by 3 and track the minimal removals.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll number;
    cin >> number;
    ll min_removals = -1;
    ll num_length = 0;
    ll temp = number;
    while (temp) {
        num_length++;
        temp /= 10;
    }
    for (ll mask = 0; mask < (1LL << num_length); mask++) {
        ll result_num = 0;
        ll removals = 0;
        ll divisor = pow(10, num_length - 1);
        for (int pos = 0; pos < num_length; pos++) {
            int digit = (number / divisor) % 10;
            if (!(mask & (1LL << pos))) {
                result_num = result_num * 10 + digit;
            } else {
                removals++;
            }
            divisor /= 10;
        }
        if (result_num && result_num % 3 == 0) {
            if (min_removals == -1) min_removals = removals;
            else min_removals = min(min_removals, removals);
        }
    }
    cout << min_removals << '\n';
    return 0;
}