Project Euler 184

Here it is.

Between fellowship applications and my senior design course, I've been quite busy, but I managed to sneak this one in.

Other people managed to find some insanely fast solutions, but I am fairly fond of my O(n^2) (n is number of points) solution - it is elegant and only relies on simple arguments.

It involves scoring "arms" or "angles" formed by triplets of points, depending on where origin is relative to the arms.  E.g. is it on one of the arms?  Directly behind?  Would the origin be "scooped up" by the arms if we were to extend them arbitrarily?

Hint -- the argument is fairly similar to the solution for Div 1 C of this Codeforces competition.  ;)

Happy solving.
-S

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.