Editorial

Loading problem...

Preparing the statement, recent submissions, and submit form.

Algorithm

A route exists if and only if $N$ is even and

K=\frac{N^2}{2}-1.

If this condition does not hold, print No. Otherwise, print Yes and make the following moves:

Make $N-1$ moves U, reaching $(1,N)$ .
For $x=2,3,\cdots,N$ , first make one move . If is even, make moves ; otherwise, make moves .

A feasible case requires printing $N^2$ characters and takes $O(N^2)$ time. An infeasible case takes $O(1)$ time. The total time complexity is .

Proof

An odd grid size is impossible.

Color each grid point according to the parity of $x+y$ . Every move changes the color, so any route returning to its starting point has even length. A cycle visiting every point exactly once has length $N^2$ . Therefore, $N$ must be even.

Every valid cycle has the same area.

Two horizontal or vertical unit grid segments can intersect or overlap only by sharing a grid point. No point is revisited except for the final return to the starting point. Thus, a valid cycle forms a simple polygon.

The polygon lies inside the square . Every integer grid point strictly inside it must therefore belong to . However, the cycle visits every point in , placing all of them on its boundary. Consequently, the number of interior grid points is .

Subtask 1

For $N\leq 4$ , exhaustively enumerate all routes while recording the visited points. Whenever a route visits every point and can return to the start in one more move, compute its area with the shoelace formula. Store a route for each area found, then look up the requested $K$ .

After the first move, the immediately preceding point cannot be visited again, so each extension considers at most $3$ directions. The search for one size $N$ takes $O(3^{N^2})$ time. The only possible sizes are , so perform the search once per size and reuse the results.

Area Inside a Cycle

Editorial