Overview of Selected Problems

The following section outlines the algorithmic approaches and C++ implementations for specific tasks encountered during the undergraduate category of the 2024 competition. Each problem addresses distinct computational challenges ranging from string manipulation to graph optimization.

Task 1: Character Compsoition Validation

Approach:

The objective requires simulating a validation process on input strings. The core logic envolves identifying valid alphanumeric sequences, calculating their lengths, and assigning scores based on character diversity (presence of digits, lowercase letters, and uppercase letters). During execution, standard stream extraction methods were preferred over line-based input to handle token separation reliably.

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

using namespace std;

bool validate_character(char c) {
    return (c >= '0' && c <= '9') || 
           (c >= 'a' && c <= 'z') || 
           (c >= 'A' && c <= 'Z');
}

int count_digits(const string& segment) {
    int cnt = 0;
    for (char c : segment) {
        if (isdigit(c)) cnt++;
    }
    return cnt;
}

int count_lower(const string& segment) {
    int cnt = 0;
    for (char c : segment) {
        if (islower(c)) cnt++;
    }
    return cnt;
}

int count_upper(const string& segment) {
    int cnt = 0;
    for (char c : segment) {
        if (isupper(c)) cnt++;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<string> tokens;
    string buffer;
    while (cin >> buffer) {
        for (size_t i = 0; i < buffer.size(); ) {
            if (validate_character(buffer[i])) {
                size_t start = i;
                while (i < buffer.size() && validate_character(buffer[i])) {
                    i++;
                }
                tokens.emplace_back(buffer.substr(start, i - start));
            } else {
                i++;
            }
        }
    }

    int total_score = 0;
    int total_chars = 0;

    for (const auto& token : tokens) {
        total_chars += token.length();
        int d = count_digits(token);
        int l = count_lower(token);
        int u = count_upper(token);

        if (d > 0 && l > 0 && u > 0) {
            total_score += 5;
        } else if (d > 0 && (l > 0 || u > 0)) {
            total_score += 3;
        } else if (l > 0 && u > 0) {
            total_score += 1;
        }
    }

    cout << total_score << '\n' << total_chars << ' ' << tokens.size() << '\n';
    return 0;
}

Task 2: Tournament Scoring Simulation

Approach:

This task models a scoring system for 30 competing teams. Points are awarded based on rank positions (e.g., 1st gets 25, 2nd gets 21, etc.). Only teams that actively participated in at least one round should appear in the final output. The results must be sorted primarily by total points (descending) and secondarily by team ID (ascending).

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

using namespace std;

struct Team {
    int id;
    int score;
};

int get_points(int rank) {
    if (rank == 1) return 25;
    if (rank == 2) return 21;
    if (rank == 3) return 18;
    return 20 - rank;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int rounds;
    if (!(cin >> rounds)) return 0;

    vector<Team> teams(31);
    set<int> participants;

    for (int i = 1; i <= 30; i++) {
        teams[i] = {i, 0};
    }

    while (rounds--) {
        for (int k = 1; k <= 20; k++) {
            int r, p;
            cin >> r >> p;
            teams[r].score += get_points(p);
            participants.insert(r);
        }
    }

    sort(teams.begin() + 1, teams.end(), [](const Team& a, const Team& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.id < b.id;
    });

    for (int i = 1; i <= 30; i++) {
        if (participants.count(teams[i].id)) {
            cout << teams[i].id << ' ' << teams[i].score << '\n';
        }
    }

    return 0;
}

Task 3: Balanced Subset Partition

Approach:

The goal is to divide a sequence into two subsets such that the sum of squares of elements in both subsets is equal. Given the combinatorial explosion of permutations, a bidirectional search strategy is employed. The space is split into two halves. We record the difference between subset sums ($\sum S_1^2 - \sum S_2^2$) for the first half and match it with corresponding differences from the second half. Additionally, we verify that the combined subsets cover exactly half the total number of elements each.

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

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; i++) cin >> nums[i];

    // Generate all permutations
    vector<ll> perms;
    vector<int> perm_indices(n);
    vector<bool :="" actual="" assume="" auto="" below="" brevity="" conceptually.="" correct="" current="" current.pop_back="" current.push_back="" demonstrates="" diff_map="" false="" focus="" for="" full="" generate="[&](auto&" generation="" half_count="perms.size()" halves="" handles="" hash_val="0;" i="1;" idx="" if="" implementation="" in="" indices="" int="" is="" j="0;" ll="" logic="" map="" mask="1;" matching="" n="" note:="" o="" omitted="" on="" perms.push_back="" permutation="" practice="" representation="" return="" self="" simplified="" since="" split="" splits="" sq_sum_a="0," sq_sum_b="0;" store="" stores="" structure="" temp="" the="" to="" true="" values="" vector="" visited="" void="" we="" x="">> j) & 1) sq_sum_a += perms[j] * perms[j];
            else sq_sum_b += perms[j] * perms[j];
        }
        diff_map[sq_sum_a - sq_sum_b].push_back(mask);
    }

    bool found = false;
    for (int mask = 1; mask < (1 << half_count); mask++) {
        ll sq_sum_a = 0, sq_sum_b = 0;
        int start_idx = half_count;
        // Iterating second half logic placeholder
        // Matching condition: diff_first == -diff_second
        ll target_diff = -(sq_sum_a - sq_sum_b); 

        if (diff_map.count(target_diff)) {
            for (auto existing_mask : diff_map[target_diff]) {
                if (__builtin_popcount(mask) + __builtin_popcount(existing_mask) == half_count) {
                    found = true;
                    break;
                }
            }
        }
        if(found) break;
    }

    return 0;
}</bool>

