mineraldeposits (BOI contest)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: interactive
Algorithms: set, geometric transformation, bipartite matching, interactive

# Mineral deposits
Problem ID: mineraldeposits

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.

![](_page_0_Picture_4.jpeg)

Eroding mud face exposing new minerals. Photo: Michael D. Turnbull, licence: CC BY-SA.

Say you sent a wave of $d$ probes to the surface at coordinates $(s_j, t_j)$ for

$1 \le j \le 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 "? s1 t1 · · · sd td", where the number $d$ of probes in this wave must satisfy $1 \le d \le 2000$. The values $(s_i, t_i)$ are interpreted as the coordinates of the $i$th probe and must satisfy $-10^8 \le s_i \le 10^8$ and $-10^8 \le t_i \le 10^8$. The response is a single line with $k \cdot d$ integers in non-decreasing order: all pairs of Manhattan distances between the mineral deposits and the 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, ... 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 \le b \le 10^8$, $1 \le k \le 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 | 9 | $k = 1, w = 10^4$ |
| 2 | 19 | $w \ge 500$ |
| 3 | 11 | $w \ge 210$ |
| 4 | 7 | $w \ge 130$ |
| 5 | 20 | $w \ge 3, b \le 10^4$ |
| 6 | 15 | $w \ge 3, b \le 10^7$ |
| 7 | 19 | No further constraints |

## Example

![](_page_1_Figure_1.jpeg)

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.

![](_page_1_Figure_6.jpeg)

Starter code:
interactor.cpp: // Adapted from boi2023_tests/mineraldeposits/output_validators/validate.py
// Author: HeRaNO

#include "testlib.h"

const int INF = 100'000'000;

int main(int argc, char *argv[])
{
	registerInteraction(argc, argv);
	int b = inf.readInt();
	int k = inf.readInt();
	int w = inf.readInt();
	std::vector<std::pair<int, int>> hidden_dots;
	for (int i = 0; i < k; i++)
	{
		int x = inf.readInt();
		int y = inf.readInt();
		hidden_dots.push_back({x, y});
	}

	int total_probes = 0;
	int queries = 0;
	printf("%d %d %d\n", b, k, w);
	fflush(stdout);

	while (true)
	{
		std::string opt = ouf.readToken("[?!]", "opt");
		if (opt == "?")
		{
			++queries;
			if (queries > w)
				quitf(_wa, "Too many rounds");
			std::vector<int> probe_coordinates;
			while (!ouf.seekEoln())
				probe_coordinates.push_back(ouf.readInt(-INF, INF, "coordinate"));
			if (probe_coordinates.size() % 2 == 1)
				quitf(_wa, "Got %d tokens, expected an even number", (int)probe_coordinates.size());
			int d = probe_coordinates.size() / 2;
			if (!(1 <= d && d <= 2'000))
				quitf(_wa, "Expected at least 1 and at most 2000 probes, got %d", d);
			total_probes += d;
			if (total_probes > 20'000)
				quitf(_wa, "Expected at most 20_000 probes in total, currently has %d", total_probes);
			std::set<std::pair<int, int>> probed_points;
			for (int i = 0; i < d; i++)
				probed_points.insert({probe_coordinates[2 * i], probe_coordinates[2 * i + 1]});
			if (probed_points.size() < d)
				quitf(_wa, "Duplicate probes");
			std::vector<int> dis;
			for (auto p : probed_points)
				for (auto q : hidden_dots)
				{
					int x, y, s, t;
					std::tie(x, y) = p; std::tie(s, t) = q;
					dis.push_back(std::abs(x - s) + std::abs(y - t));
				}
			std::sort(dis.begin(), dis.end());
			for (int i = 0; i < dis.size(); i++)
				printf("%d%c", dis[i], " \n"[i + 1 == dis.size()]);
			fflush(stdout);
		}
		else // opt == "!"
		{
			std::vector<std::pair<int, int>> answer_dots;
			for (int i = 0; i < k; i++)
			{
				int x = ouf.readInt(-INF, INF, "ans_x");
				int y = ouf.readInt(-INF, INF, "ans_y");
				answer_dots.push_back({x, y});
			}
			std::sort(answer_dots.begin(), answer_dots.end());
			std::sort(hidden_dots.begin(), hidden_dots.end());
			if (answer_dots != hidden_dots)
				quitf(_wa, "Wrong answer");
			break;
		}
	}
	quitf(_ok, "");
	return 0;
}

Grader code:
interactor.cpp: // Adapted from boi2023_tests/mineraldeposits/output_validators/validate.py
// Author: HeRaNO

#include "testlib.h"

const int INF = 100'000'000;

int main(int argc, char *argv[])
{
	registerInteraction(argc, argv);
	int b = inf.readInt();
	int k = inf.readInt();
	int w = inf.readInt();
	std::vector<std::pair<int, int>> hidden_dots;
	for (int i = 0; i < k; i++)
	{
		int x = inf.readInt();
		int y = inf.readInt();
		hidden_dots.push_back({x, y});
	}

	int total_probes = 0;
	int queries = 0;
	printf("%d %d %d\n", b, k, w);
	fflush(stdout);

	while (true)
	{
		std::string opt = ouf.readToken("[?!]", "opt");
		if (opt == "?")
		{
			++queries;
			if (queries > w)
				quitf(_wa, "Too many rounds");
			std::vector<int> probe_coordinates;
			while (!ouf.seekEoln())
				probe_coordinates.push_back(ouf.readInt(-INF, INF, "coordinate"));
			if (probe_coordinates.size() % 2 == 1)
				quitf(_wa, "Got %d tokens, expected an even number", (int)probe_coordinates.size());
			int d = probe_coordinates.size() / 2;
			if (!(1 <= d && d <= 2'000))
				quitf(_wa, "Expected at least 1 and at most 2000 probes, got %d", d);
			total_probes += d;
			if (total_probes > 20'000)
				quitf(_wa, "Expected at most 20_000 probes in total, currently has %d", total_probes);
			std::set<std::pair<int, int>> probed_points;
			for (int i = 0; i < d; i++)
				probed_points.insert({probe_coordinates[2 * i], probe_coordinates[2 * i + 1]});
			if (probed_points.size() < d)
				quitf(_wa, "Duplicate probes");
			std::vector<int> dis;
			for (auto p : probed_points)
				for (auto q : hidden_dots)
				{
					int x, y, s, t;
					std::tie(x, y) = p; std::tie(s, t) = q;
					dis.push_back(std::abs(x - s) + std::abs(y - t));
				}
			std::sort(dis.begin(), dis.end());
			for (int i = 0; i < dis.size(); i++)
				printf("%d%c", dis[i], " \n"[i + 1 == dis.size()]);
			fflush(stdout);
		}
		else // opt == "!"
		{
			std::vector<std::pair<int, int>> answer_dots;
			for (int i = 0; i < k; i++)
			{
				int x = ouf.readInt(-INF, INF, "ans_x");
				int y = ouf.readInt(-INF, INF, "ans_y");
				answer_dots.push_back({x, y});
			}
			std::sort(answer_dots.begin(), answer_dots.end());
			std::sort(hidden_dots.begin(), hidden_dots.end());
			if (answer_dots != hidden_dots)
				quitf(_wa, "Wrong answer");
			break;
		}
	}
	quitf(_ok, "");
	return 0;
}

Setup script:

Evaluation script: