Description:

In the Kingdom of Caima, there is a peculiar prison with P cells arranged in a linear fashion, where cell i is adjacent to cell i+1 (except for the last cell). Currently, all cells are occupied. An order has been issued to release one person from a specified list each day. The P prisoners in the cells can communicate with each other. When a prisoner is released, all prisoners who could previously communicate with them require one meat piece each. The task is to determine the minimum number of meat pieces needed.

Solution:

This problem can be solved using interval dynamic programming. Let dp[i][j] represent the minimum number of meat pieces needed to release all prisoners in the interval [i, j]. The transition follows the standard interval DP approach, adapting it to the specific problem requirements. The solution is implemented using a divide-and-conquer approach with memoization.

Code:

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

const int MAX_N = 105;
int n, m;
vector<int> positions;
vector<vector<int>> memo;
int INF = INT_MAX;

int solve(int left, int right) {
    if (memo[left][right] != -1) {
        return memo[left][right];
    }
    
    if (right == left + 1) {
        return 0;
    }
    
    int min_pieces = INF;
    for (int i = left + 1; i < right; i++) {
        int current = positions[right] - positions[left] - 2 + 
                      solve(left, i) + solve(i, right);
        if (current < min_pieces) {
            min_pieces = current;
        }
    }
    
    memo[left][right] = min_pieces;
    return min_pieces;
}

int main() {
    cin >> n >> m;
    positions.resize(m + 2);
    
    for (int i = 1; i <= m; i++) {
        cin >> positions[i];
    }
    positions[m + 1] = n + 1;
    
    memo.resize(m + 2, vector<int>(m + 2, -1));
    
    cout << solve(0, m + 1) << endl;
    return 0;
}

Color Panel Game

Description:

There is a color panel of length n, initially filled with color 1. Two operations can be performed:

1. Paint the entire interval [i, j] with color c
2. Count the number of distinct colors in the interval [i, j]

The task is to output the results of each type 2 operation.

Solution:

A segment tree can be used to efficiently handle both range updates and range queries. Each node in the segment tree stores information about the colors present in its interval, allowing for efficient updates and queries.

Code:

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

const int MAX_N = 100005;
const int MAX_COLORS = 35;

struct Node {
    int left, right;
    vector<int> color_count;
    int lazy;
};

vector<Node> tree;
vector<int> base_colors;

void build(int node, int l, int r) {
    tree[node].left = l;
    tree[node].right = r;
    tree[node].color_count.resize(MAX_COLORS, 0);
    tree[node].lazy = 0;
    
    if (l == r) {
        tree[node].color_count[base_colors[l]] = 1;
        return;
    }
    
    int mid = (l + r) / 2;
    build(2 * node + 1, l, mid);
    build(2 * node + 2, mid + 1, r);
    
    for (int i = 1; i < MAX_COLORS; i++) {
        tree[node].color_count[i] = 
            tree[2 * node + 1].color_count[i] + 
            tree[2 * node + 2].color_count[i];
    }
}

void apply_lazy(int node, int color) {
    for (int i = 1; i < MAX_COLORS; i++) {
        tree[node].color_count[i] = 0;
    }
    tree[node].color_count[color] = tree[node].right - tree[node].left + 1;
    tree[node].lazy = color;
}

void push_down(int node) {
    if (tree[node].lazy != 0) {
        apply_lazy(2 * node + 1, tree[node].lazy);
        apply_lazy(2 * node + 2, tree[node].lazy);
        tree[node].lazy = 0;
    }
}

void update(int node, int l, int r, int color) {
    if (tree[node].left >= l && tree[node].right <= r) {
        apply_lazy(node, color);
        return;
    }
    
    push_down(node);
    int mid = (tree[node].left + tree[node].right) / 2;
    
    if (l <= mid) {
        update(2 * node + 1, l, r, color);
    }
    if (r > mid) {
        update(2 * node + 2, l, r, color);
    }
    
    for (int i = 1; i < MAX_COLORS; i++) {
        tree[node].color_count[i] = 
            tree[2 * node + 1].color_count[i] + 
            tree[2 * node + 2].color_count[i];
    }
}

int query(int node, int l, int r) {
    if (tree[node].left >= l && tree[node].right <= r) {
        int distinct = 0;
        for (int i = 1; i < MAX_COLORS; i++) {
            if (tree[node].color_count[i] > 0) {
                distinct++;
            }
        }
        return distinct;
    }
    
    push_down(node);
    int mid = (tree[node].left + tree[node].right) / 2;
    int result = 0;
    
    if (l <= mid) {
        result = max(result, query(2 * node + 1, l, r));
    }
    if (r > mid) {
        result = max(result, query(2 * node + 2, l, r));
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    base_colors.resize(n + 1, 1);
    tree.resize(4 * (n + 1));
    
    build(0, 1, n);
    
    while (q--) {
        char op;
        int l, r;
        cin >> op >> l >> r;
        if (l > r) swap(l, r);
        
        if (op == 'C') {
            int c;
            cin >> c;
            update(0, l, r, c);
        } else {
            cout << query(0, l, r) << "\n";
        }
    }
    
    return 0;
}

Escape Game

Description:

A n×m matrix appears on the ground, with each cell containing varying amounts of magic liquid (0 to k). Two players, Player A and Player UIM, are given magic bottles. They can start at any cell, move right or down at each step, and end at any cell. Player A absorbs the magic liquid first, followed by Player UIM, alternating turns. The last step must be taken by Player UIM. The magic bottle has a capactiy of k - if it exceeds k, it resets to zero, and if it exceeds k+1, only 1 remains, and so on. If both players end with the same amount of liquid, they survive. The task is to count the number of ways they can both survive.

Solution:

This is a coordinate dynamic programming problem. Let dp[i][j][a][b][turn] represent the number of ways to reach position (i, j) with Player A having 'a' liquid and Player UIM having 'b' liquid, where turn indicates whose turn it is (0 for Player A, 1 for Player UIM). The transitions follow the problem requirements, with liquid amounts modulo (k+1). The solution uses a rolling array for efficiency.

Code:

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

const int MOD = 1000000007;
const int MAX_N = 802;
const int MAX_H = 17;

int n, m, h;
vector<vector<int>> grid;
vector<vector<vector<vector<vector<int>>>> dp;
int result = 0;

int mod(int x) {
    return (x % MOD + MOD) % MOD;
}

void initialize() {
    dp.resize(2);
    for (int i = 0; i < 2; i++) {
        dp[i].resize(MAX_N);
        for (int j = 0; j < MAX_N; j++) {
            dp[i][j].resize(MAX_H + 1);
            for (int k = 0; k <= MAX_H; k++) {
                dp[i][j][k].resize(MAX_H + 1);
                for (int l = 0; l <= MAX_H; l++) {
                    dp[i][j][k][l].resize(2, 0);
                }
            }
        }
    }
}

int calculate_adjusted(int current, int value) {
    int adjusted = current - value;
    if (adjusted < 0) adjusted += (h + 1);
    if (adjusted > h) adjusted -= (h + 1);
    return adjusted;
}

int solve() {
    initialize();
    
    for (int i = 0; i < n; i++) {
        int current = i & 1;
        int previous = 1 - current;
        
        for (int j = 0; j < m; j++) {
            for (int a = 0; a <= h; a++) {
                for (int b = 0; b <= h; b++) {
                    for (int turn = 0; turn < 2; turn++) {
                        dp[current][j][a][b][turn] = 0;
                        
                        if (turn == 0) {
                            // Player A's turn
                            if (a == grid[i][j] && b == 0) {
                                dp[current][j][a][b][turn] = 1;
                            }
                            
                            // Check from above
                            int prev_a = calculate_adjusted(a, grid[i][j]);
                            dp[current][j][a][b][turn] = mod(
                                dp[current][j][a][b][turn] + 
                                dp[previous][j][prev_a][b][1]
                            );
                            
                            // Check from left
                            prev_a = calculate_adjusted(a, grid[i][j]);
                            dp[current][j][a][b][turn] = mod(
                                dp[current][j][a][b][turn] + 
                                dp[current][j-1][prev_a][b][1]
                            );
                        } else {
                            // Player UIM's turn
                            int prev_b = calculate_adjusted(b, grid[i][j]);
                            dp[current][j][a][b][turn] = mod(
                                dp[current][j][a][b][turn] + 
                                dp[previous][j][a][prev_b][0]
                            );
                            
                            prev_b = calculate_adjusted(b, grid[i][j]);
                            dp[current][j][a][b][turn] = mod(
                                dp[current][j][a][b][turn] + 
                                dp[current][j-1][a][prev_b][0]
                            );
                        }
                        
                        if (a == b && turn == 1) {
                            result = mod(result + dp[current][j][a][b][turn]);
                        }
                    }
                }
            }
        }
    }
    
    return result;
}

int main() {
    cin >> n >> m >> h;
    grid.resize(n, vector<int>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    cout << solve() << endl;
    return 0;
}

Tree Weight Calculation

Description:

An "evolution tree" is a tree with weighted edges where leaf nodes represent species, and the distance between two leaves represents the difference between species. Given a matrix M where M[i][j] represents the distance between species i and j, the task is to reconstruct the corresponding evolution tree and calculate its total weight (sum of all edge weights).

Solution:

The solution involves treating node 1 as the root and analyzing pairs of leaf nodes. For each pair (i, j), we can determine the distances from i and j to their lowest common ancestor (LCA) using the formula: distance(i, LCA) = (distance(i, j) + distance(i, root) - distance(j, root)) / 2. Nodes that share the same parent form a "group." By analyzing these groups, we can construct the complete evolution tree and calculate its total weight.

Code:

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

const int MAX_N = 35;

int n;
vector<vector<int>> distance_matrix;
vector<int> min_distance;
vector<int> parent;
vector<vector<int>> group_distance;
map<pair<int, int>, bool> visited;
int result = 0;

int find_parent(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find_parent(parent[x]);
}

void calculate_min_distances() {
    for (int i = 1; i <= n; i++) {
        min_distance[i] = distance_matrix[1][i];
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int root = 1;
            while (root == i || root == j) {
                root++;
            }
            
            int diff = distance_matrix[root][i] - distance_matrix[root][j];
            min_distance[i] = min(min_distance[i], 
                                 (distance_matrix[i][j] + diff) / 2);
            min_distance[j] = min(min_distance[j], 
                                 (distance_matrix[i][j] - diff) / 2);
        }
    }
}

void build_groups() {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (min_distance[i] + min_distance[j] == distance_matrix[i][j]) {
                int pi = find_parent(i);
                int pj = find_parent(j);
                if (pi != pj) {
                    parent[pi] = pj;
                }
            }
        }
    }
}

void calculate_group_distances() {
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int gi = find_parent(i);
            int gj = find_parent(j);
            
            if (gi == gj) continue;
            
            if (group_distance[gi][gj] != 0) continue;
            
            group_distance[gi][gj] = distance_matrix[i][j] - 
                                    min_distance[i] - min_distance[j];
            group_distance[gj][gi] = group_distance[gi][gj];
        }
    }
}

int calculate_total_weight() {
    int group_count = 0;
    vector<int> group_ids;
    
    for (int i = 1; i <= n; i++) {
        int gi = find_parent(i);
        if (find(group_ids.begin(), group_ids.end(), gi) == group_ids.end()) {
            group_ids.push_back(gi);
            group_count++;
        }
    }
    
    for (int i = 0; i < group_ids.size(); i++) {
        for (int j = i + 1; j < group_ids.size(); j++) {
            int gi = group_ids[i];
            int gj = group_ids[j];
            
            if (group_distance[gi][gj] == 0) continue;
            
            bool is_bridge = true;
            for (int k = 0; k < group_ids.size(); k++) {
                if (k == i || k == j) continue;
                
                int gk = group_ids[k];
                if (group_distance[gi][gk] == 0 || 
                    group_distance[gk][gj] == 0) continue;
                
                if (group_distance[gi][gj] == 
                    group_distance[gi][gk] + group_distance[gk][gj]) {
                    is_bridge = false;
                    break;
                }
            }
            
            if (is_bridge) {
                result += group_distance[gi][gj];
            } else {
                group_count--;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        result += min_distance[i];
    }
    
    return result;
}

int main() {
    cin >> n;
    distance_matrix.resize(n + 1, vector<int>(n + 1));
    min_distance.resize(n + 1, INT_MAX);
    parent.resize(n + 1);
    group_distance.resize(n + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> distance_matrix[i][j];
            distance_matrix[j][i] = distance_matrix[i][j];
        }
    }
    
    calculate_min_distances();
    build_groups();
    calculate_group_distances();
    
    cout << calculate_total_weight() << endl;
    return 0;
}

Fraction Sorting

Description:

Given two arrays a and b of length n, and q queries, each query asks for the c-th smallest value among all possible fractions a[i]/b[j]. The constraints are n ≤ 10^5.

Solution:

First, sort array a in ascending order and array b in descending order. Use binary search on the real number line to find the c-th smallest fraction. For each candidate value, count how many fractions are less than or equal to it. The counting process involves iterating through each element in b and performing a binary search on array a to find the maximum a[i] such that a[i] ≤ candidate * b[j].

Code:

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

const double EPS = 1e-12;
const int MAX_N = 100005;

int n, q;
vector<int> a, b;
vector<int> prefix_sum_a;

bool is_less_or_equal(double x, double y) {
    return (x < y + EPS || fabs(x - y) <= EPS);
}

int count_fractions_less_than(double x) {
    int count = 0;
    int last_index = n;
    
    for (int j = 0; j < n; j++) {
        int low = 0, high = last_index;
        int best = -1;
        
        while (low <= high) {
            int mid = (low + high) / 2;
            if (mid < n && is_less_equal(a[mid] * 1.0, x * b[j])) {
                best = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        
        if (best != -1) {
            count += best + 1;
            last_index = best;
        }
    }
    
    return count;
}

pair<int, int> find_fraction(int c) {
    double left = 0.0, right = 1e6;
    double candidate = EPS;
    
    while (left < right - EPS) {
        double mid = (left + right) / 2.0;
        int cnt = count_fractions_less_than(mid);
        
        if (cnt < c) {
            left = mid;
        } else {
            right = mid;
            candidate = mid;
        }
    }
    
    int numerator = 0, denominator = 1;
    
    for (int j = 0; j < n; j++) {
        int low = 0, high = n;
        
        while (low < high) {
            int mid = (low + high) / 2;
            if (mid < n && is_less_equal(a[mid] * 1.0, candidate * b[j])) {
                low = mid + 1;
                if (a[mid] * denominator > numerator * b[j]) {
                    numerator = a[mid];
                    denominator = b[j];
                }
            } else {
                high = mid;
            }
        }
    }
    
    int gcd_val = __gcd(numerator, denominator);
    return make_pair(numerator / gcd_val, denominator / gcd_val);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> q;
    a.resize(n);
    b.resize(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), greater<int>());
    
    prefix_sum_a.resize(n);
    prefix_sum_a[0] = a[0];
    for (int i = 1; i < n; i++) {
        prefix_sum_a[i] = prefix_sum_a[i-1] + a[i];
    }
    
    while (q--) {
        int c;
        cin >> c;
        
        auto fraction = find_fraction(c);
        cout << fraction.first << " " << fraction.second << "\n";
    }
    
    return 0;
}

Monster Hunting Strategy

Description:

Zayin faces n monsters in a row, with the i-th monster having health a_i. Zayin attacks first, killing all monsters with health ≤ 0. After each attack, surviving monsters deal 1 damage to Zayin. This cycle continues until all monsters are defeated. Zayin has three attack types:

1. Normal attack: Costs 0 energy, reduces a monster's health by 1
2. Sound Wave: Costs 1 energy, reduces a monster's health by 2
3. Thunder Strike: Costs 1 energy, reduces all monsters' health by 1

Zayin has m energy points. The task is to find the strategy that minimizes the total damage taken while defeating all monsters.

Solution:

The solution uses a greedy approach. First, sort the monsters' health in ascending order. The key insight is that for each monster, we can choose between using Thunder Strike to kill it (damaging subsequent monsters) or using Sound Wave to kill it (if health is odd, followed by a Thunder Strike). The optimal choice depends on which approach minimizes the total damage, calculated as: damage = (number of remaining monsters) × (damage dealt to current monster).

Code:

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

const int MAX_N = 100005;

int n, m;
vector<int> health;
int total_damage = 0;
int thunder_used = 0;
int sound_used = 0;

int calculate_damage_sum(int index) {
    int remaining = n - index;
    return remaining * (remaining + 1) / 2;
}

int main() {
    cin >> n >> m;
    health.resize(n);
    
    for (int i = 0; i < n; i++) {
        cin >> health[i];
    }
    
    sort(health.begin(), health.end());
    
    total_damage = -n;  // Initial damage calculation
    
    for (int i = 0; i < n; i++) {
        health[i] -= thunder_used;
        if (health[i] <= 0) continue;
        
        int remaining_energy = m - sound_used - thunder_used;
        int max_sound = min(remaining_energy, health[i]);
        int max_thunder = min(remaining_energy, health[i]);
        
        // Calculate damage for using Sound Wave
        int sound_damage = (max_sound) * (n - i) + 
                          (health[i] - max_sound) * (n - i);
        
        // Calculate damage for using Thunder Strike
        int thunder_damage = (max_thunder) * (n - i);
        
        if (sound_damage <= thunder_damage) {
            sound_used += max_sound;
            total_damage += max_sound * (n - i);
            health[i] -= max_sound;
        } else {
            thunder_used += max_thunder;
            total_damage += max_thunder * (n - i);
            health[i] -= max_thunder;
        }
        
        total_damage += health[i] * (n - i);
    }
    
    cout << total_damage << endl;
    return 0;
}

Maximum Manhattan Distance

Description:

A cafeteria is represented as an n×m grid of seats. There are already k people seated at positions (x_i, y_i). The task is to find a seat (not occupied) that maximizes the sum of Manhattan distances to all k people.

Solution:

The maximum Manhattan distance sum will occur near one of the four corners of the grid. Since corners might be occupied, we check positions near each corner. For each candidate position, we calculate the sum of Manhattan distances by separating the x and y components, sorting them, and using prefix sums for efficient calculation.

Code:

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

const int MAX_N = 400005;
const int MAX_M = 1005;

int n, m, k;
vector<int> x_coords, y_coords;
vector<int> prefix_x, prefix_y;
map<pair<int, int>, bool> occupied;
int max_distance = 0;

int find_position(vector<int>& arr, int value) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] <= value) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int calculate_distance_sum(int x, int y) {
    int idx_x = find_position(x_coords, x);
    int idx_y = find_position(y_coords, y);
    
    int sum_x = x * (2 * idx_x - k) - 2 * prefix_x[idx_x] + prefix_x[k];
    int sum_y = y * (2 * idx_y - k) - 2 * prefix_y[idx_y] + prefix_y[k];
    
    return sum_x + sum_y;
}

