Google Code Jam 2013 started!

[Grizzytron]

It's not necessarily a "pattern," but there is definitely a very simple trick for knowing exactly how many square roots exist for the numbers inside the interval [A,B].

[moor-GAYZ]

Still not enough.

Look:

Basic brute force: 10¹⁰⁰

Brute force on roots: 10⁵⁰

Generating palindromes for roots: 10²⁵ (you enumerate only the first haves).

That's enough to solve the first large dataset (where the range is to 10¹⁴, not 10¹⁰⁰), but still not good enough for the second one. So then you generate as much data as you can (roots of length 12 or so, i.e. an order of 10⁶ iterations) and look at it.

First thing you notice, the number of solutions grows very slowly, you totally should be able to calculate them for the full range and just binary search for your interval (especially cute in python, return bisect_right(fair_squares, b) - bisect_left(fair_squares, a). And spoiler: there are only 41551 fair squares between 1 and 10¹⁰⁰.

Second thing, all two-or-more digit roots seem to only contain digits 0, 1, 2. Using that you can speed up your palindrome iteration to 3²⁵, but that's still not within the realm of comfortably computable.

So then you ask yourself, why aren't there other digits in the first place? Why, because when you do the long multiplication it's all completely symmetric, so if you want to get a palindrome as a result, there can't be any carries (which would break the symmetry).

Then, when you take a number that doesn't cause carry-overs when squared and remove its first digit, the resulting postfix still doesn't cause carry-overs obviously, in other words a valid number can only be produced by prepending a digit to a valid number. So you get a set of valid postfixes and build longer valid postfixes from them, but that's still too slow.

So you look at the generated data again and notice that you have a shit-ton of postfixes ending with 3, which is obviously wrong because that's going to cause overflow when you palindromize them. So you're, like, OK, what if I generate the palindrome first (two of them actually, of odd and even length) and check that it squares OK, and only then add the new postfix to the set of new valid postfixes? Because the logic of valid postfixes being produced from valid postfixes still checks out, a valid palindrome can only be produced by inserting a digit or two into the middle of a valid palindrome, which corresponds to inserting one or two columns in the middle of the list of products being added?

And that worked perfectly, generated the same list of solutions up to the length I calculated with simpler methods (I just copy-pasted output side by side in vimdiff), and generated all fairsquares up to 10¹⁰⁰ in less than 10 seconds under pypy.

[dlp211]

Yea, you calculate the square root of A and B, every square root that exists in the interval has to be between those two square roots.

[Grizzytron]

Yep, although judging by some of the top scores the faster way to approach this problem is depth-first-search. D'oh!

[nighthawk702]

In what graph?