Author: Panphobia [ Sat Apr 13, 2013 7:06 pm ] Post subject: Google Code Jam 2013 Qualification Now that it is over, I just wanted to ask, which algorithms could you use for number 2? Also I got the small data set for number 3 by looping from ceil(sqrt(start)) to (int)sqrt(end) but that was too slow for the other large set, and I didn't even try on the third, what methods could you have used here? I know there are patterns like 11,101,1001,10001,100001...etc.., and for number 4, could you just brute force it? or would you need to come up with something smarter?

 Author: mirhagk [ Sat Apr 13, 2013 8:53 pm ] Post subject: RE:Google Code Jam 2013 Qualification Number 2 was the lawn mower problem, I'm assuming you mean number 3? And no number 4 was not brute forceable, that was my first implementation and it utterly failed (Took like 15 seconds for the first case in the small input). For my input every chest was opened with key 2, and there was like 15 chests, which gave me 15! ways to open it up, which is obviously not ideal. It was like so class to being a graph problem, and yet so far. I was trying to think of ways to develop heuristics to speed it up, but the problem is that lexographically smallest thing, which means you must search all chests smaller than and including the right chest. I'd like to see a solution as well.

 Author: ishidon [ Sat Apr 13, 2013 9:11 pm ] Post subject: Re: RE:Google Code Jam 2013 Qualification mirhagk @ Sat Apr 13, 2013 9:53 pm wrote:I'd like to see a solution as well. You can download other peoples solutions from the Scoreboard. Just check the Solution Downloaded box underneath the All Scores tab. https://code.google.com/codejam/contest/2270488/scoreboard#vf=1

 Author: Panphobia [ Sat Apr 13, 2013 9:34 pm ] Post subject: Re: Google Code Jam 2013 Qualification I saw some people use a breadth first search for it, but when I tried to code up a bfs for that question, the large input totally failed and gave me an error. But the small file worked just fine.

 Author: Panphobia [ Sun Apr 14, 2013 3:19 pm ] Post subject: RE:Google Code Jam 2013 Qualification You should have taken part in the contest, and could I see your java implementation, I did a naive bfs for this question, and it totally bombed the large input.

 Author: DemonWasp [ Sun Apr 14, 2013 4:47 pm ] Post subject: Re: Google Code Jam 2013 Qualification The code is attached. I use lombok (http://projectlombok.org/) so if you aren't set up for that, you'll have to generate some getters/setters for the Chest class yourself.

 Author: mirhagk [ Sun Apr 14, 2013 5:52 pm ] Post subject: RE:Google Code Jam 2013 Qualification I did the naive solution without the is-viable check, which failed on the small input. I had thought about the problem as a graph, and basically came up with the is-viable check, I just didn't think long enough about it to realize that adding that check to each recursive part would greatly reduce the branches I'd need to check. I wish I had had more time this weekend, but I have this stupid calculus exam tomorrow morning at 9am, oh well at least the next round is after all my exams.

 Author: Panphobia [ Sun Apr 14, 2013 6:43 pm ] Post subject: RE:Google Code Jam 2013 Qualification Also how the hell would you do arithmetic on numbers that go up to a googol, like on question 3 large data set

 Author: DemonWasp [ Sun Apr 14, 2013 7:11 pm ] Post subject: RE:Google Code Jam 2013 Qualification In Java, java.math.BigInteger; in other languages, find something similar. Some languages (including, I think, Python) support arbitrarily-large integers "natively".

 Author: Panphobia [ Sun Apr 14, 2013 7:13 pm ] Post subject: RE:Google Code Jam 2013 Qualification that would time out no? there are some patterns with palindromic squares, so couldn't you make a recursive solution?

Author:  Zren [ Sun Apr 14, 2013 8:19 pm ]
Post subject:  Re: RE:Google Code Jam 2013 Qualification

DemonWasp @ Sun Apr 14, 2013 7:11 pm wrote:
In Java, java.math.BigInteger; in other languages, find something similar. Some languages (including, I think, Python) support arbitrarily-large integers "natively".

That's one thing I love about python. Explicitly casting it as int() won't bugger up either.

 Python: import sys, math print sys.maxint print type(sys.maxint) print type(sys.maxint + 1) print type(10 ** 100) print type(int(10 ** 100)) print type(long(sys.maxint)) """ Output: 2147483647 """

 Author: mirhagk [ Sun Apr 14, 2013 10:04 pm ] Post subject: RE:Google Code Jam 2013 Qualification Yeah I'm going to go over the solutions that worked after my exam tomorrow, I"m really curious which trick was used. I mean just checking the square root of the range was fairly obvious, but the square root of 10^100 is still 10^50, so that clearly isn't the best route.

Author:  DemonWasp [ Sun Apr 14, 2013 10:34 pm ]
Post subject:  Re: Google Code Jam 2013 Qualification

Here's how I solved C, Fair and Square (all input sizes). My program's runtime is about 2 seconds.

Obviously, the preferred way to go about generating fair-and-square numbers is to generate the "base" palindrome, square it, then check that the result is also a palindrome. This reduces the range we need to search in substantially (though, as mirhagk mentions, the problem is still intractable...10^50 is way too big).

Observation:
We need more data, though. Obviously there are some patterns in the "base" numbers that we want to find. So, I wrote a small program to find all such base numbers between 1 and 1 million. The output:
 code: 1 -> 1 2 -> 4 3 -> 9 11 -> 121 22 -> 484 101 -> 10201 111 -> 12321 121 -> 14641 202 -> 40804 212 -> 44944 1001 -> 1002001 1111 -> 1234321 2002 -> 4008004 10001 -> 100020001 10101 -> 102030201 10201 -> 104060401 11011 -> 121242121 11111 -> 123454321 11211 -> 125686521 20002 -> 400080004 20102 -> 404090404 100001 -> 10000200001 101101 -> 10221412201 110011 -> 12102420121 111111 -> 12345654321 200002 -> 40000800004

Pretty quickly we notice that aside from 3 itself, none of the "base" numbers contains the digits 3-9; only 0, 1, and 2. Broadly, the reason for this can be seen when squaring a palindrome of the form "a3b3a" (for any sequence of digits a and b) through long-form multiplication. The product 3 * (a3b3a) occurs twice, and the products are then added together; where 3 is multiplied by 3, this generates the sum 3*3 + 3*3 = 18, which has a carry digit. Try it with a number like "303" on paper if you don't believe me.

This leads pretty naturally to the idea that as long as the "squaring" process doesn't involve any carry digits, the result will also be a palindrome. If there are any carry digits whatsoever, then the result will not be a palindrome.

This next part is the trickiest part, because I don't have a great proof for it.

Intuition:
Suppose that we have the first half of a base, "abc". That implies the full-base is "abccba". If we know that "abccba" is NOT a valid base (that is, abccba^2 is not a palindrome), is there any digit d such that the "extended base", "abcddcba", is valid (that is, abcddcba^2 IS a palindrome)?

I contend that that there isn't any such digit d. I don't have a good proof for that, so I'm proving it via Google. That is, "Google agrees with me so I'm probably right, QED". If anyone has a good idea for how to prove that, I'd be interested.

Solution:
So now we know that we can recursively construct the "half base", use it to generate the "full base" and test whether the square of the full base is also a palindrome (fair-and-square). For example, the half-base "10" can be extended to the full base "1001", squared to "1002001", which is a palindrome, so 1002001 is a fair-and-square number.

We can also stop recursing early if we find that some half-base is not valid (based on my not-proven hypothesis above). For example, the half-base "12" gives the full base "1221" and square "1490841" (not a palindrome) so we don't need to investigate half-bases "120", "121", or "122".

We should also make sure that when we check the half-base "abc" (and find it valid), that we check all options for "abcdcba" (the palindromes of odd length).

Optimization:
Although the above runs in the time required by the contest (about 3 minutes for the largest test case) we can do a lot better. Instead of just counting the fair-and-square numbers in a range, start by generating a list of all the fair-and-square numbers between 1 and 10^100 (there are only 41551). Then, for each test case, only count the ones that are inside the given range. This reduces the run-time to about 2 seconds (your results may vary slightly).

Code attached.

 Author: Panphobia [ Sun Apr 14, 2013 11:43 pm ] Post subject: RE:Google Code Jam 2013 Qualification Wow man if you entered you would've gotten 250 points easyy

 Author: mirhagk [ 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.

 Author: Panphobia [ 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?

 Author: DemonWasp [ 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.

 :