Google CodeJam Qualification Round 2015

14 Apr 2015

The 4 problems for the qualification round are quite interesting. The style of a problem is a bit different from the TopCoder's one; a solution doesn't fall into usual patterns, e.g. dynamic programming. My solutions involve a lot of caching. Let's see how my solutions look like.

Problem A. Standing Ovation

I won't go into details. The solution is obvious after we realise this fact: when we are at the level i, we only need to add friends until the the persons of the level i+1 stands up.

Problem B. Infinite House of Pancakes

I was lost on this problem but I came back to solve it in time. I've realised pretty early that it's never worse to divide pancakes into the optimal setting in the beginning.

At first, I thought that we should have divided the highest pancake to half; it was not correct. If we have 100 pancakes, it's better to assign the pancakes into 10 pancakes to one diner. But I'm not sure how to handle multiple pancake stacks.

After like an hour, I see that the limit on pancakes is only 1000, which is pretty low. So, I've decided to iterate all possible maximum pancakes and divide pancakes to at the maximum. And we get the one with the minimum minutes.

Problem C. Dijkstra

This problem can be obviously solved with brute force, though it requires a lot of code and a lot of caching. The repetition of the L characters is the key here. Let's say the result of the L characters is B. We know that i must equal to multiple or zero of B followed by a prefix of the L characters. k must be a suffix of the L characters followed by multiple or zero of B.

Another important knowledge is that B4 = 1. Therefore, we don't really need to compute B5, B6, and so on because B5 = B and B6 = B2.

We can iterate through all possible i's and all possible k's, and we can compute if the number of blocks is valid. For example, if we find that i = B^3-[0,i], j = [i+1,n-1]-B-[0, j], and k = [j+1,n-1]-B^2. The number of blocks required is 3 + 4x + 1 + 1 + 4y + 1 + 2 + 4z = the given number of blocks = X. It translates to x + y + z = (X - 3 - 1 - 1 - 1 - 2)/4. This means that if (X - 3 - 1 - 1 - 1 - 2) can be divided by 4, then there can be a solution.

Nevertheless, we cannot iterate through all possible i's and all possible k's; That's like 40000 x 40000 = 1,600,000,000 iterations. It runs more than 8 minutes. But if we generate all possible i's and k's, store them in ArrayList, and only loop through those, the iteration varies but falls to around 4000x4000=16,000,000 iterations. The solution runs within 6 minutes.

Problem D. Ominous Omino

The solution is obviously brute force, but it's a lot of code. The tricky part that I've found is that we need to rotate the Richard's shape. However, it's much easier to rotate the grid instead.

I've solved this problem accidentally. I didn't handle reflection at all. But we don't need to handle reflection. This is because when you reflect the grid RxC, it looks the same; it's still RxC. But when you rotate the grid, it becomes CxR, which is different.

Another important knowledge is that, if we have N empty cells, and (N%X) is 0, we can alwasy fill all N empty cells with X-cells shapes.

The solution is straightforward: we generate all possible shapes consisting of X cells, place it on a position in the grid, and try to fill all the empty cells.