A - First ABC

The problem requires identifying the minimum 1-indexed position within a given string S where the characters 'A', 'B', and 'C' have all appeared at least once. The string length N is also provided.

To solve this, we can iterate through the string from its beginning. As we process each character, we need a way to track whether 'A', 'B', and 'C' have been encountered. A std::bitset of size 3 is an efficient data structure for this, where each bit corresponds to the presence of 'A', 'B', or 'C'. For example, bitset[0] for 'A', bitset[1] for 'B', and bitset[2] for 'C'.

During iteration, for each character S[i], we set the corresponding bit in our bitset. After marking the current character, we check if all three bits are set (bitset[0] && bitset[1] && bitset[2]). If they are, it means all required characters have been seen, and the current 1-indexed position (i + 1) is the answer. We can then print this position and terminate the program.

#include <iostream>
#include <string>
#include <bitset> // For efficient boolean flags

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

    int string_length;
    std::string input_string;
    std::cin >> string_length >> input_string;

    std::bitset<3> encountered_chars; // bitset[0] for 'A', bitset[1] for 'B', bitset[2] for 'C'

    for (int current_idx = 0; current_idx < string_length; ++current_idx) {
        // Convert character to 0-indexed offset (e.g., 'A' -> 0, 'B' -> 1)
        encountered_chars[input_string[current_idx] - 'A'] = 1;

        // Check if all three characters ('A', 'B', 'C') have been seen
        if (encountered_chars[0] && encountered_chars[1] && encountered_chars[2]) {
            std::cout << current_idx + 1 << std::endl; // Output 1-indexed position
            break; // Solution found, exit loop
        }
    }

    return 0;
}

B - Vacation Together

The problem asks us to find the longest sequence of consecutive days during which all N people are available for a vacation. We are given N people and D days. Each person's schedule is represented by a string of length D, where 'o' denotes availability and 'x' denotes being busy for a particular day.

A straightforward, but inefficient, approach would be to check every possible contiguous subsegment of days. For each subsegment, we would iterate through all N people and all days within that subsegment to ensure everyone is available. This leads to a complexity of roughly O(D^3 * N), which is too slow for typical constraints (e.g., D up to 100).

A more optimal strategy is to first determine which individual days are universally free. We can achieve this by initializing a boolean array, is_day_universally_free, of size D with all true value. Then, for each person, we iterate through their schedule. If a person is busy ('x') on day j, we mark is_day_universally_free[j] as false. After processing all N people, this boolean array will accurately reflect which days are truly free for everyone.

Once the is_day_universally_free array is populated, the problem reduces to finding the longest contiguous subsequence of true values within it. We can iterate through this array, maintaining a current_run_length counter. If is_day_universally_free[j] is true, we increment current_run_length. If it's false, we reset current_run_length to 0. We continuously update a maximum_run_length variable with the maximum value current_run_length has reached. This approach has a time complexity of O(N * D) for populating the boolean array and O(D) for finding the maximum consecutive days, resulting in an overall O(N * D) solution.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // For std::max

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

    int num_participants, total_days;
    std::cin >> num_participants >> total_days;

    // Boolean vector to track if a day is free for ALL participants
    // Initially assume all days are free for everyone
    std::vector<bool> everyone_free_on_day(total_days, true);

    for (int i = 0; i < num_participants; ++i) {
        std::string participant_schedule;
        std::cin >> participant_schedule;
        for (int j = 0; j < total_days; ++j) {
            if (participant_schedule[j] == 'x') {
                // If any participant is busy on day j, that day is not universally free
                everyone_free_on_day[j] = false;
            }
        }
    }

    int max_consecutive_free_days = 0;
    int current_consecutive_days_count = 0;

    // Iterate to find the longest sequence of 'true' days
    for (int j = 0; j < total_days; ++j) {
        if (everyone_free_on_day[j]) {
            current_consecutive_days_count++;
        } else {
            current_consecutive_days_count = 0; // Reset if a busy day is encountered
        }
        max_consecutive_free_days = std::max(max_consecutive_free_days, current_consecutive_days_count);
    }

    std::cout << max_consecutive_free_days << std::endl;

    return 0;
}

