Google Code Jam 2013 Qualification

[Panphobia]

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?

[mirhagk]

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.

[ishidon]

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

[Panphobia]

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.

[DemonWasp]

I'm not participating in the Code Jam, but after seeing this thread, I took a look. Problem D, Treasure, interested me enough to write a solution. The judge said my output was correct, so I'll explain how I did it here.

The basic algorithm is straightforward. It's a recursive solver for a constraint satisfaction problem, which shows up pretty early in the Artificial Intelligence course at UW.

1. Read in your inventory, which is a list of integers representing keys, and the set of chests. Chests have a .number (lexicographic ordering), a .key (integer key which opens that chest) and .contents (list of integer keys contained).
2. Create a list to track chests that you have opened, in order, called opened.
3. If opened is the same size as chests then you have opened all the chests, return opened.
4. If inventory is empty, then you have run out of keys. Return failure (null in my implementation).
5. Find the lexicographically-first chest that is both not open (not in opened), and that you have the key for (chest's key is in inventory).
6. Open that chest. Create a new copy of inventory; remove chest.key and add chest.contents. Add chest.num to a new copy of opened.
7. Recurse with newInventory and newOpened.
8. If recursion returned failure (null) then go to step 5 and try the next chest. If recursion returned a solution, then you've found the lexicographically-first solution.
9. If you run out of chests to try without finding a solution, return failure (null).

That algorithm will solve most of the problems in the 'small' set. However, it can sometimes get hung up if poor decisions are made early on: if you have 20 chests and you need to open the 20th one first (but could open any of them with your starting inventory), then it will try approximately 20! combinations before getting to the solution.

Since 20! is approximately 2 quintillion, that takes way too long. We need to identify when we've screwed up earlier (that is, when some chests are definitely no longer accessible). This part of the problem is more like introductory graph theory.

It's okay if we sometimes say a problem is solvable when it isn't, so long as we are always correct when we say that a problem is NOT solvable.

Assume, for the sake of this approximate check that keys are not consumed when used. If keys are consumed, then we need to pick the order very carefully (as above); since we want to detect situations where we cannot possibly solve the problem, we'll ignore that wrinkle.

is-viable(chests, opened, inventory):
1. Create a set of chests which can possibly be opened, accessible. Initially, it contains everything in opened.
2. Start adding any chest which can be opened with the current inventory. Add its contents to inventory, but don't remove its key! Add the chest.num to accessible.
3. When no further chests can be added to accessible, check whether accessible is the same size as chests: if it is, then the problem may be solvable, but if it isn't, then the problem is definitely not solvable.

Now, add a test for is-viable into the original procedure as step 4.5 and we're done.

My Java implementation solves the large input set in about 3 seconds. I can attach it if people really want, but you can already download the solutions from the Code Jam website itself.

[Panphobia]

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.

[DemonWasp]

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.

[mirhagk]

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.

[Panphobia]

Also how the hell would you do arithmetic on numbers that go up to a googol, like on question 3 large data set

[DemonWasp]

In Java, java.math.BigInteger; in other languages, find something similar. Some languages (including, I think, Python) support arbitrarily-large integers "natively".

[Panphobia]

that would time out no? there are some patterns with palindromic squares, so couldn't you make a recursive solution?

[Zren]

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 <type 'int'> <type 'long'> <type 'long'> <type 'long'> <type 'long'> """

[mirhagk]

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.

[DemonWasp]

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.

[Panphobia]

Wow man if you entered you would've gotten 250 points easyy