CF1450C2 Errich-Tac-Toe (Hard Version)

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.

N/A

N/A

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.