Identify isolated groups of zeros in a grid that do not border grid edges. Traverse connected components using BFS while tracking boundary collisions.

#include <vector>
#include <queue>
#include <iostream>

int main() {
    int rows, cols;
    std::cin >> cols >> rows;
    
    std::vector grid(rows, std::vector<int>(cols));
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            std::cin >> grid[r][c];
        }
    }

    const int dr[] = {0, 0, 1, -1};
    const int dc[] = {1, -1, 0, 0};
    int total = 0;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c]) continue;
            
            bool interior = true;
            int cluster_size = 0;
            std::queue<std::pair<int, int>> q;
            q.push({r, c});
            grid[r][c] = 1;

            while (!q.empty()) {
                auto [cur_r, cur_c] = q.front();
                q.pop();
                cluster_size++;

                for (int d = 0; d < 4; d++) {
                    int nr = cur_r + dr[d];
                    int nc = cur_c + dc[d];
                    
                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) {
                        interior = false;
                        continue;
                    }
                    if (!grid[nr][nc]) {
                        grid[nr][nc] = 1;
                        q.push({nr, nc});
                    }
                }
            }

            if (interior) total += cluster_size;
        }
    }

    std::cout << total << "\n";
    return 0;
}

Assistant Selection

Form valid teams by selecting one member from each ctaegory where no overlapping skills exist between members.

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

int main() {
    int n;
    std::cin >> n;
    
    std::vector<std::vector<std::vector<int>>> categories(3);
    for (int i = 0; i < n; i++) {
        int id, type, s1, s2, s3, s4;
        std::cin >> id >> type >> s1 >> s2 >> s3 >> s4;
        categories[type-1].push_back({id, s1, s2, s3, s4});
    }

    int skill_counts[101] = {};
    std::vector<std::vector<int>> valid_teams;
    
    for (auto& memberA : categories[0]) {
        for (int i = 1; i <= 4; i++) skill_counts[memberA[i]]++;
        
        for (auto& memberB : categories[1]) {
            bool valid = true;
            for (int i = 1; i <= 4; i++) {
                if (skill_counts[memberB[i]] && memberB[i]) valid = false;
                skill_counts[memberB[i]]++;
            }
            
            if (valid) {
                for (auto& memberC : categories[2]) {
                    bool team_valid = true;
                    for (int i = 1; i <= 4; i++) {
                        if (skill_counts[memberC[i]] && memberC[i]) {
                            team_valid = false;
                            break;
                        }
                    }
                    if (team_valid) {
                        valid_teams.push_back({memberA[0], memberB[0], memberC[0]});
                    }
                }
            }
            
            for (int i = 1; i <= 4; i++) skill_counts[memberB[i]]--;
        }
        
        for (int i = 1; i <= 4; i++) skill_counts[memberA[i]]--;
    }

    if (valid_teams.empty()) {
        std::cout << "-1\n";
    } else {
        std::sort(valid_teams.begin(), valid_teams.end());
        for (auto& team : valid_teams) {
            std::cout << team[0] << " " << team[1] << " " << team[2] << "\n";
        }
    }
    
    return 0;
}

Energy Resonence

Detect shortest symmetric subarrays with zero sum using prefix tracking and dynamic offset calculation.

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

int main() {
    int n;
    std::cin >> n;
    
    std::vector<int> sequence(n);
    for (int i = 0; i < n; i++) {
        std::cin >> sequence[i];
    }

    std::map<long, int> prefix_index;
    prefix_index[0] = -1;
    int min_length = n, count = 0;
    std::vector<int> offsets(n, 0);
    long cumulative = 0;

    for (int i = 0; i < n; i++) {
        cumulative += sequence[i];
        
        if (prefix_index.find(cumulative) != prefix_index.end()) {
            int prev = prefix_index[cumulative];
            offsets[i] = i - prev;
            
            if (i - offsets[i] >= 0 && offsets[i - offsets[i]]) {
                int total_len = offsets[i] + offsets[i - offsets[i]];
                
                if (total_len < min_length) {
                    min_length = total_len;
                    count = 1;
                } else if (total_len == min_length) {
                    count++;
                }
            }
        }
        prefix_index[cumulative] = i;
    }

    if (!count) {
        std::cout << "-1 -1\n";
    } else {
        std::cout << min_length << " " << count << "\n";
    }
    
    return 0;
}