Google Code Jam 2014 by mraziz

I have participated in this year's competition of  Google Code Jam. Being my first time in an online competition ever, it was pretty interesting, and tough!

The competition was as high as you can imagine, with people from all the different countries in the world, solving problems in minutes, problems that I would need at least an hour to solve. After getting disqualified today, I have realized I'm very slow when it comes to problem solving. I'm not sure if this is a bad thing though, it did serve me quite well when I used to work back in Zain, but it certainly didn't in an online competition.

Qualification Round

As many as 29,000+ contestants participated in the qualification round. Google decided to make it around 27 hours to cover as many time zones as possible, this long time span has served me very well considering my slowness. Out of the 29,000, around 20,000 qualified.

Checking out this website which does a way better job than Google (!) at indexing the submitted solutions, it was interesting to see how Kuwait would place into this code storm! Surprisingly, only 3 people from Kuwait participated, and of 2 of these 3 are me and my brother Saad. Even more surprising, during the competitions from 2008 up until this year, no one from Kuwait ever passed the qualification round, well that does make me feel special, a bit.

Round 1

Round 1 consists of three sub rounds: A, B, and C. Each sub round is 2 hours and 30 minutes long. You can participate in any of the three sub rounds, once you are in the top 1000 bracket of one of them, you are qualified to Round 2 and cannot participate in the remaining sub rounds. In total, 3000 will qualify to Round 2.

I did attempt all the three rounds, but unfortunately didn't make any. I did solve the problems I started, only I finished them all after rounds finished.

The Repeater

Problem

You have a list of strings, and you have 2 moves:

Given all N strings, show the minimum number of moves you need to make to have all the strings equal each other. If it's impossible, you have to indicate so by printing "Fegla Won".

Solution

3 1 2 2 1
1 3 100 1 1
3 5 1 1 9

Code

from itertools import groupby

T=int(raw_input())

def count_chars(s): return [(k,len(list(g))) for k, g in groupby(s)]
def char_order(s): return [k for k, g in groupby(s)]

for case in range(T):
    N = int(raw_input())

    strings = []
    for _ in range(N):
        strings.append(raw_input())

    # make sure all the strings have the same character order
    match = True
    for string in strings:
        match = match and char_order(string) == char_order(strings[0])
        if not match: break

    if match:
        chars_count = []
        for string in strings:
            chars_count.append(count_chars(string))

        matrix = [[x[1] for x in l] for l in chars_count]

        moves = 0
        for n in range(len(matrix[0])):
            transp = [row[n] for row in matrix]
            med = sorted(transp)[len(transp)/2]
            moves = moves + sum(abs(row[n]-med) for row in matrix)

        print "Case #%d: %d" % (case+1, moves)
    else:
        print "Case #%d: Fegla Won" % (case+1)

Part Elf

Problem

You are an Elf, either fully or partially, calculated by how Elf you parents are. The formula is: A + B / 2 where A and B are the ratios of your parents Elf-iness, the result of this formula indicates how much of an Elf you are.

You claim that you are a P/Q Elf (if you are 50% an Elf, P/Q=0.5). You know for sure that your ancestors all the way up to the 40th grandparents are either full elves or not an elf at all (1/1 or 0/1). Given a set of different P/Q, find out the closest of your grandparents (up to the 40th one) that was a full Elf, and indicate which generation was it (1 means your parents, 2 your grandparents, and so on), that grandparent must eventually produce your exact P/Q.

Solution

The first thing I noticed about this problem, is that it's a binary tree, an upside one though. You are the root, your parents are the 2 children, and so on. If you look at it as a tree, it's easy to calculate the generation number by calculating the logarithm of P/Q to the base 2. 

This is how you know the level of a node in any binary tree, for instance, in a binary tree with 10 levels, 2^10 = 1024 while log(1024) to the base 2 = 10. Let's say you are looking for the level of the 10th node (in order from root, left child, right child, and so on), it's log(10) to the base 2 = ~3.321, ceil it and it's 4, so the 10th node is on the 4th level. 3.321 also means that we need to divide 10 by 2 for 3.321 times to reach to 1. Now if you take log(0.1) to the base 2, it's -3.321, and it also means we need to multiply 0.1 by 2 for 3.321 times to reach to 1. The same concept, only inverted.

Getting the level of grandparents simply takes a log of the number to the base 2. However, this could be misleading. The problem asked for an exact P/Q, so we have to know if P/Q can really be generated or not. In order to do this, we use the given formula A + B / 2, substitute A for (2 ^  grandparent level) * P/Q which will give us the ratio of how of an Elf A is if B is 0/1 of an Elf. Since this is the level that should hold an 1/1 Elf, let's say A is 1/1, so B can be the difference of what A originally was with 1. Now take B, and see if it can be generated with a grandparent that is 1/1 of an Elf, this is to make sure these combinations are usable with the problem terms (i.e. the number we generated at our chosen level cannot be generated, at least not up until the 40th grandparent). We keep repeating this pattern until we reach the 40th grandparent, and voila.

The part where we verify P/Q is where I got stuck at, unfortunately. I should have probably moved to other problems since time was running out. The code also isn't very pretty, I'm returning True and False here and there, but I did learn the hard way that in competitions it doesn't matter how pretty your code is, you just need to get the job done!

Code

from fractions import gcd
import math

T=int(raw_input())

def is_valid(child, level):
    diff = child * (2 ** level) - 1
    acc_level = level

    while acc_level <= 40:
        if diff == 0: return True

        x = abs(math.log(diff, 2))

        if x == 1:
            return True
        else:
            x_lvl = math.ceil(x)
            diff = diff * (2 ** x_lvl) - 1
            acc_level += x_lvl

    return False

for case in range(T):
    P, Q = [int(n) for n in raw_input().split('/')]

    P = P / gcd(P, Q)
    Q = Q / gcd(P, Q)

    child = P/float(Q)
    answer = None

    x = abs(math.log(child, 2))
    level = math.ceil(x)

    if is_valid(child, level):
        answer = str(int(max(1,level)))
    else:
        answer = "impossible"

    print "Case #%d: %s" % (case+1, answer)