RC-u1 Heat Wave

Problem Summary: Given daily maximum temperatures and the day of the week for the first day, count how many days have temperatures ≥ 35°C. Days falling on weekends (Saturday and Sunday) should be counted separately.

Solution: Iterate through the temperature data while tracking the current weekday. For each temperature ≥ 35, increment the appropriate counter based on whether it's a weekend. Use modular arithmetic to cycle through weekdays.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int days, startDay;
    cin >> days >> startDay;

    int weekendCount = 0, weekdayCount = 0;
    for (int i = 0; i < days; ++i) {
        int temp;
        cin >> temp;

        if (temp >= 35) {
            if (startDay == 6 || startDay == 7)
                weekendCount++;
            else
                weekdayCount++;
        }

        startDay++;
        if (startDay > 7) startDay = 1;
    }

    cout << weekdayCount << ' ' << weekendCount << '\n';
    return 0;
}

RC-u2 Qualification Check

Problem Summary: Calculate final scores for 20 contestants based on their performance across multiple rounds. Each round provides a rank and a penalty score. Rankings determine a base score using a predefined mapping table.

Solution: Use a lookup table to convert rankings to base points, then accumulate the base points and penalties for each contestant across all rounds.

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

int getPoints(int rank) {
    if (rank == 1) return 12;
    if (rank == 2) return 9;
    if (rank == 3) return 7;
    if (rank == 4) return 5;
    if (rank == 5) return 4;
    if (rank <= 7) return 3;
    if (rank <= 10) return 2;
    if (rank <= 15) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int rounds;
    cin >> rounds;

    vector<int> total(20, 0);
    for (int i = 0; i < rounds; ++i) {
        for (int j = 0; j < 20; ++j) {
            int ranking, penalty;
            cin >> ranking >> penalty;
            total[j] += getPoints(ranking) + penalty;
        }
    }

    for (int i = 0; i < 20; ++i)
        cout << i + 1 << ' ' << total[i] << '\n';

    return 0;
}

RC-u3 Heater and Capybara

Problem Summary: On an n×m grid, there are heaters ('m'), cold-water capybaras ('c'), and regular capybaras ('w'). A regular capybaar is hidden if all 8 adjacent cells contain neither a heater nor a cold-water cpaybara. Find all valid hiding positions (empty cells adjacent to a hidden capybara).

Solution: First, mark cells covered by heaters and cold-water capybaras. For each regular capybara, check if all 8 adjacent cells are unmarked. If so, collect all adjacent empty cells that aren't near cold-water capybaras.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int rows, cols;
    cin >> rows >> cols;

    vector<string> grid(rows);
    for (auto &line : grid)
        cin >> line;

    vector<vector<int>> mark(rows, vector<int>(cols, 0));
    const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
    const int dy[] = {1, 0, -1, 1, 0, -1, 1, -1};

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'm') {
                mark[i][j] = 1;
                for (int k = 0; k < 8; ++k) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < rows && nj >= 0 && nj < cols)
                        mark[ni][nj] = 1;
                }
            }
        }
    }

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'c') {
                mark[i][j] = 2;
                for (int k = 0; k < 8; ++k) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < rows && nj >= 0 && nj < cols)
                        mark[ni][nj] = 2;
                }
            }
        }
    }

    vector<pair<int, int>> result;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (grid[i][j] == 'w' && mark[i][j] == 0) {
                for (int k = 0; k < 8; ++k) {
                    int ni = i + dx[k], nj = j + dy[k];
                    if (ni >= 0 && ni < rows && nj >= 0 && nj < cols &&
                        grid[ni][nj] == '.' && mark[ni][nj] != 2)
                        result.emplace_back(ni + 1, nj + 1);
                }
            }
        }
    }

    sort(result.begin(), result.end());

    if (result.empty())
        cout << "Too cold!\n";
    else
        for (auto &[x, y] : result)
            cout << x << ' ' << y << '\n';

    return 0;
}

RC-u4 Octopus Graph Detection

Problem Summary: Determine if an undirected graph is an "octopus graph" (exactly one cycle with trees attached to it) and output the cycle length if valid.

Solution: Use DFS with timestamps to detect cycles. Count how many back edges exist in each connected component. A valid octopus graph has exactly one cycle and at least 3 vertices in the cycle.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;

    while (testCases--) {
        int vertices, edges;
        cin >> vertices >> edges;

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

        int cycleCount = 0, maxCycleLen = 0;
        vector<int> visited(vertices + 1, 0);

        function<void(int, int, int)> dfs = [&](int node, int parent, int depth) {
            visited[node] = depth;
            for (int neighbor : adj[node]) {
                if (neighbor == parent) continue;
                if (visited[neighbor]) {
                    maxCycleLen = max(maxCycleLen, depth - visited[neighbor] + 1);
                } else {
                    dfs(neighbor, node, depth + 1);
                }
            }
        };

        for (int i = 1; i <= vertices; ++i) {
            int backEdges = 0;
            if (!visited[i]) {
                dfs(i, 0, 1);
                cycleCount += (backEdges / 2 == 1);
            }
        }

        if (cycleCount == 1 && vertices > 2)
            cout << "Yes " << maxCycleLen << '\n';
        else
            cout << "No " << cycleCount << '\n';
    }

    return 0;
}

RC-u5 Work Scheduling

Problem Summary: Given n tasks each with a duration, deadline, and profit, find the maximum profit achievable by scheduling tasks before their deadlines. Each task takes one time unit of work capacity.

Solution: Sort tasks by deadline, then apply 0-1 knapsack dynamic programming. The DP state dp[t] represents the maximum profit achievable using exactly t time units.

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

struct Task {
    int duration;
    int deadline;
    int profit;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int testCases;
    cin >> testCases;

    while (testCases--) {
        int taskCount;
        cin >> taskCount;

        vector<Task> tasks(taskCount);
        for (auto &task : tasks)
            cin >> task.duration >> task.deadline >> task.profit;

        sort(tasks.begin(), tasks.end(), [](const Task &a, const Task &b) {
            return a.deadline < b.deadline;
        });

        const int MAX_TIME = 5000;
        const long long NEG_INF = INT_MIN;
        vector<long long> dp(MAX_TIME + 1, NEG_INF);
        dp[0] = 0;

        for (const auto &task : tasks) {
            for (int t = task.deadline; t >= task.duration; --t)
                dp[t] = max(dp[t], dp[t - task.duration] + task.profit);
        }

        long long answer = 0;
        for (int t = 0; t <= MAX_TIME; ++t)
            answer = max(answer, dp[t]);

        cout << answer << '\n';
    }

    return 0;
}

Key Techniques Summary