Google Code Jam 2013 Qualification

[mirhagk]

Wow that is quite an awesome solution Demonwasp.

I don't know how you'd formally prove your assumption, but it does make sense.

You write some really awesome solutions to the problems, they are clear and informative. I hope I've learned some extra tricks for next round now.

[Panphobia]

So essentially you are checking all 2 * 3^(n/2-1) permutations of digits 0,1,2 to check for palindromic squares?

[DemonWasp]

Sort of. However, there are two problems:

First, for n = 10^100, the recursion will only check 2 * 3 ^ (fourth_root(n)-1) permutations. However, that problem space is still 10^25, which is still too big.

Second, the part that makes it finish before we are consumed by an expanding Sun, is that most of the recursion stops very early: if I know that the half-base '22' (--palindrome--> '2222' --square-> 4937284) isn't valid, then I don't need to continue building on it (half-bases '220', '221', '222', '2200', ... cannot be valid).

That seriously limits the amount of recursion required. As mentioned, there are only 41551 such fair-and-square numbers between 1 and 10^100, and since recursion is curtailed early, there will be at most 41551 checks that "pass" and result in recursion, rather than the (very very roughly) 10^25 recursions required without that check.