My high-level approach was the following: I'll look one problem at a time, and I'll do it then and there if I can come up with a solution in 10s. If not, I'll revisit it. I like this approach better than looking at all of the problems first since I can have just one thing on my mind at any time.
The first problem is essentially pattern matching. You're given a 4x4 board and you want to see if any rows, columns, and major/minor diagonal matches some string. I was feeling lazy, so I hardcoded the patterns and did a brute force search. Not too bad.
I couldn't think of a brain-dead solution for the second problem, so I skipped it for now.
The third problem required finding palindromes that are squares of palindromes. Given that this is in a programming contest, of course there will be some cleverness involved. I then looked at the input sizes. There were not just two, but THREE (a first!) inputs, the first one with a bound of 1000 (trivial), the next with a bound of 10^14 (decent, I can just do it with 64-bit integers, or so I thought), and the third had a bound of 10^100 (excuse me?). I first pooped some code for the small case, which happily ran in time. I then realized that I can adapt this for the large case, but was unconfident about constant factors, which may or may not destroy me.
I decided to port the code to C++ to play it safe, or so I thought. "Clearly C++ is much faster than Python, so that should save me, right?" said naïve me. I coded it up, generated some random input data, tested the code using that, and found that it ran in time. "Sweet." I then downloaded the large-1 test case, computed the results, and uploaded my answers.
I wasn't too sure what to do for the largest test case. I thought computing the palindromic palindrome-squares indefinitely was a good idea to figure out a general pattern, since I noticed only ~1% of numbers less than 1000 satisfied the condition and some very small fraction of numbers less than 10^14 satisfied the condition. From the ongoing run, I noticed that there were some more numbers less than 10^14 that my C++ program failed to find. "This is weird," I thought. After a while, I noticed that one of my helper functions took an int instead of an uint64_t. I changed it, reran my code, and verified that I found my error: one of my function arguments was an int, instead of an unsigned long long. Good game.
The fourth problem at first looked like a search problem. Upon glancing at the input sizes, I figured there had to be some dynamic programming involved. I was feeling pretty tired at this point, so I shut my laptop and fell asleep.
Since the contest happened during a subset of MIT's Campus Preview Weekend (which I happily attended three years ago; more on this year's CPW in another post), I didn't work on Code Jam until about T-30min. I felt somewhat annoyed about not having solved problem 2, since all of my other friends solved it (bad logic, I know). Apparently I understood the concept of the solution, from talking afterwards to a person who solved it, but I struggled to put 1 and 1 together to make 2. Thus, I pooped something that would solve the [overconstrained] small test at T-8min, which happily passed.
The qualification round ended soon enough. As expected, I got all but my problem 3 large right. Not bad, for being a few years out of practice.
No comments:
Post a Comment