Imagination Castle (Codeforces 1866I)
Tags: DP, games

Given a chessboard of size $$$N \times M$$$ ($$$N$$$ rows and $$$M$$$ columns). Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom and each column is numbered from $$$1$$$ to $$$M$$$ from left to right. The tile in row $$$r$$$ and column $$$c$$$ is denoted as $$$(r,c)$$$. There exists $$$K$$$ distinct special tiles on the chessboard with the $$$i$$$-th special tile being tile $$$(X_i,Y_i)$$$. It is guaranteed that tile $$$(1,1)$$$ is not a special tile.A new chess piece has been invented, which is the castle. The castle moves similarly to a rook in regular chess, but slightly differently. In one move, a castle that is on some tile can only move to another tile in the same row or in the same column, but only in the right direction or the down direction. Formally, in one move, the castle on tile $$$(r,c)$$$ can only move to tile $$$(r',c')$$$ if and only if one of the following two conditions is satisfied:   $$$r'=r$$$ and $$$c'>c$$$.  $$$c'=c$$$ and $$$r'>r$$$. Chaneka and Bhinneka will play a game. In the beginning of the game, there is a castle in tile $$$(1,1)$$$. The two players will play alternatingly with Chaneka going first. In one turn, the player on that turn must move the castle following the movement rules of the castle.If a player moves the castle to a special tile on her turn, then that player wins the game and the game ends. If on a turn, the castle cannot be moved, the player on that turn loses and the game ends.Given the size of the board and the locations of each special tile. Determine the winner of this game if Chaneka and Bhinneka plays optimally.

Input: The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \leq N,M \leq 2 \cdot 10^5$$$; $$$0 \leq K \leq \min(N \times M - 1, 2\cdot10^5)$$$) — the size of the chessboard and the number of special tiles.The $$$i$$$-th of the next $$$K$$$ lines contains two integers $$$X_i$$$ and $$$Y_i$$$ ($$$1\leq X_i\leq N$$$; $$$1\leq Y_i\leq M$$$; $$$(X_i, Y_i) \neq (1,1)$$$) — the location of each special tile. The special tiles are pairwise distinct.

Output: Output Chaneka if Chaneka is the winner, output Bhinneka if Bhinneka is the winner.

Note: In the first example, the following is an illustration of the chessboard in the beginning of the game. Chaneka can move the castle to special tile $$$(1,3)$$$ or $$$(1,5)$$$ directly on her first turn. Therefore, Chaneka is the winner.In the second example, the following is an illustration of the chessboard in the beginning of the game. Chaneka can only move the castle to tile $$$(1, 2)$$$ or $$$(2, 1)$$$ on her first turn. Whatever Chaneka does, Bhinneka will be able to directly move the castle to tile $$$(2, 2)$$$. After that, on Chaneka's turn, she cannot move the castle, so Chaneka loses. Therefore, Bhinneka is the winner.

Sample Inputs:
4 5 3
1 3
4 4
1 5

2 2 0

Sample Outputs:
Chaneka

Bhinneka

Solution (Python):
import sys

def main():
    (n, m, k) = map(int, input().split())
    vis = [0] * 200000
    v = [[] for _ in range(200000)]
    for _ in range(k):
        (x, y) = map(int, input().split())
        v[x - 1].append(y - 1)
    j = m - 1
    flag = False
    for i in range(n - 1, -1, -1):
        cmx = -1
        for t in v[i]:
            cmx = max(cmx, t)
            vis[t] = 1
        while j > -1 and vis[j] == 1:
            j -= 1
        if j > cmx:
            vis[j] = 1
            if i == 0 and j == 0:
                flag = True
    if flag:
        print('Bhinneka')
    else:
        print('Chaneka')
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, k) = map(int, input().split())
r = random.randint(1, pow(2, 30) - 1)
u = defaultdict(lambda : [])
v = defaultdict(lambda : [])
for _ in range(k):
    (x, y) = map(int, input().split())
    u[x ^ r].append(y)
    v[y ^ r].append(x)
(x, y) = (n, m)
(x0, y0) = ([0] * (n + 1), [0] * (m + 1))
while x ^ 1 and y ^ 1 and min(x, y):
    (x0[x], y0[y]) = (1, 1)
    while x0[x] or y0[y]:
        if x0[x]:
            for z in u[x ^ r]:
                y0[z] = 1
            x -= 1
        else:
            for z in v[y ^ r]:
                x0[z] = 1
            y -= 1
ans = 'Chaneka' if x ^ y or not max(x, y) else 'Bhinneka'
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
(n, m, k) = map(int, input().split())
special = [[] for _ in range(n)]
for _ in range(k):
    (x, y) = map(int, input().split())
    x -= 1
    y -= 1
    special[x].append(y)
j = m - 1
has0 = [0] * m
for i in range(n - 1, 0, -1):
    while j >= 0 and has0[j]:
        j -= 1
    mxjt = -1
    for jt in special[i]:
        has0[jt] = 1
        mxjt = max(jt, mxjt)
    if j >= 0 and j > mxjt:
        has0[j] = 1
if special[0] or has0[0]:
    print('Chaneka')
else:
    while j >= 0 and has0[j]:
        j -= 1
    print('Chaneka' if j else 'Bhinneka')