Problem C. Theme Park - Qualification Round 2010 - Google Code Jam

Dashboard - Qualification Round 2010 - Google Code Jam

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.

Official Analysis: https://code.google.com/codejam/contest/433101/dashboard#s=a&a=2

O(NR)  - At first glance, this problem appears to be a straightforward simulation: keep adding groups until you run out space on the roller coaster (or run out of groups), then re-form the queue and start again. Repeat this R times and you're done.

Optimization One

When you're sending the roller coaster out for 10⁹ rides, you've got to expect that a few of them are going to be the same. If you store the queue of groups as an unchanging array, with a pointer to the front, then every time you send out a ride s, you could make a note of where it ended, given where it started. Then the next time you see a ride starting with the same group in the queue, you can do a quick lookup rather than iterating through all the groups.

That speeds up the algorithm by a factor of 10³ in the worst case, leaving us with O(R) operations. There are some other ways of speeding up the calculation for any given roller coaster run: for example, you could make an array that makes it O(1) to calculate how many people are in the range [group_a, group_b] and then binary search to figure out how many groups get to go in O(log(N)) time. That gives a total of O(R log N) operations.

Optimization Two

As we observed in Optimization One, you're going to see a lot of repetition between rides. You're also going to see a lot of repetition between groups of rides. In the example in the problem statement, the queue was made up of groups of size [1, 4, 2, 1]. 6 people get to go at once. Let's look at how the queue changes between rides:

1, 4, 2, 1  [5]
2, 1, 1, 4  [4]
4, 2, 1, 1  [6]
1, 1, 4, 2  [6]
2, 1, 1, 4  [4]
4, 2, 1, 1  [6]
1, 1, 4, 2  [6]

As you may have noticed, there's a cycle of length three: starting from the second run, every third queue looks the same. We make 16 Euros when that happens, which means we'll be making 16 Euros every 3 runs until the roller coaster stops rolling.

So if the roller coaster is set to go 10⁹ times: the first time it makes 5 Euros; then there are 999999999 runs left; and every three of those makes 16 Euros. 3 divides 999999999 evenly -- if it didn't, we'd have to do some extra work at the end -- so we make 5 + (999999999 / 3 * 16) = 5333333333 Euros in total.

It turns out that a cycle must show up within the first N+1 rides, because there are only Ndifferent states the queue can be in (after N, you have to start repeating). So you only have to simulate N rides, each of which takes O(N) time in the worst case, before finding the cycle: that's an O(N²) solution.

Optimization Three

Either of the optimizations above should be enough. But if you're a real speed demon, you can squeeze out a little more efficiency by combining the binary search that we mentioned briefly in Optimization One with the cycle detection from Optimization Two, bringing our running time down to O(N log N). An alternate optimization can bring us down to O(N); 

http://articles.leetcode.com/2010/05/problem-c-theme-park-solution.html
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.)

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_i, 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.

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;

}

Small: brute force.
public static void main(String args[]) throws Exception {
//String inFile = args[0];
//String inFile = "C-example.in";
String inFile = "C-small-attempt0.in";
//String inFile = "C-large.in";
String outFile = inFile + ".out";
LineNumberReader lin = new LineNumberReader(new InputStreamReader(new FileInputStream(inFile)));
PrintWriter out = new PrintWriter(new File(outFile));
int NCASE = Integer.parseInt(lin.readLine());
for(int CASE = 1; CASE <= NCASE; CASE++) {
out.print("Case #" + CASE + ": ");
String l = lin.readLine();
String ll[] = l.split(" ");
int R = Integer.parseInt(ll[0]);
int k = Integer.parseInt(ll[1]);
int N = Integer.parseInt(ll[2]);
int g[] = new int[N];
l = lin.readLine();
ll = l.split(" ");
for(int i = 0; i < N; i++)
g[i] = Integer.parseInt(ll[i]);
int sum[] = new int[N];
int nn[] = new int[N];
for(int i = 0; i < N; i++) {
int s = 0, j = 0, n;
do {
n = (i + j) % N;
int z = g[n];
if(s + z > k)
break;
s += z;
} while(++j < N);
sum[i] = s;
nn[i] = n;
}
long e = 0;
int n = 0;
for(int i = 0; i < R; i++) {
e += sum[n];
n = nn[n];
}
out.println(
e//y
);
}
lin.close();
out.close();
}
Read full article from Dashboard - Qualification Round 2010 - Google Code Jam