Breakun's blog

By Breakun, 6 weeks ago, In English,

I participated in this year's Facebook Hacker Cup and have enjoyed all the problems so far. The only problem I couldn't solve during the contest was the last problem of Round 2 named "Seafood" (link). Facebook always uploads solutions right after the contest, which I'm thankful for, so I checked the solution for that problem. However, I couldn't see why the solution works just from their description. Maybe I'm not thinking through it enough, but I found it hard to justify their approach in mathematical rigor. So I picked up key ideas from their description and filled out the details. I'm writing this for myself, and it turns out to be more complicated than I thought but I hope this helps some folks out there. If you have any simpler solution/description I'm happy to know.

Here is a short synopsis of the problem. You start at position $$$0$$$ of a number line and move around. There are clams and rocks on the number line. Each clam/rock have distinct positive coordinates and also its own strength as a number. When you are on a position where a clam is placed, you can take the clam immediately and you can hold multiple clams at a time. When you are on a position where a rock is placed, you can use the rock to break open any clam you have with lesser strength. Your goal is to open all the clams in minimum distance moved (or determine that you can't). You should do this in quasilinear time over the number of clams+rocks.

My attempt (You can skip this)
Solution
Source Code
 
 
 
 
  • Vote: I like it
  • +62
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Writing this took me damn 6 hours. Was a good practice for technical writing though. I still need to learn how to write faster and clearer so any feedback is welcome.