Problem 1: Expogo
I wrote a relatively simple implementation using search with memoization (caching) and a bit of pruning of implausible search regions, and that was sufficient for all three data sets. According to the after-round summary, there's also a constructive solution. I had suspected so, but couldn't find it.
Problem 2: Blindfolded Bullseye
This is a nice search problem that involves some geometry. I think I started with a reasonable search strategy, but then ran out of time when it came to doing the geometry... So I gave up trying to find a "good" solution, and coded the trivial brute-force solution for solving the easiest data set. That was worth only 3 points, but those 3 points improved my final ranking by more than 1'000.
Problem 3: Join the Ranks
This didn't look too impossible, but given the high amounts of points awarded for this, I suspected that this would be beyond my skills and decided to focus on the other two problems.
With a full solution for problem 1, a half(?)-done good solution for problem 2, and the few extra points for the trivial data set of problem 2, I finally ranked #1996 [edited for final result]. As only the first 1500 contestants qualify for round 2, this was not sufficient. But I'm quite happy with how it went, and am looking forward to round 1C, about two weeks from now. And unlike during the qualification round, I didn't run into any issues with coding in Lisp—even though I haven't been using it professionally for several years now.
Post a Comment