CHEFTIC - Editorial

Problem Link:

Practice
Contest

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 :slight_smile:

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.

1 Like

Setter’s and Tester’s solution are not for this problem plzzz fix it…

1 Like

@akchamp

Setter’s solution - http://ideone.com/GIl9tu

Tester’s solution - http://ideone.com/1pZN0m

Editorialist’s solution - http://ideone.com/IDZKLf

“We can just do bruteforce by putting ‘X’ in each of the empty place of grid and check whether the grid has KK consecutive ‘X’'s or not.”

I think, this will not work for a test case like-

1

3 2

. . .

. . .

. . .

Here the actual answer is ‘NO’ but using this algorithm it will give ‘YES’.

My code is here-
https://www.codechef.com/viewsolution/9499155

@debjitdj, I think the editorialist meant, putting X at given position and checking if a solution exists, then removing the X placed for next iteration. Putting it simply, as the chef can play only one move, putting X at all possible locations is not what the editorialist meant to say.

1 Like

The links to the Problem in the Contest section and Practice section are incorrect. Please fix them.

You can add only one X.

Could someone point out what’s wrong in my solution here or give a set of n=k=3 tests?
https://www.codechef.com/viewsolution/9503691

Thanks

@likecs I have a doubt. Is this a valid test case?-

1

4 3

. X O .

X O O X

O X X O

X O X O

Because in this case that logic will also no work.

And what about this test case?

1

4 3

. X O .

X O O X

O X X O

X O X O

Done exactly like this !!!

https://www.codechef.com/viewsolution/9500258

and got AC :slight_smile:

1 Like

In that case also, it will work. You can put X in two places and check for those cases. Answer will be NO.

But the answer should be ‘YES’…because there are already 3 consecutive ‘X’.

That input is invalid according to problem. The board cannot already have some winner.

1 Like

Invalid, read the last line of the problem saying that it will be always chef’s chance and the board will not have any winner already.

Oh! I missed the last line. Thankz :slight_smile:

Sorry. I missed the last line.

@likecs: I have expanded the editorial, hope that will answer the question properly.

Oh, I didn’t see that. Yes it’s invalid input.

Can anyone help me find out test cases for 3rd subtask for which my solln. does not work?
https://www.codechef.com/viewsolution/9502837