Google Codejam 2013 Qualification Round | Bytehood

Google Codejam 2013 Qualification Round | Bytehood

Google Codejam 2013's qualification round is in progress as I write these words. I have solved enough problems to be confident that I will qualify. While I am eyeing the last remaining one, I am not going to try too hard to crack it. In this post I am going to briefly discuss problems in the round, without hinting on any solution.

Problem A. Tic-Tac-Toe-Tomek:

This is an implementation problem. You have to check whether game in current state is a win for 'X', 'O', a "Draw", or  "Game has not completed".

Problem B. Lawnmower:

You have a NxM meters of lawn, and you want to cut grass in each 1×1 meter of it to a certain length as given in problem input. The only way you can use your lawnmower is to set its setting to cut grass above a certain length, before it enters the lawn, and then let lawnmower enter lawn from any direction perpendicular to edge of lawn, cutting grass as it crosses the lawn in a straight line till it exits on the other side. You can use your lawnmower as many times as you want, and can not change its settings once it is inside the lawn.

You are required to validate whether it is possible to use your lawnmower to cut grass of your lawn according to the pattern given as input.

Problem C. Fair and Square:

You have to find the number of Fair and Square integers in a range A to B inclusive. A fair and square integer is an integer which is a palindrome and also a square of a palindrome. This problem has three input sets. One small, and two large ones. You won't go very far with a naive solution with the large inputs. Specially the second large.

Problem D. Treasure:

I haven't yet solved this problem. You have N chests, and you start with a set of keys. Each chest opens with a certain type of key, and a key once used can not be used again. Each chest has additional keys that you can pick up and use. You have to determine the lexicographically smallest sequence to open the chests in. It is possible that not all chests can be opened no matter what sequence is followed, in which case solution is IMPOSSIBLE.

Conclusion:

I have solved problems A and B, and small and first large set of C with a great deal of confidence in my solutions. I am pretty sure my solution to second large set of C is wrong. And I haven't attempted D yet.

Read full article from Google Codejam 2013 Qualification Round | Bytehood