Errich-Tac-Toe (Hard Version) (Codeforces 1450C2)
Tags: Math, constructive algorithms

The only difference between the easy and hard versions is that tokens of type O do not appear in the input of the easy version.Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces.In a Tic-Tac-Toe grid, there are $$$n$$$ rows and $$$n$$$ columns. Each cell of the grid is either empty or contains a token. There are two types of tokens: X and O. If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration.  The patterns in the first row are winning configurations. The patterns in the second row are draw configurations. In an operation, you can change an X to an O, or an O to an X. Let $$$k$$$ denote the total number of tokens in the grid. Your task is to make the grid a draw in at most $$$\lfloor \frac{k}{3}\rfloor$$$ (rounding down) operations.You are not required to minimize the number of operations.

Input: The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 300$$$) — the size of the grid.The following $$$n$$$ lines each contain a string of $$$n$$$ characters, denoting the initial grid. The character in the $$$i$$$-th row and $$$j$$$-th column is '.' if the cell is empty, or it is the type of token in the cell: 'X' or 'O'.It is guaranteed that not all cells are empty.The sum of $$$n$$$ across all test cases does not exceed $$$300$$$.

Output: For each test case, print the state of the grid after applying the operations.We have proof that a solution always exists. If there are multiple solutions, print any.

Note: In the first test case, there are initially three 'O' consecutive in the second row and the second column. By changing the middle token to 'X' we make the grid a draw, and we only changed $$$1\le \lfloor 5/3\rfloor$$$ token.In the second test case, the final grid is a draw. We only changed $$$8\le \lfloor 32/3\rfloor$$$ tokens.In the third test case, the final grid is a draw. We only changed $$$7\le \lfloor 21/3\rfloor$$$ tokens.

Sample Inputs:
3
3
.O.
OOO
.O.
6
XXXOOO
XXXOOO
XX..OO
OO..XX
OOOXXX
OOOXXX
5
.OOO.
OXXXO
OXXXO
OXXXO
.OOO.

Sample Outputs:
.O.
OXO
.O.
OXXOOX
XOXOXO
XX..OO
OO..XX
OXOXOX
XOOXXO
.OXO.
OOXXO
XXOXX
OXXOO
.OXO.

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def gift():
    for _ in range(t):
        n = int(input())
        s = []
        for i in range(n):
            array = list(input())
            s.append(array)
        f = [0] * 3
        g = [0] * 3
        for (i, r) in enumerate(s):
            for (j, c) in enumerate(r):
                if c == 'X':
                    f[(i + j) % 3] += 1
                elif c == 'O':
                    g[(i + j) % 3] += 1
        rKey = min([1, 2, 3, 5, 6, 7], key=lambda x: f[x % 3] + g[x // 3])
        for (i, r) in enumerate(s):
            for (j, c) in enumerate(r):
                if c == 'X' and (i + j) % 3 == rKey % 3:
                    s[i][j] = 'O'
                elif c == 'O' and (i + j) % 3 == rKey // 3:
                    s[i][j] = 'X'
            yield ''.join(s[i])
if __name__ == '__main__':
    t = int(input())
    ans = gift()
    print(*ans, sep='\n')

Solution (Python):
def mini(a, b):
    pp = []
    pp = [[a[0] + b[1], [0, 1]], [a[0] + b[2], [0, 2]], [a[1] + b[0], [1, 0]], [a[1] + b[2], [1, 2]], [a[2] + b[0], [2, 0]], [a[2] + b[1], [2, 1]]]
    pp.sort()
    return (pp[0][1][0], pp[0][1][1])
t = int(input())
for z in range(t):
    n = int(input())
    arr = []
    count = [0, 0, 0]
    suma = [0, 0, 0]
    for i in range(n):
        arr.append(list(input()))
    for i in range(n):
        for j in range(n):
            if arr[i][j] == 'X':
                count[(i + j) % 3] += 1
            if arr[i][j] == 'O':
                suma[(i + j) % 3] += 1
    (k, p) = mini(count, suma)
    for i in range(n):
        for j in range(n):
            if (i + j) % 3 == k and arr[i][j] == 'X':
                arr[i][j] = 'O'
            elif (i + j) % 3 == p and arr[i][j] == 'O':
                arr[i][j] = 'X'
        arr[i] = ''.join(arr[i])
    for s in arr:
        print(s)

Solution (Python):
def main():
    t = int(input())
    while t > 0:
        t -= 1
        n = int(input())
        mp = [''] * n
        X = [0] * 3
        O = [0] * 3
        for i in range(n):
            mp[i] = list(input().strip())
            for j in range(n):
                if mp[i][j] == 'X':
                    X[(i + j) % 3] += 1
                elif mp[i][j] == 'O':
                    O[(i + j) % 3] += 1
        tp = [0, 1]
        mins = X[0] + O[1]
        for i in range(3):
            for j in range(3):
                if i == j:
                    continue
                if mins > X[i] + O[j]:
                    mins = X[i] + O[j]
                    tp = [i, j]
        for i in range(n):
            for j in range(n):
                k = (i + j) % 3
                if k == tp[0] and mp[i][j] == 'X':
                    mp[i][j] = 'O'
                elif k == tp[1] and mp[i][j] == 'O':
                    mp[i][j] = 'X'
        for i in range(n):
            print(''.join(mp[i]))
if __name__ == '__main__':
    main()