Aaron N. Tubbs bio photo

Aaron N. Tubbs

Dragon chaser.

Twitter Facebook Google+ LinkedIn Github

And so it continues! I went ahead and fixed my mime types too, so the solutions will appear in the browser.

10183 – How Many Fibs?

Feeling lazy, I decided not to use an arbitrary precision integer arithmetic system, even though I developed one as practice for the previous chapter. Instead, I just used my 40k source limit up by hard-coding the first 500 fibonacci numbers. Yes, I’m just that awesome.

10213 – How Many Pieces of Land?

I suck at combinatorics. I couldn’t figure this out and had to read the forums to solve the recurrence relation. NB source code for the solution is missing the BigInt code. Of course, maybe I’m not as stupid as I think, and the BigInt library I was using at first was completely broken. Who knows.

10198 – Counting

Whee, recurrence relations and dynamic programming. Solution is missing BigInt if you try to compile it.

10157 – Expressions

Determining the initial relationship between n and d was, again, beyond my capability. I just seem to suck at recurrences. Trolling through the forums, I found an explanation of a recurrence generated by one individual. Again, the work to deduce the solution was far beyond my ability. This depresses me. I implemented said solution, and everything seemed to work correctly. My code was massively slow, though, with all of my time spent in big integer multiplication. I spent the better part of a week thinking over the solution and trying to come up with a faster way, avoiding multiplications. I found some really interesting properties that develop in the solution triangle, by going Knuth on the problem (that is to say just staring at it for a long time, waiting for God to hand me some bit of insight). Spent a decent amount of time playing with OEIS and became intimately familiar with A000225, A033537, A000108, etc.

So I gave up.

In better spirits early this morning, I decided to rewrite my solution in Java, since it has built-in BigInteger support that is, I assume, superior to the version I’m using in C++. Sure enough, the judge input solves in under a second. So there you have it, my first programming challenge solved in java instead of C++. Having not touched java in about five years, I’d forgotten everything. For example, I’d forgotten how much I hate writing Java.