Posted: Mon Apr 15, 2013 9:25 pm Post subject: RE:Google Code Jam 2013 Qualification
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.
Posted: Tue Apr 16, 2013 7:56 pm Post subject: RE:Google Code Jam 2013 Qualification
So essentially you are checking all 2 * 3^(n/2-1) permutations of digits 0,1,2 to check for palindromic squares?
Posted: Wed Apr 17, 2013 12:18 pm Post subject: RE:Google Code Jam 2013 Qualification
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.