Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Google Code Jam 2013 Qualification
Index -> Contests
Goto page Previous  1, 2
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
mirhagk




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
Panphobia




PostPosted: 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?
DemonWasp




PostPosted: 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.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 2  [ 18 Posts ]
Goto page Previous  1, 2
Jump to:   


Style:  
Search: