Saturday, April 13, 2013

Google Code Jam - Qualification Round 2013

Hello, I'm writing now laying in my bed, after some hours struggling with the contest problems, so, I'll be direct.

Problem A - Tic-Tac-Toe-Tomek
This problem turned out to be a 4x4 version of a Tic-Tac-Toe problem, it implementation it's quite simple, I managed to spent a lot of memory creating a bunch of sets, you only have to watch out about the order to check the possible outcomes, misunderstand the order to check incomplete games and draw games can manage for a wrong solution, a poor O(N^2*log(N)) works:

Problem B - Lawnmower
This problem is also simple, but requires a little attention for a fast solution. Analyzing some possible outcomes for the lawnmower routes, you can cleverly figure out that for an position '[i][j]' inside the matrix, if this position has an block with a higher height both above and below, and some other position in it's sides has an height higher than the value in position '[i][j]', the field is invalid. This rule can be applied in the 'inverse' form, considering higher values in it sides, and one possible value above or below, the code runs comfortably in O(N^3):

Problem C - Fair and Square
Here comes the trouble, the first time I read the problem, I just got scarred about a case with astronomic values (10^100). Then I noticed simpler cases with lower constraints (10^14), I pre-computed the possible values for this fair and square numbers up to 10^14 and then, sought their bounds with binary search, I think there's pattern within these numbers that I unfortunately couldn't find, so, I'm looking forward to see the 'non-brute-force' solution for this problem:

Problem D - Fair and Square
To be honest, I'm reading this problem statement right now, something involving maximum flow and dynamic programming pass by my neurons. I'm thinking about a breadth-first-search storing the actual states of the 'graph', this solutions clearly won't fit in the large input limits, unfortunately I only have spare thought now, maybe next time;