Subtask 1

We can conjecture that for any random set of ~X~ robots, there is a decent probability that a valid solution exists. For a given set, we can find a solution (or determine that there is no solution) by brute forcing through all ~2^X~ ways to turn robots on and off. Whilst we have not found a solution, we can repeat this process for another set of ~X~ robots.

Time complexity: ~\mathcal{O}(N + 2^X)~

Subtask 2

Note that there are at most ~1001~ different horizontal lines that the RoboThieves could be hiding on. By the pigeonhole principle, there exists a horizontal line containing at least ~\lceil \frac{10^6}{1001} \rceil = 1000~ robots. Thus, we can always choose ~X~ robots to leave enabled which exist on the same horizontal line.

Let's generate a list of the enabled robots, sorted by their ~x~-coordinate. Note that for each robot, in each network, the set of robots that it is connected to form a contiguous range in this list. Therefore, it suffices to turn every third robot in this list on, and turn the remaining robots off.

Time complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N + X \log X)~

Subtask 3

Our construction for subtask 2 can be generalised to sets of robots other than straight lines. If we sort our set of robots by their ~x~-coordinate, then our construction will work as long as the sequence of ~y~-coordinates in this sorted list is non-increasing or non-decreasing. Let us call such a set a good set.

As it turns out, if all ~10^6~ robots lie on their convex hull, then we are guaranteed that exists a good set with at least ~250\,001~ robots, well more than enough. The proof of this is simple and is left as an exercise to the reader. We can obtain this good set by any method, such as repeatedly randomly picking ~X~ adjacent robots on the convex hull.

Time complexity: ~\mathcal{O}(N \log N)~

Subtask 4

Actually, a good set always exists. Let's sort all ~10^6~ robots by their ~x~-coordinate, and consider the sequence formed by their ~y~-coordinates. Generalising the Erdős–Szekeres theorem for repeated values, we see that there exists a non-increasing or non-decreasing subsequence with at least ~\sqrt{10^6} = 1000~ robots. We can then perform the same construction on this good set as before.

Time complexity: ~\mathcal{O}(N \log N)~