# Cheesing (?) BOI 2023 mineral deposits
## Subtasks
The subtasks are well-explained in the official slides. The purpose is to explain a working 100-point solution in greater detail. https://github.com/thorehusfeldt/boi23-development/blob/master/mineraldeposits/spoilers/slides.pdf

## $K^2$ candidates, 2 queries
First, query $(\infty,\infty)$. then, $(-\infty,\infty)$, where $\infty=10^8$. Each of these queries give us up to $k$ lines, on which all deposits must lie. The lines of the two queries will be orthogonal, so we can intersect them for potential locations. This gives us at most $K^2$ candidates for locations of the deposits. In other words, the deposits *must* be located in one of these $K^2$ locations.

## $4*K^2$ candidates, 1 query
To get full points, we first start with getting few candidates. However, we can no longer afford asking $(\infty,\infty)$ and $(-\infty,\infty)$ separately. Therefore, we will ask both of them in the same query. We now don't know which distance belongs to which point, so we will be forced to try all pairs of the $2K$ distances, $2K \cdot 2K=4K^2$.

## Solving the problem
Denote the set of $4K^2$ candidates by $C$.
The goal is to now deduce the $K$ of these that are real mineral deposits. If we ask for a particular $P$, we know that it will give back a subset of size $K$ of the $4K^2$ distances. If we were super lucky and all such possible distances were unique, the problem would be solved instantly. Sadly, a $P$ with all unique distances might not exist. To avoid interference between different $P$, we will choose the $P$ such that the possible distances are all disjoint.

How do we make deductions given the result? For each $P$, candidate points with the same distance to $P$ will be "grouped". For each group, we will know how many candidates are real deposits. Our deductions will be as follows: first, for all groups with 0 real deposits, we know that all candidates in them are not real deposits. We can thus remove them from other groups. Then, for every group where all of its members are real, we can know for certain that said members are real deposits. If even one is not real, we don't use it; it's too annoying to make such deductions, and the benefits are unclear. Using the information better than this is almost certainly NP-hard in general. Therefore, it seems better to focus our efforts on choosing good query points.

By trial and error, it turns out that using a mix of the following kinds of $P$ suffices:
- Uniformly random
- Close to the corners
- Close to the sides of the grid
- The coordinate of some candidate, with $x$ and $y$ $\pm$ random number $\in [0, 5]$.

Around half of the $P$ are chosen arbitrarily among these. The other are chosen by maintaining the smallest group that each candidate is present in, and only adding a $P$ if it decreases this value for some candidate.

For maximum randomness, I created a function for generating the $x$ and $y$ component independently, which means that if there is a candidate with coordinates $(a,b)$, I might also consider the $P$ with coordinates $(a,a)$, $(b,b)$, $(b,a)$.

## Takeaway
This solution extremely cheesy. But it's also extremely reasonable; it seems very difficult to actually kill it. "Most of the time", the groups are going to be small, and we have a lot of wiggle room. In order to develop such a solutions quickly, it's important to be able to quickly iterate by generating data and seeing whether your changes took you closer or further to a working solution.