this post was submitted on 01 Dec 2023
17 points (100.0% liked)
NotAwfulTech
364 readers
1 users here now
a community for posting cool tech news you don’t want to sneer at
non-awfulness of tech is not required or else we wouldn’t have any posts
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
11
a,b
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.
Love ur premature optimization
Watch me as I solve P=NP and then find out I was only supposed to solve fizzbuzz