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).
simple optimization, brining it down to O(N)
As you can see, the roller coaster runs way more often than groups stand in line. So to 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.
Nico Heid
Latest posts by Nico Heid (see all)
- Raspberry Pi Supply Switch, start and shut down your Pi like your PC - August 24, 2015
- Infinite House of Pancakes – code jam 2015 - July 13, 2015
- google code jam 2014 – magic trick - April 18, 2014