Google Code Jam Practice

Published: May 4 2013

I was playing around with Google Code Jam practice question and was thinking of a smarter way to solve this question. The particular challenge I'm doing is Hedgemony problem. I ended up solving it with two solutions and I did performance benchmark for fun.

First solution

First solution is pretty straight forward although I have to admit my code is ugly as hell. I just coded a quick solution.

static void CalculateWithoutAlgo(string[] inputs)
{
    var totalCase = Int32.Parse(inputs[0]);

    for (var i = 0; i < totalCase; i++)
    {
        var index = 1 + i * 2;
        var totalItem = int.Parse(inputs[index]);
        var items = inputs[index + 1].Split(' ').Select(decimal.Parse).ToArray();

        // do calculation here
        for (var j = 1; j < totalItem - 1; j++)
        {
            var average = (items[j - 1] + items[j + 1])/2;
            if (items[j] > average)
            {
                items[j] = average;
            }
        }

        Console.WriteLine("Case #{0}: {1}", i + 1, items[totalItem - 2]);
    }
}

Second solution

Second solution is pretty elegance I think, but I think it could be much better. I just couldn't figure out how to handle multiple variable (read: Math variable). I'll explain in a bit. This is the code.

static void CalculateUsingAlgo(string[] inputs)
{
    var totalCase = Int32.Parse(inputs[0]);

    for (var i = 0; i < totalCase; i++)
    {
        var index = 1 + i * 2;
        var totalItem = int.Parse(inputs[index]);
        var items = inputs[index + 1].Split(' ').Select(decimal.Parse).ToArray();

        // do calculation here
        for (var j = 1; j < totalItem-1; j++)
        {
            items[j] = ((items[j-1] + items[j+1] + (2*items[j]) - Math.Abs(items[j-1] + items[j+1] - 2*items[j])) / 4;
        }

        Console.WriteLine("Case #{0}: {1}", i + 1, items[totalItem - 2]);
    }
}

Explanation

Ok, now let me explain the Math part.

I believe this can be expand more for n > 3. But the thing is, the variable in the equation will be much more than 3 and it becomes harder to simplify. Or maybe it can use some sort of recursion (I forgot what's the name of the method in Math) and to simplify it then we can just pull the value and plug it in to get the answer.

I like it because it doesn't involve comparing value and the need to create extra variable to hold the average.

Performance

I was hoping the algo would work faster, but apparently it doesn't haha. Damn. I used the sample provided by Google. For each test, I ran the program 10 times and average the time it takes. The result is as below

100 Samples

Without Algo : 33.10439 ms
With Algo    : 37.30668 ms

10,000 Samples

Without Algo : 38.60448 ms
With Algo    : 40.60399 ms

As you can see, there is not much different.