Google Code Jam 2015 by mraziz

Another year of Google Code Jam and interesting problems as always. I love how the problems end up looking simple at the end of each round.

Qualification Round

Standing Ovation

The first problem was relatively easier than the rest.

Your friend is an opera singer and you want to show her support by making sure everybody claps when she is done. This is determined by each person's level of shyness; you will only clap if n number of people clap where n is your shyness level (0 to 9). You can bring as many people as you want with any shyness levels you wish for to fill any gaps in the audience and ensure a domino clap effect.

Solution

The solution is to look at the gaps between the audience shyness levels and fill those gaps with more people if necessary, so you will have to iterate through the list of people given and check for each person if there are n persons with a lower shyness level. In other words, for each person P that has a shyness of Pn, you want to make sure there exists Pn persons with shyness level < Pn.

Python implementation:

T = int(raw_input())
for case in range(T):
    s_max, s_values = raw_input().split()
    s_values = list(s_values)
    clap_depend = [(lvl, sum([int(x) for x in s_values[:lvl]])) for lvl in range(int(s_max)+1)]
    target = filter(lambda t: t[1] < t[0], clap_depend)
    add_persons = 0
    while len(target):
        x = target.pop(0)
        diff = x[0] - x[1]
        add_persons += diff
        target = [(t[0], t[1]+diff) for t in target]
        target = filter(lambda t: t[1] < t[0], target)
    print "Case #%d: %d" % (case+1, add_persons)

Here is a C implementation I have made after the round was done, this is much more efficient than my python implementation:

#include <stdio.h>
#include <stdlib.h>
int main() {
    int T, smax, n, sum, diff;
    int i,j;
    scanf("%d", &T);
    for(i=0; i<T; i++) {
        sum=0;
        diff=0;
        scanf("%d", &smax);
        for(j=0; j<=smax; j++) {
            scanf("%1d", &n);
            if(n && j>sum) {
                diff+=j-sum;
                sum+=j-sum;
            }
            sum+=n;
        }
        printf("Case #%d: %d\n", i+1, diff);
    }
    return 0;
}

Round 1: A

Unfortunately, I was at the airport during round's schedule and couldn't reliably compete. I have managed to solve the first problem correctly in an hour or so, however due to the boarding time I had to move and lose internet access.

Mushroom Monster

The first part of this problem is relatively easy, the second part is the tricky one.

For the first part, the answer is the sum of differences a-b if a > b. The rationale behind this formula is that since we are looking for the minimum number of eaten mushrooms and Kaylin can eat as many mushrooms as she wants, then it is valid to say that whenever the number of mushrooms increase it means that Kaylin stopped eating. The opposite of this statement also holds true, that is: whenever the number of mushrooms decrease it means that Kaylin resumed eating (all of them).

For the second part, the rate is fixed and we have to find out this rate. If we see a decline from 90 to 20, for instance, then it means she ate 7 mushrooms per second, that's (90-20)/10. We can get this rate for each set of consecutive numbers a and b such that a > b. We will use the rate of the maximum difference since if it fits the maximum difference then it will definitely fit all the smaller differences but not the other way around. The answer is the sum of the minimum value between the actual number of mushrooms (as if she ate them all) and the maximum difference - i'm simply saying the maximum difference is the upper bound for the number of mushrooms she can eat but it can be less, all the way down to the number of mushrooms she has on her plate.

Python implementation:

T = int(raw_input())

for case in range(T):
    N = int(raw_input())
    mushrooms = map(lambda x: int(x), raw_input().split())

    diff = [x1-x2 for x1, x2 in filter(lambda x: x[0] > x[1], zip(mushrooms, mushrooms[1:]))]
    s1 = sum(diff)
    s2 = sum(min(m, max(diff)) for m in mushrooms[:-1]) if diff else 0

    print 'Case #%d: %d %d' % (case+1, s1, s2)