Google CodeJam 2010 : Theme Park with Solution

Guys,

This is one of the three problems asked in the 2010 Edition of Google Codejam Qualification Round. The question is quite interesting and simple to solve and I did solve. But the problem here is the running time. If not a proper strategy is followed, then the running time of the algorithm will be more and eventually you cannot submit the answer in time for large data set. Lets look at the problem.

Problem

Roller coasters are so much fun! It seems like everybody who visits the theme park wants to ride the roller coaster. Some people go alone; other people go in groups, and don't want to board the roller coaster unless they can all go together. And everyone who rides the roller coaster wants to ride again. A ride costs 1 Euro per person; your job is to figure out how much money the roller coaster will make today.
The roller coaster can hold k people at once. People queue for it in groups. Groups board the roller coaster, one at a time, until there are no more groups left or there is no room for the next group; then the roller coaster goes, whether it's full or not. Once the ride is over, all of its passengers re-queue in the same order. The roller coaster will run R times in a day.
For example, suppose R=4, k=6, and there are four groups of people with sizes: 1, 4, 2, 1. The first time the roller coaster goes, the first two groups [1, 4] will ride, leaving an empty seat (the group of 2 won't fit, and the group of 1 can't go ahead of them). Then they'll go to the back of the queue, which now looks like 2, 1, 1, 4. The second time, the coaster will hold 4 people: [2, 1, 1]. Now the queue looks like 4, 2, 1, 1. The third time, it will hold 6 people: [4, 2]. Now the queue looks like [1, 1, 4, 2]. Finally, it will hold 6 people: [1, 1, 4]. The roller coaster has made a total of 21 Euros!

 

Input

The first line of the input gives the number of test cases, T. T test cases follow, with each test case consisting of two lines. The first line contains three space-separated integers: R, k and N. The second line contains N space-separated integers g_i, each of which is the size of a group that wants to ride. g₀ is the size of the first group, g₁ is the size of the second group, etc.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of Euros made by the roller coaster.

Limits

1 ≤ T ≤ 50.
g_i ≤ k.

Small dataset

1 ≤ R ≤ 1000.
1 ≤ k ≤ 100.
1 ≤ N ≤ 10.
1 ≤ g_i ≤ 10.

Large dataset

1 ≤ R ≤ 10⁸.
1 ≤ k ≤ 10⁹.
1 ≤ N ≤ 1000.
1 ≤ g_i ≤ 10⁷.

Sample

Input	Output
3 4 6 4 1 4 2 1 100 10 1 1 5 5 10 2 4 2 3 4 2 1 2 1 3	Case #1: 21 Case #2: 100 Case #3: 20

Solution

The solution for this problem may look simple and if we follow the problem as is, its pretty straight-forward. So, here is the solution that I initially arrived at,

private int solve(int R, int k, int[] groups){
  
  int moneyMade = 0;
  LinkedList<Integer> groupsQueue = new LinkedList<Integer>();
  
  for(int i=0;i<groups.length;i++){
   groupsQueue.add(groups[i]);
  }
  
  while(R>0){
   //calculate the people that can fit in
   int eachSum = 0;
   int i;
   for(i=0;i<groups.length;i++){
    eachSum+=groupsQueue.get(i);
    if(eachSum>k){
     eachSum-=groupsQueue.get(i);
     break;
    }
   }
   moneyMade+=eachSum;
   //alterQueue
   for(int j=0;j<i;j++){
    groupsQueue.add(groupsQueue.poll());
   }
   R--;
  }
  
  return moneyMade;
 }

If you look at the above solution, I have followed the problem by the word. But turned out this cannot take the large data input set simply because of the amount of time it takes to run. The mole in the above solution is that I calculate the eachSum everytime for all R iterations. The large dataset is having R upto 10^8 and Group to be 10^7. So the runtime in worst case will be 10^16 which even the fastest computers invented these days struggle to solve in small time.

So, I had to attack my problem in a different manner. All Google CodeJam problems dont have any space criterion, so its wise to make use of it. So, what would be ideal here is to precalculate the sum and extent for each group before hand. This would take a max of 10^3 * 10^3 = 10^6 iterations. The results are stored in a separate array for faster recovery.

Then iterate through the entire R once and finish the problem in constant time. The matured code is given below.

private long solve(long R, long k, long[] groups){
  int len = groups.length;
  long[] sums = new long[len];
  int[] span = new int[len];
  //irrespective of R, calculate and keep the extent and sum in separate arrays
  for(int x=0;x<len;x++){//Maximum 1000 runs
   int sum = 0; int extent=0;
   for(int y=x;;y++){
    if(sum+groups[y%len]>k || len==extent){
     break;
    }
    extent++;
    sum+=groups[y%len];
   }
   sums[x] = sum;
   span[x] = extent;
  }
  long totalSum = 0;
  int i = 0;
  for(int r=0;r<R;r++){
   totalSum += sums[i];
   i+=span[i];
   i=i%len;
  }
  return totalSum;
 }

Files you may need.
1. Input file - Small dataset
2. Input file - Large dataset
3. Output file - Small dataset
4. Output file - Large dataset
5. Complete Source code in Java

Cheers!,
Bragaadeesh.