Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Two drunken players Alice and Bob are playing a modified version of Tic-Tac-Toe.

Initially, there is a $N \times M$ empty grid.

Alice and Bob take alternate turns starting with Alice. In her turn, Alice chooses an empty cell on the board and puts a "A" on the chosen cell. In Bob's turn, he chooses an empty cell and puts a "B" on the chosen cell.

The player who first gets any $K\times K$ subgrid completely filled with his/her initial wins the game. By a $K\times K$ subgrid, we mean the intersection of $K$ consecutive rows and $K$ consecutive columns. The players do not stop making turns after one of them wins and they play all $N \cdot M$ turns until the grid is filled.

You are given the sequence of moves played by each player (The cell selected by the player in his/her turn). You have to output the winner of the game or report that there is no winner.

------  Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow.
The first line of each test case contains three integers $N$, $M$, $K$.
Each of the next $N\cdot M$ lines contains two integers $X$, $Y$ (the row and column of the cell chosen by the player with the current turn)

------  Output ------
For each test case, output "Alice" if Alice wins the game or "Bob" if Bob wins the game or "Draw" if no one wins.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 1000$
$1 ≤ K ≤ \min(N,M)$
$1 ≤ X ≤ N$
$1 ≤ Y ≤ M$
The sum of $N\cdot M$ over all test cases does not exceed $10^{6}$.

------  Subtasks ------

Subtask 1 (10 points): $1 ≤ N ≤ 10,\ 1 ≤ M ≤ 10$

Subtask 2 (20 points): $1 ≤ N ≤ 50,\ 1 ≤ M ≤ 50$

Subtask 3 (70 points): Original Constraints

------  Sample Input ------

1
3 4 2
1 1
3 1
1 2
2 3
2 1
2 4
3 2
3 4
1 3
3 3
2 2
1 4

------  Sample Output ------

Bob

------  Explanation ------
After $10$ turns of the game the state of the grid is:

AAA.
A.BB
BABB

At this moment, Bob has achieved a subgrid of $2 \times 2$ with his initials while Alice has not achieved it yet so Bob is the winner.

Source: codechef | Difficulty: HARD
Tags: Sorting

Range queries

Complete search


Solutions:
import sys, math, random, heapq
from collections import deque
from math import gcd

def bs(arr, le, ri):
	l = 0
	arr.sort()
	r = len(arr) - 1
	ans = 10000000
	while l <= r:
		m = (l + r) // 2
		if arr[m] >= le and arr[m] <= ri:
			ans = arr[m]
			r = m - 1
		elif arr[m] < le:
			l = m + 1
		else:
			r = m - 1
	return ans
for __ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = [[-1 for j in range(m)] for i in range(n)]
	ans = [[0 for j in range(m)] for i in range(n)]
	largest = [[0 for i in range(m)] for j in range(n)]
	for i in range(n * m):
		(x, y) = map(int, input().split())
		l[x - 1][y - 1] = (i % 2, i)
	for i in range(n):
		ans[i][0] = l[i][0][0]
		for j in range(1, m):
			ans[i][j] = l[i][j][0] + ans[i][j - 1]
	for j in range(m):
		for i in range(1, n):
			ans[i][j] += ans[i - 1][j]
	for i in range(n):
		st = deque()
		for j in range(k):
			while len(st) > 0 and st[-1][0] < l[i][j][1]:
				st.pop()
			st.append((l[i][j][1], j))
		largest[i][k - 1] = st[0][0]
		for j in range(k, m):
			if st[0][1] == j - k:
				st.popleft()
			while len(st) > 0 and st[-1][0] < l[i][j][1]:
				st.pop()
			st.append((l[i][j][1], j))
			largest[i][j] = st[0][0]
	for i in range(k - 1, m):
		st = deque()
		for j in range(k):
			while len(st) > 0 and st[-1][0] < largest[j][i]:
				st.pop()
			st.append((largest[j][i], j))
		largest[k - 1][i] = st[0][0]
		for j in range(k, n):
			if st[0][1] == j - k:
				st.popleft()
			while len(st) > 0 and st[-1][0] < largest[j][i]:
				st.pop()
			st.append((largest[j][i], j))
			largest[j][i] = st[0][0]
	alice = []
	bob = []
	for i in range(k - 1, n):
		for j in range(k - 1, m):
			x = ans[i][j]
			if i - k >= 0:
				x -= ans[i - k][j]
			if j - k >= 0:
				x -= ans[i][j - k]
			if i - k >= 0 and j - k >= 0:
				x += ans[i - k][j - k]
			if x == 0:
				alice.append(largest[i][j])
			if x == k * k:
				bob.append(largest[i][j])
	if len(bob) == 0 and len(alice) == 0:
		print('Draw')
	elif len(bob) == 0:
		print('Alice')
	elif len(alice) == 0:
		print('Bob')
	else:
		print('Bob') if min(alice) > min(bob) else print('Alice')