Interviewstreet: Lucky Numbers

Here is the problem description.

This one was great!  Earlier today I was having a fair amount of difficulty with the supposedly simpler Median problem, which shouldn't have been too bad -- for some reason I kept failing three test cases, how frustrating! -- but I am now much happier that I have a solution to Lucky Numbers.  :)

The key was to formulate the problem in terms of dynamic programming.  We don't actually have to range over all of the numbers -- we can knock out lots of numbers all at once by recognizing that, when we have a set of D digits which may all range freely from 0 to 9 (inclusive), we can find the number of lucky numbers by examining sets of D-1 digits (for which we establish an a priori sum of digits and sum of squares of digits based on the value of digit 1 of D).

Of course, this does not quite do the trick, as our inputs A and B are never just 0 and {9}*n for some n -- they are generally more restrictive.  Fortunately, we can use the aforementioned precomputation to efficiently handle this more restrictive case.  ;)

Interviewstreet: Grid Walking

This one was really fun! Here's the problem description.

My approach involved the following ideas:

1. We can precalculate the number of ways to stay within a one dimensional segment of a particular length, starting at a particular place, and using a particular number of moves.
2. From here, the number of ways to stay within D dimensions of the grid using M moves can be found by going through all possible ways of splitting M into two chunks (say, k and M-k) and interleaving the k moves we use to stay within dimension D (at starting position x_D) with the number of ways to stay within D-1 dimensions using M-k moves.

Of course, there is a trick in counting the number of ways to interleave the moves to stay within 1 dimension with the number of ways to interleave the moves to stay within the remaining D-1 dimensions.  ;)

Say for every move in dimension D, we write a 0.  For every move in the remaining D-1 dimensions, we write a 1.  The number of interleavings is, of course, the same as the number of possible binary strings composed in this fashion.  If we have M total moves, k of which are made in dimension D, this gives, of course, M choose k possible interleavings.

But we have to give the output modulo 10^9 + 7!  How do we calculate M choose k modulo this number?  Fortunately p = 1E9 + 7 is prime, so the group of integers modulo p gives a field.  This means that we can simply calculate M choose k (mod p) as M! * (k!)^-1 * ((M-k)!)^-1, all modulo p, of course. Since p is prime we are guaranteed that the numbers k! and (M-k)! have multiplicative inverses. I used the extended Euclidean algorithm to get these, although I believe you could just as well raise them to the p-2 power (which, by Fermat's theorem, gives the multiplicative inverse).

Whew!  It's great to see a problem that combines concepts from dynamic programming, discrete math, and number theory!

Hello, World

This blog has no relation to the Scottish youth volunteering organization of the same name.  I created this blog way back in January 2012 as a way to chronicle my study abroad experience at the University of Edinburgh... and promptly forgot about it.  Although my time in Scotland has come to an end, I am nevertheless quite fond of this blog title, and I would hate to see it go to waste.  Thus, I hope to keep this blog updated with key events, math / cs, and random musings... basically the usual stuff from a cs nerd.  Maybe somebody will find it entertaining.