Google Code Jam

[HermanHiddema]

Last year, a lot of L19'ers were interested and participated in the Google Code Jam. If anyone's interested this year, the qualifiers are coming up (April 6/7).

See: https://code.google.com/codejam/

I'll be participating

[Bill Spight]

Good luck, Herman, and good luck to all!

[Kirby]

I'm going to try, though, I'll be in the airport for Korea this Friday when the qualification round starts. Given that it's for 24 hours, maybe I'll have the chance to get some points.

[hyperpape]

After last year, I was a little annoyed with not solving more. I wanted to practice and be ready for this year. None of that happened.

Right now, I'm pretty excited about a separate project, and have been working on it every time I get a chance. I think I might try to do the Code Jam, but I can't decide what to spend time on.

[Kirby]

Well, in Korea now. A bit jet lagged, but saw that there is still time to work on the qualification round.

I did the first two problems. I can't seem to see how many you need to solve to advance to Round 1. Is it similar to last year?

[Kirby]

I see it now - 25 points. Cool.

[bernds]

I see it now - 25 points. Cool.

And note the score displayed on the standings page is "optimistic", i.e. it assumes you get full points when the hidden results are revealed.

[Kirby]

Yeah, I get it. That part is the same as last year IIRC.

[jeromie]

I don't have time to participate this year, but I'm looking forward to the inevitable discussion that crop up around here! I learned a lot last year.

[Kirby]

Well, that was quick - I'm out already. I only attempted the first two problems, and while they passed the small set on the first attempt, the large dataset gave TLE for both. I didn't do any sort of special optimization for either - just breadth first search for the first problem, and pretty much a straightforward implementation of the second.

Oh well. I guess I should have tried the other two problems, too (or thought about perf more, maybe).

[bernds]

Well, that was quick - I'm out already. I only attempted the first two problems, and while they passed the small set on the first attempt, the large dataset gave TLE for both. I didn't do any sort of special optimization for either - just breadth first search for the first problem, and pretty much a straightforward implementation of the second.

Oh well. I guess I should have tried the other two problems, too (or thought about perf more, maybe).

What do you mean by "breadth first search" in this case? The trick to the first one is that there is always one highest possible value swap. We can disregard all trailing Cs, then there is an irrelevant prefix followed by a number of S characters. Swapping the first of those S with the previous C will give you the maximum reduction. Example: SCSCSSS -> SCSSCSS.

In the second one, one has to not implement the quadractic bubble sort. The thing to realize here is that each swap leaves the middle element unchanged, so essentially it ends up sorting two arrays which are interleaved. So, put your input elements into two separate arrays as they come in, run quicksort on each, then look for mismatched elements when interleaving them again.

The one I didn't attempt was the two-rotations case for the cube. Played around with wxmaxima but couldn't really find an equation to give me the angle for a given area. I suppose a binary search could easily have found the right spot but at that point I felt I'd done enough.

[Kirby]

What do you mean by "breadth first search" in this case? The trick to the first one is that there is always one highest possible value swap. We can disregard all trailing Cs, then there is an irrelevant prefix followed by a number of S characters. Swapping the first of those S with the previous C will give you the maximum reduction. Example: SCSCSSS -> SCSSCSS.

I didn't try to do any trick. For any given string, I swap each pair of consecutive characters to generate a bunch of new strings (each one representing a possible hack). I add these to a queue for the breadth first search I'm doing. Every time I pop something off of the queue, I check to see the damage. Also, whenever I add to the queue, I'm actually adding a pair to also indicate how many hacks I did to get that string. The unmodified string has 0 hacks, the first set of hacked strings all have 1 hack, the next iteration has 2 hacks, etc.

Anyway, I didn't try to think of any particular properties of swapping - I just generated all possibilities and explored them all. That's what I meant by BFS.

In the second one, one has to not implement the quadractic bubble sort.

I implemented the quadratic bubble sort, literally taking the pseudocode from the problem description.

