a: So, I’ve been in the habit of skipping the flavour text and glossing over the prompt. This time, it hurt me badly.

I read the problem as follows: for N galaxies, find N/2 pairings such that the sum of distances is minimal.

At this point, I was like, wow, the difficulty has ramped up. A DP? That will probably run out of memory with most approaches, requiring a BitSet. I dove in, eager to implement a janky data structure to solve this humdinger.

I wrote the whole damn thing. The bitset, the DP, everything. I ran the code, and WOAH, that number was much smaller than the sample answer. I reread the prompt and realised I had it all wrong.

It wasn’t all for naught, though. A lot of the convenience stuff I’d written was fine. Also, I implemented a sparse parser, which helped for b.

b: I was hoping they were asking for what I had accidentally implemented for a. My hopes were squandered.

Anyway, this was pretty trivial with a sparse representation of the galaxies.