Problem Link:
Author: Misha Chorniy
Tester: Pushkar Mishra
Editorialist: Praveen Dhinwa
Difficulty:
simple
Pre-Requisites:
Implementation, bruteforce.
Problem Statement
Two players are playing game of Tic-Tac-Toe on a grid of size n \times n. First player puts ‘X’, whereas second puts ‘O’ in one of the empty cells in the grid (denoted by ‘.’). You are given the state of a game at some point of time. Now it is turn of first player to put an ‘X’, First player will win at this step if by putting an ‘X’ in this step, he can create K consecutive X’s in either a row, column or diagonal. You have to find out whether there is such an empty cell for first player or not? It is guaranteed that none of the player has won the game till now.
Quick Explanation
We can use a direct bruteforce solution by putting X in each of the empty cells of grid and check whether the modified grid has K consecutive X’s in a row, column or diagonal or not.
Even simpler solution will be to check whether there exists K-1 consecutive X’s in some row, column or diagonal in the grid and there is an empty cell available for extending that to create a row, column or diagonal of K consecutive X’s.
Explanation
Subtask 1
K is fixed to be 1. So, we just have to check if it is possible to 1 X in the grid or not. It is equivalent to checking whether there is an empty cell in the grid or not.
Subtask 2
N and K are fixed to 3. It is like usual Tic Tac Toe game. We have to check whether there are two consecutive cells with X’s either in a row, column or diagonal.
We can check these conditions in constant time as N and K are fixed to 3.
Subtask 3
Now, K, N are general and can take values up to 20.
Method 1
We select each of the empty cells of the grid and try putting an ‘X’ in it. For each such grid, we will check whether there is an row, column or diagonal with exactly K X’s. Note that problem statement guarantees that there will never be a situation in which the grid will contain more than K consecutive cells in the grid after putting an ‘X’, i.e. the original grid can contain at max K - 1 consecutive X’s.
For checking whether there will exist a row, column or diagonal with exactly K X’s, we can iterate over each cell of the modified grid (after putting one ‘X’) and check the number of X’s lying consecutively in the row, column or diagonal starting from cell (i, j).
Checking row
let x = i // assume 0 based indexing
let y = j
total = 0 // number of consecutive X's in a row starting from (i, j)
for i in range(0, K):
x++;
if (x >= 0 and x < n and y >= 0 and y < n and grid[x][y] == 'X')
ans += 1
else
break;
Checking column
let x = i // assume 0 based indexing
let y = j
ans = 0 // number of consecutive X's in a column starting from (i, j)
for i from 1 to K:
y++; // increment y
if (x >= 0 and x < n and y >= 0 and y < n and grid[x][y] == 'X')
ans += 1
else
break;
Now, there can be two possible diagonal starting from cell (i, j), one of the diagonal going towards right downwards from current cell (also called as main/principal/primary/leading diagonal) and one going towards left downwards([antidiagonal/counter-diagonal/secondary/trailing/minor]).
Checking Major diagonal
let x = i // assume 0 based indexing
let y = j
ans = 0 // number of consecutive X's in a major diagonal starting from (i, j)
for i in range(0, K):
x++; // increment x as mjaor diagonal goes towards right
y++; // increment y as mjaor diagonal goes towards right
if (x >= 0 and x < n and y >= 0 and y < n and grid[x][y] == 'X')
ans += 1
else
break;
Checking minor diagonal
let x = i // assume 0 based indexing
let y = j
ans = 0 // number of consecutive X's in a minor diagonal starting from (i, j)
for i from 1 to K:
x++; // increment x
y--; // decrement y (because minor diagonal towards left, i.e. decreasing y)
if (x >= 0 and x < n and y >= 0 and y < n and grid[x][y] == 'X')
ans += 1
else
break;
Infact, we can succinctly represent the movement along a direction by a pair of variables (dx, dy) where dx, dy denote the change in the x and y coordinates respectively for a single step. For example, movement in a row by a single step, increases x by 1 whereas there is no change in y, so we can represent this by dx = 1, dy = 0. Similarly, for column we have dx = 0, dy = 1. For a major diagonal, we have dx = 1, dy = 1, and for a minor we have dx = 1, dy = -1. Using this idea, we can reduce our code by creating two arrays dx and dy denoting all the movement directions.
let dx = [1, 0, 1, 1]
let dy = [0, 1, 1, -1]
let x = i // assume 0 based indexing
let y = j
total = 0 // number of consecutive X's in a row starting from (i, j)
for direction = 0 to 3:
ans = 0 // number of consecutive X's in the direction denoted by variable #direction, starting from (i, j)
for i from 1 to K
x += dx[direction]
y += dy[direction]
if (x >= 0 and x < n and y >= 0 and y < n and grid[x][y] == 'X')
ans += 1
else
break;
Now let us estimate time complexity of this solution. First we replace each the empty cells by ‘X’, so number of such grids can be O(N^2) in the worst case. Now for each such modified grid, we iterate over all O(N^2) cells and for each of the cell, we search for maximum number of consecutive X’s in row/column/diagonal which can take at max O(K) steps in the worst case.
So, overall time complexity will be O(N^2 * N^2 * K) = O(N^4 * K).
A faster solution
In the previous solution, we had created O(n^2) grids and processed each of them. Note that we can check the condition of K consecutive X’s by working on a single grid itself. We can reformulate the problem as checking whether there exists a row/column/diagonal with K - 1 consecutive X’s and there is an empty cell which can be used to extend these X’s to create K X’s. You can implement this solution using the ideas described above. For sample implementations, please see either of the setter’s or tester’s solution.
Time complexity of this solution will be O(N^2 * K).
Exercise
Can you solve this problem in O(N^2) time? Please feel free to answer this question in comments 
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.