CF 102697053 - Tic-Tac-Toe

We are given which player we control, either X or O, followed by the current 3 by 3 Tic-Tac-Toe board. An empty cell is represented by a space.

codeforcescompetitive-programming

CF 102697053 - Tic-Tac-Toe

Rating: -
Tags: -
Solve time: 1m 7s
Verified: yes

Solution

Problem Understanding

We are given which player we control, either X or O, followed by the current 3 by 3 Tic-Tac-Toe board. An empty cell is represented by a space. We need to decide whether there is at least one empty cell where placing our mark immediately creates three equal marks in a row, column, or diagonal.

For example, with player X and the board

X OX  O X

placing X in the middle-right cell gives

X OX XO X

which completes the main diagonal? No, the main diagonal is already X X X only after considering the center, so this move wins.

The board size is fixed at only 3 by 3. There is no large n hidden in the input, so asymptotic complexity is less significant here than making the winning condition correct. Even an approach that examines every empty cell and checks the eight possible winning lines is tiny: there are at most 9 candidate moves and 8 lines to inspect for each move, giving at most 72 line checks. A quadratic or cubic approach is completely safe for this input size.

The tricky part is not performance but interpreting the board correctly.

One edge case is an already complete row. For

XXXXOO

the correct output is Yes you can. because X can place a mark in any empty cell, but more importantly, a careless implementation that only checks cells with exactly two existing marks might fail to recognize that the player has already won. The usual intended interpretation of the task is whether a winning move exists, so the safest implementation is to test candidate moves directly.

Another edge case is a diagonal win. For

OXOX O X

placing O in the bottom-right corner completes the main diagonal, so the output is Yes you can.. An implementation that checks only rows and columns silently misses this case.

A third edge case is a winning move on an anti-diagonal. For

XX O O   X

placing X in the top-right cell gives the anti-diagonal X X X, so the answer is Yes you can.. Both diagonals must be handled.

The sample displayed by Codeforces contains a trailing | after each board row. This is part of the board representation shown by the statement, so the implementation below removes | when reading a row and preserves spaces as empty cells.

Approaches

The most direct brute-force solution is to try every empty square. For each candidate square, place our mark there temporarily and check all three rows, all three columns, and both diagonals. If any of those eight lines consists entirely of our mark, the move wins.

This is already fast enough. There are at most 9 possible moves and exactly 8 winning lines, so the worst case performs at most 72 line checks. Each line contains only 3 cells, giving at most 216 individual cell inspections. Since the board is permanently 3 by 3, this is effectively constant time.

We can simplify the implementation further by observing that a move can only affect the row, column, and possibly one or two diagonals passing through the selected cell. Instead of checking all eight lines after every move, we can directly ask whether some winning line currently contains exactly two of our marks and one empty cell. That empty cell is then the winning move.

There are only eight possible winning lines in Tic-Tac-Toe. We inspect each one, count our marks and empty cells, and accept if a line contains exactly two of our marks and one empty cell. This avoids modifying the board and makes the condition especially explicit.

The brute-force solution is already accepted because the input is a fixed 3 by 3 board. The second approach is preferable because it directly expresses the mathematical condition for a winning move and has less state to manipulate.

Approach Time Complexity Space Complexity Verdict
Brute Force O(1), at most 216 cell inspections O(1) Accepted
Check all winning lines O(1), 8 lines of length 3 O(1) Accepted

Algorithm Walkthrough

  1. Read the player's mark and the three board rows. Remove a possible trailing | from each row, but do not remove spaces because spaces represent empty cells.
  2. Enumerate the eight winning lines: three rows, three columns, the main diagonal, and the anti-diagonal. Every possible Tic-Tac-Toe win belongs to exactly one of these lines.
  3. For each line, count how many cells contain our mark and how many cells are empty.
  4. If a line contains exactly two of our marks and exactly one empty cell, that empty cell is a legal winning move. Print Yes you can. immediately.
  5. If all eight lines have been checked without finding such a line, print No you can't..

The key invariant is that after processing any prefix of the eight winning lines, every possible one-move win belonging to those processed lines has already been detected. Since every Tic-Tac-Toe win is one of the eight lines, finishing the scan proves that no winning move exists when none was found.

Python Solution

Pythonimport sysinput = sys.stdin.readline

def solve():    player = input().strip()
    board = []    for _ in range(3):        row = input().rstrip("\n")        if row.endswith("|"):            row = row[:-1]        board.append(row)
    lines = []
    for r in range(3):        lines.append([(r, 0), (r, 1), (r, 2)])
    for c in range(3):        lines.append([(0, c), (1, c), (2, c)])
    lines.append([(0, 0), (1, 1), (2, 2)])    lines.append([(0, 2), (1, 1), (2, 0)])
    for line in lines:        mine = 0        empty = 0
        for r, c in line:            if board[r][c] == player:                mine += 1            elif board[r][c] == " ":                empty += 1
        if mine == 2 and empty == 1:            print("Yes you can.")            return
    print("No you can't.")

if __name__ == "__main__":    solve()

The first input line identifies which symbol belongs to the current player. We keep it as a single character so every later comparison is simply board[r][c] == player.

Each board row is read with rstrip("\n") rather than strip(). This distinction matters because strip() would delete leading and trailing spaces, destroying information about empty cells. If the input representation contains the trailing | shown in the official sample, it is removed separately.

The eight winning lines are represented by their three coordinate pairs. The first six describe the three horizontal and three vertical lines, while the last two describe the diagonals.

