P12560 [UTS 2024] Randomized Palindromes

You are given a binary matrix $n \times n$ consisting of zeroes and ones. Initially, you have an empty string $S$. You start in the position $(0;0)$ (left-up corner) and move right or down. You append each element you have passed to the string $S$ in the respective order. Tell whether it is possible to achieve $S$ being a palindrome. If yes, print the way it should pass to achieve that. Note that each matrix is randomly generated.

The first line contains the only integer $n$ $(1 \le n \le 5\,000)$ --- the size of a matrix. The following $n$ lines contain the $n$ characters $a_{i,j}$ $(0 \le a_{i,j} \le 1)$ --- description of the matrix. The input matrix for the problem is picked $\textbf{randomly}$ across all possible valid matrices for the problem of size $n \times n$.

Print $\tt{NO}$ if there is no such palindrome. Otherwise, in the first line, print $\tt{YES}$. In each of the following $2n-1$ lines, print two integers $x_i$ and $y_i$ ($0 \leq x_i, y_i < n$) --- the coordinates of the $i$-th cell.

- ($5$ points) $n \le 10$; - ($9$ points) $n \le 100$; - ($19$ points) $n \le 500$; - ($27$ points) $n \le 1\,500$; - ($40$ points) no additional restrictions.