Alright, I’ve started chapter two. I’ll just keep editing this post with progress, if/when I make any.
10038 was very easy, accepted first try without any testing ahead of time. The solution is uninteresting.
10315 is a terrible problem. I did it, but it took me two weeks because I kept procrastinating, because I wanted nothing more than to not work on this particular challenge. My solution is a bag of hell, and I hope never to look at this problem or another like it again. It bothers me because it’s a whole bunch of little stupid unrelated things you have to get right, not one of which is at all difficult or interesting. Yuck. What I don’t get is it’s a chapter about data structures, but I can’t figure out a good reason to leverage data structures on this problem. Maybe I’m missing something clever. Accepted on second submission.
10050 reminds me an awful lot of FizzBuzz. My solution wasn’t particularly classy, but it compiled the first time I tried and accepted on first submission. I used a fancy data structure called an array, so we’re still 0 for 3 on needing anything clever in this chapter.
843 was an awesome problem. Not because it was anything special, but because it was the first problem that required the slightest amount of actual, well, thinking. There weren’t any real gotchas, just a matter of “think the problem through, and how you want to approach it.” I’m pleased with the speed of my solution, though there is room for improvement. At least conceptually, I used a stack, so at least I’ve finally found an excuse to travel beyond arrays. My submission worked fine the second time (had a stupid backtracking bug the first time). For some reason, I pass the UVA judge but fail the book’s judge. I don’t really care enough to go back and massage it into working for the book’s judge; but if I can find a breaker case in the future I’ll revise it.
Stack ’em Up
10205 was easy. I was hasty because I hated the problem from the start and wrote a stupid initial solution, and then stared at it forever because I was overconfident that I was doing the right thing. Hubris, it gets you every time. My final solution was accepted the first time I saved it, as I just started over from scratch without being stupid. All of that said, this problem is still trivial, and does not belong in this chapter. Put it back in the previous chapter with all the other multidimensional array problems, there is nothing interesting here.
I hated 10044 in the face. It took me almost two weeks (not working constantly, but casually over several nights/weekends) to get this one. First off, there’s a parsing issue, which was what killed my first solution, which would only result in wrong answers, but I didn’t realize it at the time. See, there’s malformed input with only a surname and no front initials, and my parsing code was barfing on it. Otherwise that solution was fine, as a quick hack it together tree traversal thing. So, I decided to write a robust string splitter and adjacency matrix graph representation. And an adjacency list graph representation. APSP and SPSP implementations. Optimzations. Didn’t matter. No matter what, TLE on every submission.
I was stunned. Graph algorithms are about as fast as I can solve this problem, but I was still running into time bounds.
So, I tore out most of the code and started figuring out the input size through writing code that would generate a segmentation fault on purpose if certain conditions were exceeded.
And, sure enough, the problem input is massive. With my elegant implementation (elegant because it’s generic, portable, and still “fast”), I was spending nearly 1 of the 3 allowed seconds just processing input data. Yikes.
So I rewrote it as garbage code again, and that solution got an accepted. To keep parsing fast I pre-allocated a bunch of character buffers to dump input into, used a hash map for node lookup, and used a set to manage duplicate links.
But, I hate this problem because it has a nasty parsing issue, and because it discourages the creation of an elegant approach that is just as fast algorithmically but much slower on the input data. .46 seconds runtime. I have no idea how somebody writing Java could actually be expected to solve this sort of problem.
10258 was easy. So easy that it took four tries. Stupid sorting error the first time. And the second time. And the third time. Duh. Got it on the fourth. Hubris, Mr. Bond, hubrus. My solution is uninteresting.
10149 doesn’t make any sense to me in this chapter. I don’t think there is a P solution (well, it’s O(1) since we know the size of the problem space, right? right?), and the “hint” that maybe I can make some greedy optimizations doesn’t strike me as accurate in all cases. So I solved it using simulated annealing instead, and my solution completes in about 1.7 seconds on the judge. I was stuck for a little while because my original implementation produced nearly correct results, but took too long. Turns out my implementation of simulated annealing made a minor but fatal error, by always doing a state change in conjunction with best answer storage, when in fact they should be treated as independent decisions. Oops. After that, it was just tracking down a small premature (and incorrect, as always) optimization in my scoring routines, and turning the iterations down until I got a judge runtime under 3 seconds; I could probably tune further, but I start entering into the “I have no real confidence this will get the right answer consistently” zone.