F2. Plegma II: Ask Me Any Cell (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note the unusual score distribution for F1 and F2. This problem is significantly more difficult than F1.

There is a visualizer available for this problem. You can view it using this link.

Hacks are disabled on this problem.

This is the Hard Version of the problem. The only difference between the two versions is the constraints on $$$n$$$ and $$$k$$$.

Verity has a grid of $$$n$$$ rows and $$$n$$$ columns. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. The cell on row $$$p$$$ and column $$$q$$$ is denoted by $$$(p, q)$$$.

Verity also has a robot, Circuity, with extremely simple functionality. Verity must program Circuity so it can automatically locate specific cells on the grid, while ensuring these cells stay hidden from foreign robots.

There are two phases in this problem.

Phase 1: Verity (Encoding)

In this phase, Verity tries to encode a given cell on the grid.

Verity receives a target cell $$$(r, c)$$$, and he assigns a binary value ($$$0$$$ or $$$1$$$) to each cell of the grid. On cells with value $$$1$$$, beacons that broadcast signal will be placed, while cells with value $$$0$$$ remain empty.

However, he believes that using too few beacons will make it easy for foreigners to also locate the target cell. Therefore, he has decided that it is safest to use at most $$$k$$$ zeros.

Phase 2: Circuity (Decoding)

In this phase, Circuity tries to find the cell Verity encoded, based on the grid he created. However, Circuity is unable to process large grids efficiently.

At each moment of time, Circuity suspects that the target cell lies in the subgrid bounded by the two cells $$$(x_0, y_0)$$$ and $$$(x_1, y_1)$$$. Initially, $$$(x_0, y_0) = (1, 1)$$$ and $$$(x_1, y_1) = (n, n)$$$.

Circuity locates the encoded cell by making exactly $$$2n-2$$$ decisions, one after another. Each decision works as follows.

Circuity can sense the number of beacons in the current subgrid. Let this number be $$$S$$$. Formally, $$$S$$$ is the number of cells with value $$$1$$$ inside the subgrid bounded by the cells $$$(x_0, y_0)$$$ and $$$(x_1, y_1)$$$.

Based solely on $$$S$$$, it will choose exactly one of the following actions:

  • Action U: increase $$$x_0$$$ by $$$1$$$
  • Action L: increase $$$y_0$$$ by $$$1$$$
  • Action D: decrease $$$x_1$$$ by $$$1$$$
  • Action R: decrease $$$y_1$$$ by $$$1$$$

Note that this decision does not rely on previous decisions, and it cannot directly rely on the values of $$$x_0, x_1, y_0$$$ or $$$y_1$$$. Circuity is memoriless, and the only parameter when making a decision must be $$$S$$$ in the current moment.

If at any point $$$x_0 \gt x_1$$$ or $$$y_0 \gt y_1$$$, the program bugs out and Circuity is unsuccessful.

The cell Verity encoded in this grid was some cell $$$(r, c)$$$. After all $$$2n-2$$$ decisions, it must hold that $$$x_0 = x_1 = r$$$ and $$$y_0 = y_1 = c$$$.

There are exactly 32 tests:

  • Each value $$$n = 3,10,11,\ldots,40$$$ is used in exactly one test, in order.
  • For every allowed $$$n$$$, $$$k=f(n)$$$, where $$$f(n)$$$ is the minimum possible worst-case number of zeros needed to encode any cell of an $$$n \times n$$$ grid.
Input

The only input contains one integer $$$n$$$ ($$$n = 3$$$ or $$$10 \le n \le 40$$$).

Output
  • For Phase $$$1$$$:

Output $$$n^2$$$ binary grids.

The $$$i$$$-th grid is the grid Verity should choose when the target is $$$(r, c)$$$, where $$$r = \lfloor \frac{i-1}{n} \rfloor + 1$$$ and $$$c = ((i-1) \bmod n) + 1$$$.

In other words, the first grid corresponds to target $$$(1,1)$$$, the second grid corresponds to target $$$(1,2)$$$, the $$$(n+1)$$$-th grid corresponds to target $$$(2,1)$$$, and so on.

Each grid must contain at most $$$k=f(n)$$$ zeros.

  • For Phase $$$2$$$:

Output a sequence of $$$n^2 + 1$$$ characters: $$$a_0, a_1, a_2, \ldots, a_{n^2}$$$. Each character must be one of U, D, L, or R. The $$$i$$$-th character means that if $$$S=i$$$, then Circuity performs action $$$a_i$$$.

Example
Input
3
Output
111
111
001

011
111
100

110
110
110

010
111
111

111
111
111

010
111
101

111
111
110

111
011
111

011
010
111

DURLDULRUU
Note

Consider the third grid as an example. The target cell is $$$(1,3)$$$.

Verity chooses the following grid: 

110
110
110

The action sequence is: 

DURLDULRUU

Initially, Circuity examines the subgrid bounded by $$$(1,1)$$$ and $$$(3,3)$$$.

It must locate cell $$$(1,3)$$$, so it will make $$$2 \cdot 3 - 2 = 4$$$ decisions.

  • Decision 1: there are $$$S=6$$$ ones in the current subgrid, so Circuity performs action $$$a_6=\mathtt{L}$$$.

    The new subgrid becomes $$$[(1,2),(3,3)]$$$.

  • Decision 2: there are $$$S=3$$$ ones in the current subgrid, so Circuity performs action $$$a_3=\mathtt{L}$$$.

    The new subgrid becomes $$$[(1,3),(3,3)]$$$.

  • Decision 3: there are $$$S=0$$$ ones in the current subgrid, so Circuity performs action $$$a_0=\mathtt{D}$$$.

    The new subgrid becomes $$$[(1,3),(2,3)]$$$.

  • Decision 4: there are again $$$S=0$$$ ones in the current subgrid, so Circuity performs action $$$a_0=\mathtt{D}$$$.

    The new subgrid becomes $$$[(1,3),(1,3)]$$$.

After all decisions, Circuity ends up at cell $$$(1,3)$$$, which is indeed the target cell.