Stamp

This is a heuristic optimization problem.

You are given a colored $N\times N$ board $A$, a $D\times D$ stamp $S$, and a target board $T$. Colors are integers from $0$ to $C-1$. Color $0$ is treated exactly like every other color.

Coordinates are zero-based, with $(0,0)$ at the top left. Row indices increase downwards and column indices increase to the right.

Each operation consists of the following steps.

• Choose the top-left corner $(x,y)$ of a $D\times D$ region and $r\in\{0,1,2,3\}$.

The stamp must fit inside the board. Regions may overlap, and the same region may be used repeatedly. Moving and rotating the stamp do not cost additional operations. The rotation in each operation is relative to the reference orientation, not to the previous operation.

The position inside the selected region corresponding to stamp cell $(u,v)$ is defined by

For every stamp cell with $R_r(u,v)=(p,q)$, exchange $S_{u,v}$ with .

Perform at most $K$ operations to maximize the number of cells whose final color agrees with $T$. The target does not change. Intermediate boards and the final stamp do not contribute to the score. You may perform zero operations. A perfect match is not guaranteed to be possible.

Scoring

Let $M$ be the number of matching cells on the final board. This input earns $P=\left\lfloor10^6M/N^2\right\rfloor$ points. Your total is the sum over 40 evaluation inputs, with a maximum of $$ points. Invalid output or a resource-limit failure earns zero for that input only. Scores do not depend on other contestants or any reference solution. Equal totals share the same rank.

Replay tool

Open Stamp replay (new tab)

Each input file contains one instance in the following format.

$N\ D\ C\ K$ $A_{0,0}\ A_{0,1}\ \cdots\ A_{0,N-1}$

Print the operation count $L$, followed by each operation $x_i,y_i,r_i$ in order.

• $3\le N\le30$.
• $D\in\{2,3\}$, $D\le N$.