Problem B
Mineral deposits
You handle signal processing for an extra-terrestrial mining company, and your vessel is currently approaching an asteroid. Preliminary scans show the presence of $k$ mineral deposits on the asteroid, but their precise locations are unknown.
The surface of the asteroid can be seen as a grid of integer coordinates. Each of the mineral deposits is located at unknown integer coordinates such that the $i$th deposit has coordinates $(x_ i, y_ i)$ with $-b \le x_ i \le b$ and $-b\le y_ i \le b$ for some integer $b$ corresponding to the size of your initial scan.
To determine the precise locations of the mineral deposits, you may send probes to the surface of the asteroid. The probes are sent out in waves of several probes at once.
Say you sent a wave of $d$ probes to the surface at coordinates $(s_ j,t_ j)$ for $1\leq j\leq d$. When a probe arrives at its coordinates, it determines the Manhattan distances to each of the $k$ mineral deposits and sends the distances back to the ship. All data packets arrive at the same time, and it is not possible to determine which probes returned which distances. Thus the wave returns the $k\cdot d$ integer distances
\[ |x_ i-s_ j| + |y_ i - t_ j| \qquad \text {for all } i \in \{ 1,\ldots ,k\} \text { and } j \in \{ 1,\ldots ,d\} \, . \]You need to minimise the number of waves of probes that is sent to the surface.
Interaction
This is an interactive problem. Interaction begins with you reading a single line containing three integers $b$, $k$, and $w$: the grid’s boundary $b$, the number $k$ of mineral deposits, and the maximum number $w$ of waves you may send.
You then ask at most $w$ queries, each corresponding to a wave. A query consists of ? followed by $2d$ integers separated by space, such as “? $s_1$ $t_1$ $\cdots $ $s_ d$ $t_ d$”, where the number $d$ of probes in this wave must satisfy $1\leq d\leq 2000$. The values $(s_ i,t_ i)$ are interpreted as the coordinates of the $i$th probe and must satisfy $-10^8 \leq s_ i \leq 10^8$ and $-10^8 \leq t_ i \leq 10^8$. The response is a single line with $k \cdot d$ integers in non-decreasing order: the Manhattan distances between all pairs of mineral deposits and probe coordinates. The total number of probes across all waves may not exceed $2\cdot 10^4.$
Interaction ends with you printing a single line consisting of ! followed by $k$ points $x_1, y_1, x_2, y_2, \ldots x_ k, y_ k$, separated by space. This must be your last line of output.
Your submission is considered correct if you print all locations of the mineral deposits. You may print them in any order.
Constraints and Scoring
We always have $1\leq b \leq 10^8$, $1 \leq k \leq 20$, and $2 \le w \le 10^4$.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Constraints |
|
$1$ |
$16$ |
$k = 1, w = 10^4$ |
|
$2$ |
$19$ |
$w \ge 500$ |
|
$3$ |
$11$ |
$w \ge 210$ |
|
$4$ |
$13$ |
$w \ge 130$ |
|
$5$ |
$14$ |
$w \ge 3$, $b \le 10^4$ |
|
$6$ |
$14$ |
$w \ge 3$, $b \le 10^7$ |
|
$7$ |
$13$ |
No further constraints |
Example
![\includegraphics[width=.6\textwidth ]{img/sample1.pdf}](/problems/boi23.mineraldeposits/file/statement/en/img-0002.png)
In this example, there are $k=2$ mineral deposits at positions $(1,2)$ and $(-3,-2)$, shown as red stars. In the first wave, you might send $d=3$ probes to $(-4,-3)$, $(-1, 0)$, and $(2,-1)$, shown as black dots. This wave would return the $6$ distances
\[ 2, 4, 4, 4, 6, 10\, . \]In the next wave, you might send $d=2$ probes to $(1,2)$ and $(0,-2)$. This wave would return the $4$ distances
\[ 0, 3, 5, 8\, . \]| Read | Sample Interaction 1 | Write |
|---|
4 2 10
? -4 -3 -1 0 2 -1
2 4 4 4 6 10
? 1 2 0 -2
0 3 5 8
! 1 2 -3 -2
