Google Code Jam

[Hitmen]

Some of the better programmers here might have a shot at winning Google's programming contest. There are at least a few people here who might have a shot at winning

[Yoni]

All individuals who are 18 years of age or older are eligible

Discriminators!

[Kev1n]

Lol, ya. thats pretty lame.

[iago]

Yay, completed!  Here are my 2 questions:

250 point:
You're running an arcade, you have a list of machines and a list of locations; each machine has it's own profit, and each location is a percentage of the max profit that the machine can get.

For example, you might have machines with a profit of {30, 15, 100} and locations which will give you { 10, 50 } which would be 10% and 50% of potential profit.  the lists might be different lengths.  

I opted to use Java for this, since it greatly reduced the required effort.  Here's my code:

Code Select Expand

// System> iago has submitted the 250-point problem for 133.47 points

import java.util.*;

public class GameLocations
{
   public int maximizeProfits(int[] machinePotential, int[] locationVisibility)
   {
      // First sort the arrays
      Arrays.sort(machinePotential);
      Arrays.sort(locationVisibility);

      // Now step through and compare each value until one of them it empty, adding
      // it to our total
      int total = 0;
      int machineIndex = machinePotential.length - 1;
      int locationIndex = locationVisibility.length - 1;
      while(machineIndex >= 0 && locationIndex >= 0)
      {
         total += machinePotential[machineIndex] * locationVisibility[locationIndex];
         machineIndex--;
         locationIndex--;
      }

      // Now divide by 100 because it's a percentage
      total /= 100;

      // That should be it!
      return total;
   }
}

1000 point
For the second, there were 2 people, John and Mary, who each had their own array of coins.  John owed mary some amount of money (debt).  You had to determine the least number of coins transferred between the two of them.

I had absolutely no clue how to do this, on paper or otherwise, so I took Grok's advice ("[19:53:29] (BotNet) <Grok> yes.  shoot person 2.  take his money."):

Code Select Expand

// System> iago has submitted the 1000-point problem for 549.85 points
import java.util.*;
public class Exchange
{
   public int min(int[] johnCoins, int[] maryCoins, int debt)
   {
      // This is going to go on the assumption that John has a gun
      int johnMoney = 0;
      for (int i = 0; i < johnCoins.length; i++)
      {
         johnMoney += johnCoins[i];
      }
      // Here's where John pulls the gun on mary
      for( int i = 0; i < maryCoins.length; i++)
      {
         johnMoney += maryCoins[i];
      }
      System.out.println("John now has " + johnMoney + " worth of coins, and Mary has nothing.  Poor mary.");
      return maryCoins.length;
   }
}

[Hitmen]

1000 point
For the second, there were 2 people, John and Mary, who each had their own array of coins.  John owed mary some amount of money (debt).  You had to determine the least number of coins transferred between the two of them.

I had absolutely no clue how to do this, on paper or otherwise, so I took Grok's advice ("[19:53:29] (BotNet) <Grok> yes.  shoot person 2.  take his money."):

Code Select Expand

// System> iago has submitted the 1000-point problem for 549.85 points
import java.util.*;
public class Exchange
{
   public int min(int[] johnCoins, int[] maryCoins, int debt)
   {
      // This is going to go on the assumption that John has a gun
      int johnMoney = 0;
      for (int i = 0; i < johnCoins.length; i++)
      {
         johnMoney += johnCoins[i];
      }
      // Here's where John pulls the gun on mary
      for( int i = 0; i < maryCoins.length; i++)
      {
         johnMoney += maryCoins[i];
      }
      System.out.println("John now has " + johnMoney + " worth of coins, and Mary has nothing.  Poor mary.");
      return maryCoins.length;
   }
}

Now that's think outside of the box.

[iago]

I had a long conversation with my friend on msn afterwards.  He can't think of any way of doing it that would actually work.  It almost seems like you'd have to generate the entire tree and find the closes leaf :/

[Adron]

I had a long conversation with my friend on msn afterwards.  He can't think of any way of doing it that would actually work.  It almost seems like you'd have to generate the entire tree and find the closes leaf :/

You probably don't have to generate the entire tree, as soon as you've found a solution you can stop all searches when they reach that depth.

[iago]

That's what I was thinking, a breadth first search.. go one node down at each iteration until we find an end state, then deal with it.

Problem is, I had 33 minutes left to do this.  I should go back and do it right just to make me feel better.

[Adron]

I'm pretty sure I've solved similar problems in other programming competitions and they can be solved rather quickly if you just get down to work.

[iago]

If I did it now, I might be able to in that time constraint, especially with Java, but it's too late now

[Adron]

Hehe

When will you know how you placed?

[iago]

They said they'd email me today

[hismajesty]

Keep us updated...good luck.