Read the question here from GCJ Qualification Round 2010:

» Problem C: Theme Park

This question is the easiest to understand, and is also the easiest to solve (for the small input). It’s tricky for the large input though, as you can see from the statistics — Only **40%** of the submitted attempts are correct. First, I’ll explain the easy way to solve this question which works for the small input. Then, I’ll explain why the large input is tricky to solve.

The first thing that might come to your mind is, what is a good data structure to represent the groups of people? A natural and appropriate choice is to use a queue.

To fill people into the roller coaster, you pop the first group from the front. Then the second, and third… Eventually you stop when the roller coaster is unable to fill the next group, or when the queue has been emptied.

For the next ride, push all previous groups to the back of the queue, and repeat the same steps again for a total of **R** times. (**R** is the total # of rides).

Alright, easy enough. You’ve passed the small input, and now you’re going for the large input.

Wait! We haven’t looked at the complexity of this solution. Since you are repeating **R** times, and each time there are at most **N** groups to fit in the roller coaster, the worst case is in the order of O(**R*****N**). For the large input, the biggest **R** is 10^8 and the biggest N is 1000. Besides, there are at most 50 input set, which means the complexity is in the order of 10^12. Do you think this will run within minutes? (Hint: A solution that runs in minutes must be in the order of less than 10^9.)

Therefore, we need a different strategy! There are multiple optimizations given in Google’s contest analysis, but here are two of my observations:

1) We can use an array as the data structure. We do not have to move the contents of the array, as we can use an index which tells us where does the queue start. The index wraps around, which makes the array a circular array. This is much more efficient than using a queue.

2) We can exchange space for speed. Pre-processing comes to mind. At any index of the queue, we can know exactly where the next queue starts at. We can also be definite how many people will fit in the roller coaster for any starting index of queue. We store these two information in two tables. The pre-processing step has a complexity of O(**N**^2).

Using optimization 2) above, the complexity decreases to either O(**N**^2) or O(**R**), depend on which is bigger – **N**^2 or **R**.

We are almost done, however there is another trap. Note that each group’s number, **g _{i}** could be as large as 10^7. There might be a case where you might add all

**g**, from i=1 to i=N, therefore the sum could be as large as 10^10, which is more than what a 32 bit integer could store. In short, just use 64 bit integer for the sum.

_{i}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
int n; cin >> n; for (int m = 0; m < n; m++) { long long R, k, N; cin >> R >> k >> N; long long li[2000]; for (int i = 0; i < N; i++) cin >> li[i]; long long result_money[2000] = {0}; int result_st[2000] = {0}; for (int h = 0; h < N; h++) { long long sum = 0; int st = h; bool done = false; for (int b = 0; b < N; b++) { if (sum + li[(h+b)%N] <= k) { sum += li[(h+b)%N]; st = (st+1)%N; } else { result_money[h] = sum; result_st[h] = st; done = true; break; } } if (!done) { result_money[h] = sum; result_st[h] = st; } } long long money = 0; int st = 0; for (long long i = 0; i < R; i++) { money += result_money[st]; st = result_st[st]; } cout << "Case #" << m + 1 << ": " << money << endl; } |

Cool! The version that I used for submitting this is very similar to yours, although written in Common Lisp. The complexity can be further brought down to O(

N^2), and even to O(N). See my blog post for explanations and code.0You can do another optimization in the preprocessing. For computing result_st[i] instead of starting the inner loop from b=0, we can start from b=result_st[i-1] and sum = result_money[i-1]-li[i-1]

0I think the pre-processing can be combined with the problem-solving part. The benefit is that, you only need to compute positions that can ever become the head of the roller coaster.

And another improvement on top of the above change could be that, if you once go to a position that you have seen before, it means you are going to repeat the path thing that just happened. For example, if you go to the same position every T rides, you can jump over the following N*T rides by just adding N * (profit of T rides).

0We can further optimize the solution by binary searching on the prefix sums of the number of euros earned. The time complexity for the brute force solution would then become R * logN, still too slow to execute in the time allotted. However, the precomputing solution would then have a time complexity of max(NlogN, R), much faster than max(N^2, R).

0Pingback: LeetCode | Technical interview solutions