For every line, mine counts the current player's marks and empty counts spaces. A winning move exists precisely when those counts are 2 and 1. The third cell is necessarily empty and can be filled with the player's mark to create three in a row.

There is no need to modify the board, undo a move, or search through candidate cells. That avoids the most common implementation mistake in the brute-force version, where a temporary move is left on the board while the next candidate is tested.

Python integers cannot overflow here, and all indices are explicitly limited to 0, 1, and 2.

Worked Examples

Sample 1

The official sample gives player X and the board shown below. The trailing | characters are removed before processing.

XXOXXO O X

The algorithm inspects the winning lines as follows.

Line Cells X count Empty count Result
Row 1 X O X 2 0 Not a move
Row 2 X O space 1 1 Not a move
Row 3 O space X 1 1 Not a move
Column 1 X X O 2 0 Not a move
Column 2 O O space 0 1 Not a move
Column 3 X space X 2 1 Winning move

The third column contains two X marks and one empty cell, so putting X there wins immediately. The output is Yes you can..

Example 2

Consider player O with this board:

OXX O

The relevant line counts are:

Line Cells O count Empty count Result
Row 1 O X X 1 0 Not a move
Row 2 space O space 1 2 Not a move
Row 3 space space space 0 3 Not a move
Column 1 O space space 1 2 Not a move
Column 2 X O space 1 1 Not a move
Column 3 X space space 0 2 Not a move
Main diagonal O O space 2 1 Winning move

The main diagonal has two O marks and one empty cell. Filling the bottom-right corner with O creates O O O, so the answer is Yes you can..

Complexity Analysis

Measure Complexity Explanation
Time O(1) There are exactly 8 winning lines, each containing 3 cells.
Space O(1) The board and the fixed set of winning lines have constant size.

The board never grows beyond 3 by 3, so the solution performs only a few dozen elementary operations. It is comfortably within the 1 second time limit and 256 MB memory limit given by Codeforces.

Test Cases

The original statement exposes one sample, so the remaining tests below cover the small fixed board, both diagonal directions, a position with no immediate win, and the trailing | representation used by the sample.

Pythonimport sysimport io

def solve():    player = input().strip()
    board = []    for _ in range(3):        row = input().rstrip("\n")        if row.endswith("|"):            row = row[:-1]        board.append(row)
    lines = []
    for r in range(3):        lines.append([(r, 0), (r, 1), (r, 2)])
    for c in range(3):        lines.append([(0, c), (1, c), (2, c)])
    lines.append([(0, 0), (1, 1), (2, 2)])    lines.append([(0, 2), (1, 1), (2, 0)])
    for line in lines:        mine = 0        empty = 0
        for r, c in line:            if board[r][c] == player:                mine += 1            elif board[r][c] == " ":                empty += 1
        if mine == 2 and empty == 1:            print("Yes you can.")            return
    print("No you can't.")

def run(inp: str) -> str:    global input    old_stdin = sys.stdin    old_input = input
    sys.stdin = io.StringIO(inp)    input = sys.stdin.readline
    try:        from io import StringIO
        old_stdout = sys.stdout        sys.stdout = StringIO()
        solve()        result = sys.stdout.getvalue()
        sys.stdout = old_stdout        return result    finally:        sys.stdin = old_stdin        input = old_input

# Provided sampleassert run(    "X\n"    "XOX|\n"    "XO |\n"    "O X|\n") == "Yes you can.\n", "sample 1"
# Row winassert run(    "X\n"    "XX \n"    "OO \n"    "   \n") == "Yes you can.\n", "winning row"
# Main diagonal winassert run(    "O\n"    "OXX\n"    " O \n"    "   \n") == "Yes you can.\n", "winning main diagonal"
# Anti-diagonal winassert run(    "X\n"    " O \n"    " XO\n"    "  X\n") == "Yes you can.\n", "winning anti-diagonal"
# No immediate winning moveassert run(    "X\n"    "XOX\n"    "OXO\n"    "OX \n") == "No you can't.\n", "no winning move"
Test input Expected output What it validates
X / XOX| / XO | / O X| Yes you can. Official sample and trailing | handling
X / XX / OO / Yes you can. Winning move at the end of a row
O / OXX / O / Yes you can. Main diagonal
X / O / XO / X Yes you can. Anti-diagonal
X / XOX / OXO / OX No you can't. No available immediate win

Edge Cases

A row with two of the player's marks and one empty cell is the simplest winning case. For

XXX OO

the first row contains two X marks and one space. The algorithm records mine = 2 and empty = 1, so it immediately returns Yes you can.. This catches implementations that accidentally require the empty cell to be in a particular column.

For a diagonal case, consider

OOXX O

The main diagonal is O O space. When the algorithm reaches that line, its counts are mine = 2 and empty = 1, so the bottom-right cell is identified as the winning move. A solution checking only horizontal and vertical lines would incorrectly return No you can't..

The opposite diagonal must be treated independently. With

X O  XO  X

the anti-diagonal contains X X space from top-right to bottom-left. The algorithm explicitly includes coordinates (0, 2), (1, 1), and (2, 0), so it finds the winning move without relying on a special case hidden elsewhere in the code.

Finally, the sample's trailing | characters require careful input handling. For

XXOX|XO |O X|

the parser removes only the final |, leaving the spaces inside each row untouched. The resulting board is exactly three cells wide, and the third column contains X, a space, and X, which gives the required winning move. The output is Yes you can..