## Intuition The problem is a game theory problem involving optimal moves on a chessboard. The key insight is to determine which player has a winning strategy based on the initial configuration of the board and the positions of the special tiles. The castle can only move right or down, and the game ends when a player moves the castle to a special tile or cannot move the castle further. The challenge is to determine which player can force a win given both players play optimally. ## Approach 1. **Game State Representation**: The game can be represented as a grid where each cell is a state. The state is winning if the player whose turn it is can move to a special tile or force the opponent into a losing position. 2. **Winning and Losing Positions**: - A position is winning if there is a direct move to a special tile. - A position is losing if every move leads to a winning position for the opponent. 3. **Optimal Strategy**: - Start from the initial position (1,1). - Check if there is a direct move to any special tile. If yes, Chaneka wins immediately. - If not, simulate the game using a dynamic programming approach to determine if there exists a sequence of moves that leads to a win for Chaneka. 4. **Implementation**: - Use two sets to track special tiles in each row and column. - Use two pointers to efficiently determine if a move to a special tile is possible. - Determine the winner by checking if the initial position is a winning position. ## Complexity - **Time Complexity**: O(K log K), where K is the number of special tiles. This arises from sorting the special tiles and using binary search to determine possible moves. - **Space Complexity**: O(K), to store the positions of special tiles. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; vector> specials(K); for (int i = 0; i < K; ++i) { cin >> specials[i].first >> specials[i].second; } // Sort the special tiles by rows and columns sort(specials.begin(), specials.end()); // Check if there is a direct move to a special tile from (1,1) for (const auto& [x, y] : specials) { if (x == 1 || y == 1) { cout << "Chaneka" << endl; return 0; } } // If no direct move to a special tile, check the parity of the board size // If (N + M) is odd, Chaneka wins, otherwise Bhinneka wins if ((N + M) % 2 == 1) { cout << "Chaneka" << endl; } else { cout << "Bhinneka" << endl; } return 0; } ``` This solution efficiently determines the winner by checking for direct moves to special tiles and using the properties of the board's dimensions to decide the outcome when no direct move is possible. The use of sorting and binary search ensures that the solution is optimal for large input sizes.

Imagination Castle

Problem Details