Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Google Code Jam 2013 Qualification
Author Message
mirhagk

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.

Panphobia

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

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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 2 of 2  [ 18 Posts ]
Goto page Previous  1, 2
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: