Home ›

Google Code Jam - Theme Park

Nico Heid's picture
by Nico Heid on Sat, 07/31/2010 - 12:20
in

Theme Park is another good example of a problem which can be solved with a fairly simple algorithm. The simple version will solve the small input set without a problem, but will run almost infinitely with the large dataset.

You can read the problem on the Google Code Jam site: Theme Park

simple solution

The simple solution is to put the groups in a static array, use a pointer that "wraps around" using modulo and fill the roller coaster until it's so full, that the next group does not fit in, then let it ride earning income accordingly to the seats taken.

This is a correct solution, but unfortunately a bit slow. The input set can have a roller coaster with up to 109 seats and 108 rides and groups as large as 107.

So going through each entry every time step by step would use a lot of calculation time. The be precise, that would be O(NR).

On my system, this would mean calculation time going to infinity.

Here's the code for calculating the results:

  1. // rides
  2.         for(int j=1; j<=r; j++ ){
  3.                 // we can fill the coaster with max all groups (nobody can be present twice)
  4.                 int groupRotation = 0;
  5.                
  6.                 // fill rollercoaster
  7.                 int seatsTaken = 0;
  8.                
  9.                 while(( seatsTaken + groups[(int) (g % n)]) <= k && (groupRotation < n)){
  10.                         // seats free
  11.                         seatsTaken +=  groups[(int) (g % n)];
  12.                         g++;
  13.                         groupRotation++;
  14.                 }
  15.        
  16.                 // rollercoaster starting
  17.                 income += seatsTaken;
  18.         }

To view the slow version visit the source on github.

simple optimization, brining it down to O(R)

As you can see, the roller coaster runs way more often than groups stand in line. So at some point, you will reach a group which has already been in the roller coaster as first group. And that's the exact situation we're looking for.

Every time we fill the roller coaster, we store the position of the first group who enters the ride, remember how many people went in and store the position of the group which will fill the roller coaster first on the next run. If we then check before the run, if this group has been in first, we already know the result and we know, that from thereon we know the subsequent groups.

From this point on we can iterate on our stored results and performance increases to O(R), that's a speed up of at least 103.

Here's how we fill the Map:

  1. while (rides < r) {
  2.                 startPosition = endPosition;
  3.                 if (groupStore.get(startPosition) != null) {
  4.                         break;
  5.                 }
  6.  
  7.                 // start riding
  8.                 while ((seatsTaken + groups[endPosition % n]) <= k && groupsInRide < n) {
  9.                         seatsTaken += groups[endPosition % n];
  10.                         endPosition++;
  11.                         groupsInRide++;
  12.  
  13.                 }
  14.                 rides++;
  15.                 income += seatsTaken;
  16.                 endPosition = endPosition % n;
  17.  
  18.                 groupStore.put(startPosition, new Integer[] { endPosition, seatsTaken });
  19.  
  20.                 // reset
  21.                 seatsTaken = 0;
  22.                 groupsInRide = 0;
  23.  
  24.         }

We just start with the pattern from the first example, and put every result in a Map. As soon as we come to a position we already (line 3) know, we're done.
From thereon we just take the start position, look up the end position and add the money earned. So we go step by step forward till we finished all the rides.
  1. // now we found all combinations, just read from the map
  2.         while (rides < r) {
  3.                 Integer[] thisRide = groupStore.get(groupPosition);
  4.                 income += thisRide[1];
  5.                 groupPosition = thisRide[0];
  6.                 rides++;
  7.         }

On my system, this is needs about 85 seconds to calculate. That's fast enough for the code challenge. Congratulations ;-)

second optimization, brining it down to O(N2)

As you might have seen, going through our map step by step is again just looping through the entries. In the worst case we have a cycle, that uses every item once, or maybe the cycle contains just a few elements. So why not find the cycle, calculate the rides and income in the full cycle and use simple arithmetics instead of looping trough a map.

As you can see in the previous example, we already found the spot, where our cycle hits an element it already knows. This is the start and end point of our loop. Remember, the loop does not have to contain all items or start from the beginning.

So we use this point, and travel trough the map step by step until we return to our starting position. Then we know how many rides are in a cycle and how much income a cycle generates. After that, we just take the remaining rides and divide it by cycles and add the income. Whatever remains, as there is a chance that we don't finish the rides with a full cycle, we do step by step, as seen in the simple optimization.

So here's our loop detector:

  1. // now we found all combinations, we're trying to calculate the big cycle
  2.         int cycleEndPosition = startPosition;
  3.         long incomeFullCycle = 0;
  4.         int cycleRideCount = 0;
  5.         do {
  6.                 Integer[] curPos = groupStore.get(cycleEndPosition);
  7.                 cycleEndPosition = curPos[0];
  8.                 incomeFullCycle += curPos[1];
  9.                 cycleRideCount++;
  10.         } while (endPosition != cycleEndPosition);
  11.  
  12.  
  13.          int ridesLeft = r - rides;
  14.          int fullCycles = ridesLeft/cycleRideCount;
  15.          income += fullCycles * incomeFullCycle;
  16.          rides += cycleRideCount * fullCycles;

This brings down the processing time to less than one second. Nice, isn't it?

The optimizations can be found on github.

Comments

Twitter Trackbacks for Google Code Jam - Theme Park | unite's picture
Pingback
Twitter Trackbacks for Google Code Jam - Theme Park | unite (not verified) - Mon, 08/02/2010 - 08:12

[...] Google Code Jam - Theme Park | united-coders.com united-coders.com/nico-heid/google-code-jam-theme-park – view page – cached Theme Park is another good example of a problem which can be solved with a fairly simple algorithm. The simple version will solve the small input set without a problem, but will run almost infinitely with the large dataset. Tweets about this link [...]

didxga's picture
Very insightful! thanks for
didxga (not verified) - Mon, 08/02/2010 - 10:45

Very insightful! thanks for sharing your ingenious way to solve the problem. keep this kind of articles up.

Nico Heid's picture
solution discussion
Nico Heid - Mon, 08/02/2010 - 12:33

hi, the solutions are also discussed on the google code jam site itself, or in the google groups belonging to code jam. there are some more approaches to solving the puzzles, if you're interested. But i never found examples of the solution together with some code. That's what you can find here now.
Just to clear, I don't want to take full credit, because some of the solutions are inspired or even implementations of the google solutions (which are without code).

Nicolas Wu's picture
I've written a version in
Nicolas Wu (not verified) - Sun, 01/16/2011 - 14:10

I've written a version in Haskell, and it's interesting to compare our approaches. You can read about my solution here: http://zenzike.com/posts/2011-01-16-rho-llercoaster-rides/

Solutions for the google code jam 2012 qualify round | unite's picture
Pingback
Solutions for the google code jam 2012 qualify round | unite (not verified) - Sun, 04/15/2012 - 22:17

[...] Theme Park from the Qualification Round 2010 [...]