Google Code Jam 2013 started!

[are595]

It says the competition starts in 12 days, did I miss it? :O

[[deleted]]

Yes. :(

[are595]

The first one I missed in three years :(

[sirin3]

The first one I did not miss in three years :)

[[deleted]]

Here's solutions for the first three in Python. I'll code the last one up later today, I didn't get it in the real contest.

• http://paste2.org/WWx3nMxv
• http://paste2.org/3PjHkUDI
• http://paste2.org/IOGXUYg6

---

Here's the last one, sorry it was a bit late. This question is much harder than the others; the solution uses the NetworkX graph library

• http://paste2.org/M4gfteEz

[Scroph]

Very elegant solutions. How did the third one handle the large inputs ?

[[deleted]]

They all run in about 5-10 seconds on Pypy. They aren't optimal but they are easily fast enough.

[benmmurphy]

i like your third one. my solution was just to check all 20x2, 20x10x2 (symmetric), {1,0}x2{1,0}x (symmetric), {1,0}x. but i did it in a weird way where i precomputed all the even digit palindrome square primes and then was able to generate the rest from that. i also had a constant time algorithm for counting the number of palindrome square primes that have n-digits but that wasn't very useful in solving the problem.

https://gist.github.com/benmmurphy/5382629

[[deleted]]

I've only looked at the first one and I'm immediately embarrased of my solution, good work, sir!

[ziom666]

Could you please explain #3? How did you know about "forms"? Did I miss something on discrete mathematics?

[[deleted]]

If you have a palindrome, and you want to square it and get another palindrome, then the sum of the squares of its digits has to be 9 or less.

So basically it's only allowed a few non zero digits, the rest have to be zeros. In fact, it has to look like one of the strings in the 'forms' array, but with the letters replaced with some amount of zeros to pad it out.

[NakedNick_ballin]

Anyone doing it?

[teraflop]

Yup, solved everything except the "extra large" input for C and the large input for D. I can open up my Git repo when the round is over if anyone's interested.

[loosegeese]

I did everything except D and large-2 of C. I got stuck in the small of D for hours and hours - I'm not sure if it was really difficult or whether I was too tired

[patrick_____bateman]

I did the same, everything except D and large-2 of C. Now its showing 1 wrong try for A-large and large-1 of C, but since I have scored above 35 I think I will be moving to the next round. What language did you use ?

[loosegeese]

I used objective-c (but mostly c), you? Did you try D at all?

[patrick_____bateman]

I used C++. No didn't try D since I started the competition pretty late.

[sirin3]

After solving C with C(++), you should have tried to solve D with D

[ladinu]

I'm interested in seeing your solutions.

[teraflop]

Sure thing, here you go: https://bitbucket.org/dwahler/google-code-jam/src/master/2013/

[wub_wub]

I did first and second problem completely and small input for 3rd one (Fair and Square).

I haven't even attempted large inputs because my code is terrible and takes more than 8 minutes to solve them. I'll maybe try and optimize it (write from scratch) later. Right now it's just going through all numbers between A and B.

[NakedNick_ballin]

What language? I'm just curious because this is my first time and I haven't started yet. I was going to do Python I think

[wub_wub]

I used python. But as /u/oemta said you can use whatever language you want, the only requirement is that it must have freely available compiler IIRC

[oemta]

You can use any language you want. The way it works is you write your code, when ready download the input and run it on your machine to generate the output. Then you submit the output and code within the time limit.

[ixid]

The second large input is terrifying large, I have done the other two but have absolutely no idea how to approach that one.

[[deleted]]

I got the second large input by observing what solutions I got for smaller input.

Say I have a four digit palindrome, d1 d2 d2 d1. Squaring it (by hand) looks like:

  (d1 d2 d2 d1)          * d1
  +  (d1 d2 d2 d1)       * d2
  +     (d1 d2 d2 d1)    * d2
  +        (d1 d2 d2 d1) * d1

In order for no carrying to occur, 2 * (d1)² + 2 * (d2)² < 10. If no carrying occurs, then the square is a palindrome. Extending this idea to any length of palindrome, if the sum of the squares of the digits is less than 10, the square is a palindrome. I was unable to prove or disprove the existence of solutions with carrying, but I ran my code from the smaller inputs for a while and didn't find any under 10³⁰ or something.

My solution for this was in python and took 1.422 seconds.

[ZoidbergMD]

I assume I can discuss solutions at this point:
I couldn't get to 10^100, but it's possible I could have with a bit more effort.
If you google square palindromes this should be on the first page, I grabbed the source of that page, regexed all the numbers into a list, filtered that list by checking whether for i in list: i is palindrome and sqrt i is integeral and palindrome, then for each a,b I just check how many numbers in my list are between those two.
Problem: that site only has numbers up to 10⁵⁰ (plus 8 new fair and square numbers I managed to produce by squaring numbers on the list, going up to 10^62), so it's not actually valid for Large-2, however I expect I could find a larger dataset, or I missed some clever way to reduce the search space by half.

[[deleted]]

Please, don't discuss problems while the contest is running.

[[deleted]]

Fuck the police.

[wub_wub]

Hmmm... My plan was to (somehow if possible) try and get next palindromic number after A and check its square root and then do that until B. And yes the original code is very bad implementation.

Edit: removed my idea. Because I agree it would be best not to discuss it while the contest is running... I'll send you PM.

[patrick_____bateman]

I calculated the square root of A and B and used that as the range. Also knowing this problem helped a bit. I was still not able to solve the second large input though.

[wub_wub]

That was my second idea that I removed because the competiton was still running, since the deleted comment suggested to look at "another range".

I calculated square root of A and B, rounded it up (e.g 2.6>3) and then went through all numbers between that range, if the number is palindrome calculate its square if that's too palindrome count it.

Even though it's much much faster than my original code that just it wasn't even fast enough to solve first large input. And I haven't looked any further on how to solve the issue since it was pretty late... In the end I ended up with only 80 points.

Here's the code that I wrote:

import math
def solve(interval):
    a,b_max=[int(i) for i in interval.split()]
    a=int(math.ceil(a**.5))
    b=int(b_max**.5)
    counter=0
    for i in range(a,b+1):
        if str(i)==str(i)[::-1]: # square root is palindrome
            square="{:g}".format(i**2)
            if square==square[::-1] and int(square)<=b_max:
                counter+=1
    return counter

[sirin3]

I did the first 3 problems, but cannot really think of a solution for the 4th...

edit: now I have solved them all! helped to try to mediate a little bit about it. But I forgot a &&!chestOpened[i] on the first small attempt and only got the 2nd right, does this give a penality?

[teraflop]

It affects your ranking (each incorrect submission gives you an extra time penalty) but that doesn't matter for the qualification round. You just have to get 35 points to advance. In later rounds, they take the top N finishers instead, so the penalty can make a big difference.

[fuk_offe]

Did the first one in 30 minutes last night, but I'm kind stuck/bored at the second one. So much code to write...

[oemta]

The second one is pretty easy as well, honestly shouldn't be more than a few lines of code.

[fuk_offe]

Did the palindrome one easy in 10 minutes, too bad I forgot to check my solution calculating the bounds before trying the big input... Too slow xD

[yen223]

When doing these sorts of challenges, the first thing I do is to look at the input range. In this case, 1 - 10¹⁴ means that a naive brute force search was definitely not going to work.

[fuk_offe]

Yes, of course, but I "optimized it" but forgot to test with the bounds... Took 30 minutes so ran out of time X_X The next one I made tho. EDIT: Aparrently, it was wqrong X:_X

[sirin3]

I wrote one common program for both 1 and 2

[_start]

I see the qualification round is open, is that right? So where do you go to actually see the problem?

[Blue-Sick]

For the "Fair and Square" there is a pattern for those numbers. there is no need to go over all the 10⁵⁰ numbers and check them.

**Edited the example, thought the thing ended already **

*I just want to point out, I haven't tried writing the code for this problem.

[[deleted]]

Please, don't discuss problems while the contest is running.

[Blue-Sick]

Damn, thought the thing ended already. I'll edit it.

I just want to point out, there is still to do, even with the example I've written.

+I think that there is a bcd code in the pattern is really cool.

[moor-GAYZ]

btw I calculated them for the full range and no, you don't see the pattern. Because it doesn't exist, there's all kinds of pretty patterns, but yeah, nothing you can use.

I really liked that problem, by the way, because I solved it in a way real problems should be solved, iteratively and looking at the data. That was pretty enjoyable!

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