Problem A: Determining the Winner

Given three relational operators between three individuals, we need to determine the intermediate winner. Instead of enumerating all 8 combinations manually, we can assign a victory score to each individual based on the given comparisons. The winner is the one who achieves exactly one victory.

#include <iostream>
#include <string>

using namespace std;

int main() {
    char rel_ab, rel_ac, rel_bc;
    cin >> rel_ab >> rel_ac >> rel_bc;
    
    int victories[3] = {0, 0, 0};
    victories[0] += (rel_ab == '>') + (rel_ac == '>'); // A beats B and C?
    victories[1] += (rel_ab == '<') + (rel_bc == '>'); // B beats A and C?
    victories[2] += (rel_ac == '<') + (rel_bc == '<'); // C beats A and B?
    
    string names = "ABC";
    for (int i = 0; i < 3; ++i) {
        if (victories[i] == 1) {
            cout << names[i] << endl;
            break;
        }
    }
    return 0;
}

Problem B: First Occurrence Detection

We process a sequence of family member identifiers and genders, outputting "Yes" only for the first time a male appears for a specific identifier. This can be efficiently handled using a hash set to track encountered male identifiers, ensuring constant-time lookups.

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    int total_fam, queries;
    cin >> total_fam >> queries;
    unordered_set<int> encountered_males;
    
    while (queries--) {
        int idx; char gender;
        cin >> idx >> gender;
        if (gender == 'M' && encountered_males.find(idx) == encountered_males.end()) {
            encountered_males.insert(idx);
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

Problem C: Minimum Cost Graph Isomorphism

To find the minimum transformation cost making graph G isomorphic to H, we iterate over all permutations of G's vertices. For each permutation, we compare the adjacency matrices and accumulate the edge costs where edges mismatch between the permuted G and H. The minimum accumulated cost across all permutations is the answer.

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<bool>> graph_g(n, vector<bool>(n, false));
    vector<vector<bool>> graph_h(n, vector<bool>(n, false));
    
    auto read_graph = [&](vector<vector<bool>>& mat) {
        int m; cin >> m;
        for (int i = 0; i < m; ++i) {
            int u, v; cin >> u >> v;
            mat[u-1][v-1] = mat[v-1][u-1] = true;
        }
    };
    read_graph(graph_g);
    read_graph(graph_h);
    
    vector<vector<int>> cost(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            cin >> cost[i][j];
            cost[j][i] = cost[i][j];
        }
    }
    
    vector<int> perm(n);
    for (int i = 0; i < n; ++i) perm[i] = i;
    
    int min_cost = 1e9;
    do {
        int current_cost = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (graph_g[perm[i]][perm[j]] != graph_h[i][j]) {
                    current_cost += cost[i][j];
                }
            }
        }
        min_cost = min(min_cost, current_cost);
    } while (next_permutation(perm.begin(), perm.end()));
    
    cout << min_cost << endl;
    return 0;
}

Problem D: Population Range Queries

We are given village coordinates and populations, and need to answer queries for the total population within a coordinate range. By sorting villages by coordinates and computing a prefix sum of populations, we can answer each query in logarithmic time using binary search to find the inclusive boundaries.

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

using namespace std;

struct Settlement {
    int coordinate;
    int population;
};

int main() {
    int n;
    cin >> n;
    vector<Settlement> towns(n);
    for (int i = 0; i < n; ++i) cin >> towns[i].coordinate;
    for (int i = 0; i < n; ++i) cin >> towns[i].population;
    
    sort(towns.begin(), towns.end(), [](const Settlement& a, const Settlement& b) {
        return a.coordinate < b.coordinate;
    });
    
    vector<long long> prefix_pop(n + 1, 0);
    vector<int> sorted_coords(n);
    for (int i = 0; i < n; ++i) {
        sorted_coords[i] = towns[i].coordinate;
        prefix_pop[i + 1] = prefix_pop[i] + towns[i].population;
    }
    
    int q;
    cin >> q;
    while (q--) {
        int left, right;
        cin >> left >> right;
        auto it_l = lower_bound(sorted_coords.begin(), sorted_coords.end(), left);
        auto it_r = upper_bound(sorted_coords.begin(), sorted_coords.end(), right);
        int start_idx = it_l - sorted_coords.begin();
        int end_idx = it_r - sorted_coords.begin();
        cout << prefix_pop[end_idx] - prefix_pop[start_idx] << "\n";
    }
    return 0;
}

Problem E: Cumulative Subarray Distinct Sum

The problem asks for the sum of the number of distinct elements in all possible subarrays. We can solve this using dynamic programming. Let subarray_sum represent the sum of distinct counts for all subarrays ending at the current index. For a new element, if its previous occurrence was at prev_pos, only subarrays starting after prev_pos will gain a +1 distinct count. Thus, subarray_sum += i - prev_pos. The final answer is the accumulation of subarray_sum across all indices.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int num_elements;
    cin >> num_elements;
    vector<int> values(num_elements);
    for (int i = 0; i < num_elements; ++i) cin >> values[i];
    
    unordered_map<int, int> last_seen;
    long long subarray_sum = 0;
    long long total_sum = 0;
    
    for (int i = 0; i < num_elements; ++i) {
        int prev_pos = last_seen.count(values[i]) ? last_seen[values[i]] : -1;
        subarray_sum += (i - prev_pos);
        total_sum += subarray_sum;
        last_seen[values[i]] = i;
    }
    
    cout << total_sum << endl;
    return 0;
}