A - First ABC

Solution

We can track the first appearence of each character using boolean flags. By iterating through the string, we can determine the earliest position where all three required characters have been encountered.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int length;
    string input;
    cin >> length >> input;
    
    bool foundA = false, foundB = false, foundC = false;
    int position = 0;
    
    for (int i = 0; i < length; i++) {
        char current = input[i];
        if (current == 'A') foundA = true;
        if (current == 'B') foundB = true;
        if (current == 'C') foundC = true;
        
        if (foundA && foundB && foundC) {
            position = i + 1;
            break;
        }
    }
    
    cout << position << endl;
    return 0;
}

B - Vacation To gether

Solution

We'll scan through each day and track the longest consecutive period where everyone is available. By maintaining a record of the last day some one was unavailable, we can calculate the maximum vacation duration.

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int people, days;
    cin >> people >> days;
    
    string schedule[people + 1];
    for (int i = 1; i <= people; i++) {
        cin >> schedule[i];
    }
    
    int lastUnavailable = -1;
    int maxVacation = 0;
    
    for (int day = 0; day < days; day++) {
        bool everyoneAvailable = true;
        
        for (int person = 1; person <= people; person++) {
            if (schedule[person][day] == 'x') {
                everyoneAvailable = false;
                break;
            }
        }
        
        if (everyoneAvailable) {
            maxVacation = max(maxVacation, day - lastUnavailable);
        } else {
            lastUnavailable = day;
        }
    }
    
    cout << maxVacation << endl;
    return 0;
}

C - Find it!

Solution

Instead of using DFS, we can detect cycles in the directed graph by following pointers and coloring nodes. For each unvisited node, we'll traverse following the edges until we either find a cycle or reach a previously visited node with a different color.

1. Start at an unvisited node
2. Follow the pointer to the next node
3. Color each visited node with the current color
4. If we encounter a node with a different color, this path cannot form a cycle
5. If we return to a node with the same color, we've found a cycle

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int nodes;
    cin >> nodes;
    
    int nextNode[nodes + 1];
    int color[nodes + 1] = {0};
    int currentColor = 0;
    
    for (int i = 1; i <= nodes; i++) {
        cin >> nextNode[i];
    }
    
    vector<int> cycle;
    
    for (int i = 1; i <= nodes; i++) {
        if (color[i] == 0) {
            currentColor++;
            cycle.clear();
            int current = i;
            bool hasCycle = true;
            
            do {
                color[current] = currentColor;
                cycle.push_back(current);
                
                if (color[nextNode[current]] != 0 && color[nextNode[current]] != currentColor) {
                    hasCycle = false;
                    break;
                }
                
                current = nextNode[current];
            } while (color[current] == 0);
            
            reverse(cycle.begin(), cycle.end());
            while (cycle.back() != current) cycle.pop_back();
            reverse(cycle.begin(), cycle.end());
            
            if (hasCycle) {
                cout << cycle.size() << endl;
                for (int node : cycle) cout << node << " ";
                cout << endl;
                return 0;
            }
        }
    }
    
    return 0;
}

D - Grid Ice Floor

Solution

We'll use BFS to explore the grid. The movement rule is special: we can slide in one direction until we hit a wall or boundary. We mark cells as visited only when we stop sliding, not during the slide.

Code

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    int rows, cols;
    cin >> rows >> cols;
    
    string grid[rows];
    for (int i = 0; i < rows; i++) {
        cin >> grid[i];
    }
    
    bool visited[rows][cols] = {false};
    queue<pair<int, int>> exploration;
    exploration.push({0, 0});
    visited[0][0] = true;
    
    int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    while (!exploration.empty()) {
        int x = exploration.front().first;
        int y = exploration.front().second;
        exploration.pop();
        
        for (int dir = 0; dir < 4; dir++) {
            int newX = x, newY = y;
            
            while (true) {
                int nextX = newX + directions[dir][0];
                int nextY = newY + directions[dir][1];
                
                if (nextX < 0 || nextX >= rows || nextY < 0 || nextY >= cols || grid[nextX][nextY] == '#') {
                    if (!visited[newX][newY]) {
                        exploration.push({newX, newY});
                        visited[newX][newY] = true;
                    }
                    break;
                }
                
                visited[newX][newY] = true;
                newX = nextX;
                newY = nextY;
            }
        }
    }
    
    int reachable = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (visited[i][j]) reachable++;
        }
    }
    
    cout << reachable << endl;
    return 0;
}

E - Defect-free Squares

Solution

We'll use dynamic programming to count all defect-free squares. Let dp[i][j] represent the size of the largest square with bottom-right corner at (i, j). The transition depends on the three neighboring squares.

For each cell (i, j):

• If it's a defect, dp[i][j] = 0
• Otherwise, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

The total number of defect-free squares is the sum of all dp[i][j] values.

Code

#include <iostream>
using namespace std;

int main() {
    int rows, cols, defects;
    cin >> rows >> cols >> defects;
    
    bool hasDefect[rows + 1][cols + 1] = {false};
    for (int i = 0; i < defects; i++) {
        int x, y;
        cin >> x >> y;
        hasDefect[x][y] = true;
    }
    
    long long dp[rows + 1][cols + 1] = {0};
    long long totalSquares = 0;
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (hasDefect[i][j]) {
                continue;
            }
            
            dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            totalSquares += dp[i][j];
        }
    }
    
    cout << totalSquares << endl;
    return 0;
}