Task 4: Minimum Heat Pathfinding

Approach:

We employ Dijkstra's algorithm to find the shortest path between a source and destination node. However, this variant introduces a secondary constraint: minimizing the maximum "heat" value of any intermediate node along the chosen path. We maintain an auxiliary distance array tracking this peak heat level, updating it whenever a path with equal traversal distance offers a lower maximum node weight.

#include <iostream>
#include <vector>
#include <queue>
#include &limits.h>

using namespace std;
const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, start_node, end_node;
    cin >> n >> m >> start_node >> end_node;

    vector<int> node_heat(n + 1);
    for (int i = 1; i <= n; i++) cin >> node_heat[i];

    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> min_dist(n + 1, INF);
    vector<int> max_heat_path(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    min_dist[start_node] = 0;
    max_heat_path[start_node] = 0;
    pq.push({0, start_node});

    while (!pq.empty()) {
        auto [dist, u] = pq.top();
        pq.pop();

        if (dist > min_dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (min_dist[v] > min_dist[u] + weight) {
                min_dist[v] = min_dist[u] + weight;
                max_heat_path[v] = max(max_heat_path[u], node_heat[v]);
                pq.push({min_dist[v], v});
            } else if (min_dist[v] == min_dist[u] + weight) {
                int current_max_heat = max(max_heat_path[u], node_heat[v]);
                if (current_max_heat < max_heat_path[v]) {
                    max_heat_path[v] = current_max_heat;
                    pq.push({min_dist[v], v});
                }
            }
        }
    }

    if (min_dist[end_node] == INF) {
        cout << "Impossible\n";
    } else {
        cout << min_dist[end_node] << ' ' << max_heat_path[end_node] << '\n';
    }

    return 0;
}

Task 5: Subgrid Removal Optimization

Approach:

This problem involves a grid manipulation game where rectangular subregions are removed to maximize cumulative gain. A greedy strategy is used combined with prefix sums and dynamic programming to identify the optimal subrectangle at each step. Special atttention is required for the coordinate mapping (rows vs. columns inversion) and boundary conditions during element shifting after removal.

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

using namespace std;
const int NEG_INF = -500000;

struct RectResult {
    int score;
    int r_start, c_start;
    int r_end, c_end;
};

RectResult MinRes(RectResult a, RectResult b) {
    if (a.score != b.score) return a.score > b.score ? b : a;
    // Tie-breaking logic preserved
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<vector<int>> grid(n + 1, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[j][i];
            if (grid[j][i] == 0) grid[j][i] = NEG_INF;
        }
    }

    int total_gain = 0;

    while (true) {
        RectResult best{NEG_INF, 0, 0, 0, 0};
        
        // Scan all subgrids
        for (int r1 = 1; r1 <= n; r1++) {
            for (int r2 = r1; r2 <= n; r2++) {
                vector<int> row_prefix(n + 1, 0);
                // Calculate row sums between r1 and r2
                for (int k = 1; k <= n; k++) {
                     for(int r=r1; r<=r2; r++) row_prefix[k] += grid[r][k];
                }

                // DP to find max subsegment
                vector<vector<int>> dp(n + 1, vector<int>(2, -1e9));
                for (int k = 1; k <= n; k++) {
                    int current = row_prefix[k];
                    dp[k][0] = current;
                    dp[k][1] = k;
                    if (k > 1 && dp[k-1][0] + current > dp[k][0]) {
                        dp[k][0] = dp[k-1][0] + current;
                        dp[k][1] = dp[k-1][1];
                    }
                    
                    RectResult curr_res = {dp[k][0], r1, dp[k][1], r2, k};
                    best = MinRes(best, curr_res);
                }
            }
        }

        if (best.score <= 0) break;

        total_gain += best.score;
        cout << '(' << best.r_start << ", " << best.c_start << ") (" << best.r_end << ", " << best.c_end << ") " << best.score << '\n';

        // Remove cells and shift remaining values
        for (int r = best.r_start; r <= best.r_end; r++) {
            int shift_idx = -1e5;
            for (int c = best.c_start; c <= best.c_end; c++) {
                grid[r][c] = shift_idx;
            }
            
            // Shift right
            int k = best.c_end + 1;
            while(k <= n && grid[r][k] == shift_idx) k++;
            // Compact logic applied to fill holes
            int write_ptr = best.c_start - 1;
            for (int c = 1; c <= n; c++) {
                 if (grid[r][c] != shift_idx) {
                     write_ptr++;
                     grid[r][write_ptr] = grid[r][c];
                 }
            }
            for(int c=write_ptr+1; c<=n; c++) grid[r][c] = NEG_INF;
        }
    }

    cout << total_gain << '\n';
    return 0;
}