void check_corner_region(int start_x, int end_x, int start_y, int end_y) {
    for (int x = start_x; x <= end_x && x <= n; x++) {
        for (int y = start_y; y <= end_y && y <= m; y++) {
            if (occupied.count({x, y})) continue;
            
            int distance = calculate_distance_sum(x, y);
            if (distance > max_distance) {
                max_distance = distance;
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    x_coords.resize(k);
    y_coords.resize(k);
    
    for (int i = 0; i < k; i++) {
        cin >> x_coords[i] >> y_coords[i];
        occupied[{x_coords[i], y_coords[i]}] = true;
    }
    
    sort(x_coords.begin(), x_coords.end());
    sort(y_coords.begin(), y_coords.end());
    
    prefix_x.resize(k + 1);
    prefix_y.resize(k + 1);
    
    for (int i = 0; i < k; i++) {
        prefix_x[i + 1] = prefix_x[i] + x_coords[i];
        prefix_y[i + 1] = prefix_y[i] + y_coords[i];
    }
    
    // Check regions near each corner
    check_corner_region(1, min(n, MAX_M), 1, min(m, MAX_M));
    check_corner_region(1, min(n, MAX_M), max(1, m - MAX_M + 1), m);
    check_corner_region(max(1, n - MAX_M + 1), n, 1, min(m, MAX_M));
    check_corner_region(max(1, n - MAX_M + 1), n, max(1, m - MAX_M + 1), m);
    
    cout << max_distance << endl;
    return 0;
}