Description

You are writing a vision program for a robot. Each time the robot’s camera takes a photo, the image is stored in the robot’s memory as a black-and-white image. Each image is a grid of pixels of size $H\times W$. The rows are numbered from $0$ to $H-1$, and the columns are numbered from $0$ to $W-1$. Each image contains exactly two black pixels, and all other pixels are white.

The robot can process images using a program made of simple instructions. Given $H$, $W$, and a positive integer $K$, your goal is to write a function that generates a program for the robot. This program must determine whether the distance between the two black pixels is exactly $K$. Here, the distance between the pixel at row $r_1$ and column $c_1$ and the pixel at row $r_2$ and column $c_2$ is defined as $|r_1-r_2|+|c_1-c_2|$. In this expression, $|x|$ denotes the absolute value of $x$: it equals $x$ when $x\ge0$, and equals $-x$ when $x<0$.

The robot works as follows.

The robot’s memory has enough cells, numbered starting from $0$. Each cell can store $0$ or $1$, and once its value is set, it cannot be changed. The image is stored in memory row by row, in cells numbered from $0$ to $H\cdot W-1$. The first row is stored in cells $0$ to $W-1$, and the last row is stored in cells $(H-1)W$ to $H\cdot W-1$. In particular, if the pixel at row $i$ and column $j$ is black, then the value stored in cell $i\cdot W+j$ is $1$; otherwise it is $0$.

The robot’s program is a sequence of instructions, numbered by consecutive integers starting from $0$. While the program runs, instructions are executed one by one. Each instruction reads the values of one or more memory cells (we call these values the instruction’s inputs) and produces a value $0$ or $1$ (we call it the instruction’s output). The output of instruction $i$ is stored in cell $H\cdot W+i$. The inputs of instruction $i$ can only be memory cells that store the image, or memory cells that store outputs of previous instructions, i.e., cells numbered from $0$ to $H\cdot W+i-1$.

The robot has four types of instructions:

• NOT: has exactly one input. If the input is $0$, the output is $1$; otherwise the output is $0$.
• AND: has one or more inputs. Its output is $1$ if and only if all inputs are $1$.
• OR: has one or more inputs. Its output is $1$ if and only if at least one input is $1$.
• XOR: has one or more inputs. Its output is $1$ if and only if the number of inputs equal to $1$ is odd.

If the distance between the two black pixels is exactly $K$, then the output of the last instruction should be $1$; otherwise it should be $0$.

Implementation Details

You need to implement the following function:

void construct_network(int H, int W, int K)

• $H$, $W$: the size of the image captured by the robot’s camera.
• $K$: a positive integer.
• This function must generate a robot program. For every image captured by the robot’s camera, the program should determine whether the distance between the two black pixels is exactly $K$.

The program should be generated by appending instructions to the robot’s program (initially, the robot’s program is empty) by calling the following functions:

int add_not(int N)
int add_and(int[] Ns)
int add_or(int[] Ns)
int add_xor(int[] Ns)

• These append one NOT, AND, OR, or XOR instruction, respectively.
• $N$ (for add_not): the index of the input memory cell for the NOT instruction to be appended.
• $Ns$ (for add_and, add_or, add_xor): an array of indices of input memory cells for the AND, OR, or XOR instruction to be appended.
• Each call returns the index of the memory cell where the appended instruction’s output is stored. Consecutive calls will return consecutive integers starting from $H\cdot W$.

The robot’s program may contain at most $10^4$ instructions. In total, these instructions may read at most $10^6$ values. In other words, the sum of the lengths of the $Ns$ arrays over all add_and, add_or, and add_xor calls, plus the number of add_not calls, must not exceed $10^6$.

After appending the last instruction, the function construct_network must return. The generated robot program will be evaluated on some images. For an image, the output of the last instruction is $1$ if and only if the distance between the two black pixels is exactly $K$. If, for every image in a test point, the program generated by your solution outputs the correct result, then you pass that test point.

While evaluating your program, the grader may produce the following error messages:

• Instruction with no inputs: an empty array was provided as input to add_and, add_or, or add_xor.
• Invalid index: an incorrect (possibly negative) memory cell index was provided as input to add_not, add_or, or add_xor.
• Too many instructions: your function attempted to add more than $10^4$ instructions.
• Too many inputs: the instructions in the program read more than $10^6$ values in total.

Example of a Grader Program

The example grader program reads input in the following format:

• Line $1$: $H$, $W$, $K$.
• Line $2+i$ ($i\ge0$): $r1_i$, $c1_i$, $r2_i$, $c2_i$.
• The last line: $-1$.

Except for the first and the last line, each line represents an image containing two black pixels. Let the image described on line $2+i$ be image $i$. In this image, one black pixel is at row $r_1[i]$ and column $c_1[i]$, and the other black pixel is at row $r_2[i]$ and column $c_2[i]$.

The example grader program first calls construct_network(H, W, K). If construct_network violates the constraints described in this statement, the example grader will output one of the error messages listed at the end of the Implementation Details section and terminate.

Otherwise, the example grader program outputs two parts.

First, it outputs the robot program’s results in the following format:

• Line $1+i$ ($0\le i$): the output ($1$ or $0$) of the last instruction of the robot program for image $i$.

Second, it writes the following format to a file named log.txt in the current directory:

• Line $1+i$ ($0\le i$): $m_{i,0}$, $m_{i,1}$, $\dots$，$m_{i,c-1}$.

The sequence on line $1+i$ describes the data stored in memory after the robot program finishes running with image $i$ as input. Specifically, $m_{i,j}$ is the value stored in memory cell $j$. Note that $c$ (the sequence length) equals $H\cdot W$ plus the number of instructions in the robot program.

Hint

Sample

Suppose $H=2$, $W=3$, and $K=3$. In this case, there are only two possible images where the distance between the two black pixels is $3$.

• Case 1: the black pixels are $0$ and $5$.
• Case 2: the black pixels are $2$ and $3$.

One feasible solution is to construct the robot program using the following calls:

1. add_and([0, 5]): adds an instruction whose output is $1$ if and only if the image matches case 1. The output will be stored in memory cell $6$.
2. add_and([2, 3]): adds an instruction whose output is $1$ if and only if the image matches case 2. The output will be stored in memory cell $7$.
3. add_or([6, 7]): adds an instruction whose output is $1$ if and only if at least one of the above two cases holds.

Constraints

For all data:

• $1\le H,W\le200$.
• $2\le H\cdot W$.
• $1\le K\le H+W-2$.

The additional constraints and scores for each subtask are as follows: | Subtask ID | Additional Constraints | Score | | :--------: | :--------------------: | :---: | | $1$ | $\max(H,W) \le 3$ | $10$ | | $2$ | $\max(H,W) \le 10$ | $11$ | | $3$ | $\max(H,W) \le 30$ | $11$ | | $4$ | $\max(H,W) \le 100$ | $15$ | | $5$ | $\min(H,W) = 1$ | $12$ | | $6$ | In every image, the pixel in row $0$ and column $0$ is black | $8$ | | $7$ | $K = 1$ | $14$ | | $8$ | No additional constraints | $19$ |

Translated by ChatGPT 5