C - Find it!

This problem describes a functional graph where each node i has exactly one outgoing edge, pointing to node A[i]. The objective is to identify any cycle within this graph and output its length, followed by the nodes that constitute the cycle.

In a functional graph, starting a traversal from any node will eventually lead into a cycle. Since every node has an out-degree of exactly one, a path will necessarily revisit a node at some point. The first node encountered that has already been visited indicates entry into a cycle.

An elegant solution involves simulating the traversal. We can start from an arbitrary node (e.g., node 0 if 0-indexed, or node 1 if 1-indexed) and keep track of all nodes visited along the current path. As we move from current_node to next_node = A[current_node], we mark next_node as visited. The moment next_node is found to be already visited, we have identified the entry point into a cycle. This next_node is the first node of the cycle that we traversed.

To reconstruct the cycle, once the first repeated node k is found, we restart a traversal from k. We follow the edges A[j] and add each node to a list until we reach k again. The nodes collected in this second traversal (excluding the second k when it closes the loop) form the cycle.

It's common practice in competitive programming to convert 1-indexed problem inputs to 0-indexed internally for easier array and vector access, and then convert back to 1-indexed for output.

#include <iostream>
#include <vector>
#include <numeric> // Potentially for std::iota, though not used in final code structure
#include <algorithm> // Potentially for std::reverse, though not used in final code structure

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

    int num_vertices;
    std::cin >> num_vertices;

    std::vector<int> adjacency_list(num_vertices); // Stores the next node A[i] for each i
    for (int i = 0; i < num_vertices; ++i) {
        std::cin >> adjacency_list[i];
        adjacency_list[i]--; // Adjust input to be 0-indexed
    }

    std::vector<bool> visited_during_traversal(num_vertices, false);
    int current_exploration_node = 0; // Start traversal from node 0 (arbitrary choice)

    // Follow edges until a previously visited node is encountered
    // This node will be the first entry point into a cycle
    while (!visited_during_traversal[current_exploration_node]) {
        visited_during_traversal[current_exploration_node] = true;
        current_exploration_node = adjacency_list[current_exploration_node];
    }

    // 'current_exploration_node' now holds the identifier of a node within the cycle.
    // We now traverse from this node again to collect all cycle elements.
    std::vector<int> cycle_elements;
    int cycle_start_identifier = current_exploration_node;
    do {
        cycle_elements.push_back(current_exploration_node);
        current_exploration_node = adjacency_list[current_exploration_node];
    } while (current_exploration_node != cycle_start_identifier);

    std::cout << cycle_elements.size() << "\n";
    for (size_t i = 0; i < cycle_elements.size(); ++i) {
        std::cout << cycle_elements[i] + 1 << (i == cycle_elements.size() - 1 ? "" : " "); // Output 1-indexed
    }
    std::cout << "\n";

    return 0;
}

D - Grid Ice Floor

This problem involves navigating a grid composed of '.' (open cells) and '#' (walls). Starting from the cell at (1,1) (assuming 1-indexed coordinates), a person can slide in any of the four cardinal directions (up, down, left, right). A slide continues uninterrupted until a wall or the grid boundary is reached. All cells traversed during a slide, including the starting cell and the cell immediately before the wall/boundary, are considered "ice-floored." The objective is to determine the total number of unique cells that become ice-floored.

This scenario is well-suited for a Breadth-First Search (BFS) approach. Each state in our BFS queue represents a cell from which a new slide can be initiated. To manage the state, we need two distinct sets of visited flags:

1. slide_origins_processed: A boolean grid to mark cells that have already been added to the BFS queue as a starting point for new slides. This prevents redundant processing and ensures terminasion.
2. all_ice_floored: A boolean grid to mark every cell that has been touched or covered by any slide. This is the set we will count at the end.

BFS Aglorithm Steps:

1. Initialize a queue and add the starting cell (0,0) (corresponding to (1,1) in 1-indexed systems) to it.
2. Mark (0,0) in both slide_origins_processed and all_ice_floored as true.
3. While the queue is not empty: a. Dequeue a cell (r, c), which is the current slide origin. b. For each of the four cardinal directions (up, down, left, right): i. Simulate a slide starting from (r, c) in the chosen direction (dr, dc). ii. Continuously move (temp_r, temp_c) in the direction (dr, dc). For each new valid open cell (temp_r, temp_c) encountered during the slide, mark all_ice_floored[temp_r][temp_c] as true. iii. The slide stops when (temp_r, temp_c) would move out of bounds or into a wall cell. The cell (temp_r, temp_c) where the slide stopped (the last valid open cell) becomes the new potential slide_origin. iv. If this (temp_r, temp_c) (the end point of the slide) has not yet been marked in slide_origins_processed, mark it as true and enqueue it for future exploration.

After the BFS completes, iterate through the all_ice_floored grid and count all cells marked true. This total count is the answer.

#include <iostream>
#include <vector>
#include <string>
#include <queue> // For BFS
#include <utility> // For std::pair

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

    int num_rows, num_cols;
    std::cin >> num_rows >> num_cols;

    std::vector<std::string> grid_map(num_rows);
    for (int i = 0; i < num_rows; ++i) {
        std::cin >> grid_map[i];
    }

    // Direction vectors for (right, left, down, up)
    int row_deltas[] = {0, 0, 1, -1};
    int col_deltas[] = {1, -1, 0, 0};

    // Tracks cells from which a slide has originated and been processed by BFS
    std::vector<std::vector<bool>> slide_origin_processed(num_rows, std::vector<bool>(num_cols, false));
    // Tracks all unique cells that have been covered by any slide path
    std::vector<std::vector<bool>> all_ice_floored(num_rows, std::vector<bool>(num_cols, false));

    std::queue<std::pair<int, int>> bfs_queue;

    // Start BFS from (0,0) which corresponds to (1,1) in problem statement
    bfs_queue.push({0, 0});
    slide_origin_processed[0][0] = true;
    all_ice_floored[0][0] = true; // The initial cell is also ice-floored

    while (!bfs_queue.empty()) {
        std::pair<int, int> current_coords = bfs_queue.front();
        bfs_queue.pop();
        int r_curr = current_coords.first;
        int c_curr = current_coords.second;

        for (int i = 0; i < 4; ++i) { // Explore each of the four cardinal directions
            int r_slide_end = r_curr;
            int c_slide_end = c_curr;

            // Simulate the slide in the current direction
            while (true) {
                int r_next = r_slide_end + row_deltas[i];
                int c_next = c_slide_end + col_deltas[i];

                // Check if the next cell is within grid boundaries and is an open path ('.')
                if (r_next >= 0 && r_next < num_rows && c_next >= 0 && c_next < num_cols && grid_map[r_next][c_next] == '.') {
                    r_slide_end = r_next;
                    c_slide_end = c_next;
                    all_ice_floored[r_slide_end][c_slide_end] = true; // Mark this cell as ice-floored
                } else {
                    // Hit a wall or went out of bounds, slide ends at (r_slide_end, c_slide_end)
                    break;
                }
            }

            // The cell (r_slide_end, c_slide_end) is where the current slide stopped.
            // If this cell has not yet been processed as a slide origin, add it to the queue.
            if (!slide_origin_processed[r_slide_end][c_slide_end]) {
                slide_origin_processed[r_slide_end][c_slide_end] = true;
                bfs_queue.push({r_slide_end, c_slide_end});
            }
        }
    }

    int total_unique_ice_floored_cells = 0;
    for (int i = 0; i < num_rows; ++i) {
        for (int j = 0; j < num_cols; ++j) {
            if (all_ice_floored[i][j]) {
                total_unique_ice_floored_cells++;
            }
        }
    }

    std::cout << total_unique_ice_floored_cells << std::endl;

    return 0;
}