I guess I should have been trying to think of ways to optimize and make things fast, but I pretty much wrote things up literally to solve the problems, which I guess wasn't enough for the large datasets.

That being said, I still feel I've improved since last year, even though I didn't make it as far. Last year, I think you were able to tell when you got TLE, since it was manual upload of the output file, so I would have caught the fact that my implementations were too slow. And I wrote things up much faster than last year - in around 20 minutes for each problem, which is faster than last year.

So I'll mark it up as a success, even if I'm out so early this year.

[Tryss]

That must have been... innefficient

My code for the two first problems (in C#) :

Problem 1 :

Code: Select all

using System;
using System.Collections.Generic;
using System.Linq; 

namespace Problem 1
{
    class Program
    {
        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());
            for (int t=1; t<=T; t++)
            {
                string[] s = Console.ReadLine().Split(' ');
                int result = Solve(int.Parse(s[0]), s[1]);

                Console.WriteLine("Case #" + t + ": " + ((result<0)?"IMPOSSIBLE":result.ToString()) );
            }
        }

        static int Solve(int D, string P)
        {
            List<int> instructions = new List<int>();
            int shot = 0;
            int charge = 1;
            for (int i = 0; i < P.Length; i++)
            {
                if (P[i] == 'C')
                {
                    charge *= 2;
                }
                else
                {
                    instructions.Add(charge);
                    shot++;
                }
            }

            if (shot > D)
                return -1;


            int result = 0;
            while ( instructions.Sum() > D )
            {
                int move = shot - 1;
                while( move > 0 && instructions[move] == instructions[move-1] )
                {
                    move--;
                }

                instructions[move] /= 2;
                result++;
            }

            return result;
        }
    }
}

Problem 2 :

Code: Select all

using System;
using System.Collections.Generic;
using System.Linq;


namespace Problem_2
{
    class Program
    {
        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());
            for (int t = 1; t <= T; t++)
            {
                Console.ReadLine();
                List<int> data = Console.ReadLine().Split(' ').Select(s => Convert.ToInt32(s)).ToList();
                
                int result = Solve(data);

                Console.WriteLine("Case #" + t + ": " + ((result < 0) ? "OK" : result.ToString()));
            }
        }


        static int Solve(List<int> data)
        {
            List<int> even = data.Where((c, i) => i % 2 == 0).ToList();
            List<int> odd = data.Where((c, i) => i % 2 != 0).ToList();

            even.Sort();
            odd.Sort();

            for( int i = 0; i<odd.Count; i++)
            {
                if (odd[i] < even[i])
                    return 2*i;

                if ((i+1)<even.Count && odd[i] > even[i + 1])
                    return 2*i+1;
            }

            return -1;
        }
    }
}

Note that in my first problem, I completly abstracted the sequence : I don't swap anything,

[HermanHiddema]

Well, I didn't make it.

For problem 1 my code only solved the small set. I haven't looked at what went wrong with the large but I suspect something like an off by one error or perhaps a floating point inaccuracy from Math.log on large numbers.

For problem 2 I only wrote a quick brute force implementation which solves the small but not the large set.

For problem 3 I still have no idea what went wrong. My solution was quite efficient (equivalent to the more efficient solution mentioned in the analysis) and solved all test cases locally (using the provided test script, adjusted to give all sorts of test cases), but when I submitted it, it reported a failure with "Runtime Error" and I had no real way to debug. Very frustrating

I didn't start problem 4. After trying various ways to debug problem 3 I didn't feel like continuing, especially not on the math heavy problem 4, so I quit and went to do something more fun

[bernds]

For problem 3 I still have no idea what went wrong. My solution was quite efficient (equivalent to the more efficient solution mentioned in the analysis) and solved all test cases locally (using the provided test script, adjusted to give all sorts of test cases), but when I submitted it, it reported a failure with "Runtime Error" and I had no real way to debug.

Which language were you using? Perhaps something turned out not quite as portable between systems as one would hope.