Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Roller Coaster

Original Problem

The Goal

You have recently been assigned to a new amusement park’s center of analysis and supervision. Your mission is to estimate each day what the earnings will be for each ride that day. You start by looking at the roller coaster.

Rules

You notice that people like the roller coaster so much that as soon as they have finished a ride, they cannot help but go back for another one.
  • People queue up in front of the attraction
  • They can either be alone or in a group. When groups are in the queue, they necessarily want to ride together, without being separated.
  • People never overtake each other in the queue.
  • When there isn’t enough space in the attraction for the next group in the queue, the ride starts (so it is not always full).
  • As soon as the ride is finished, the groups that come out, go back into the queue in the same order.

The attraction contains a limited number L of places.
The attraction can only function C number of times per day.
The queue contains a number N of groups.
Each group contains a number Pi of people.
Each person spends 1 dirham per ride.

Example

With L=3, C=3 and 4 groups (N=4) of the following sizes [3,1,1,2]:

Ride 1: for the first roller coaster ride, only the first group can get on and takes all the places. At the end of the ride, this group returns to the back of the queue that now looks as follows [1,1,2,3].
Earnings of the ride : 3 dirhams.

Ride 2 : on the second ride, the following two single-person groups can get on, leaving one place empty (the group of 2 people that follows cannot be separated) At the end of the ride, they return to the back of the queue: [2,3,1,1]
Earnings of the ride : 2 dirhams.

Ride 3: for the last ride (C=3), only the group of 2 people can get on, leaving one place empty. Earnings of the ride : 2 dirhams.

Total earnings: 3+2+2 = 7 dirhams

Game Input

Input

Line 1: The integers L, C and N separated by a space.

N following lines: Each line contains an integer Pi representing the number of people in a group. The lines are ordered in the same way as the queue. (The first lines correspond to the first groups that can get on the ride).

Output
An integer representing the number of dirhams earned at the end of the day on the roller coaster (after C roller coaster rides)
Constraints
PiL
1 ≤ L ≤ 10^7
1 ≤ C ≤ 10^7
1 ≤ N ≤ 1000
1 ≤ Pi ≤ 10^6

Solution

I really liked to solve this problem. We can do much better than the trivial solution, which simply loops \(C\) times. Or better said, we must do better, since \(C\) can become quite large. What I first did, was playing the game for a while. With the example input of (3, 1, 1, 2) and a limit of 3, this means:

\[\begin{array}{l} \leftarrow (3) \leftarrow (1, 1, 2)\\ \leftarrow (1, 1) \leftarrow (2, 3)\\ \leftarrow (2) \leftarrow (3, 1, 1)\\ \end{array}\]

After that, we always have the same groups. Let's try another example (2, 3, 5, 4) with a limit of 5:

\[\begin{array}{l} \leftarrow (2, 3) \leftarrow (5, 4)\\ \leftarrow (5) \leftarrow (4, 2, 3)\\ \leftarrow (4) \leftarrow (2, 3, 5) \end{array}\]

Last example: (3, 9, 7, 6, 4) with limit 15:

\[\begin{array}{l} \leftarrow (3, 9) \leftarrow (7, 6, 4)\\ \leftarrow (7, 6) \leftarrow (4, 3, 9)\\ \leftarrow (4, 3) \leftarrow (9, 7, 6)\\ \leftarrow (9) \leftarrow (7, 6, 4, 3) \end{array}\]

It's clear that this pattern must start to cycle eventually. So, the first step to solve this problem is to find the groups that emerge and the cycle offset. For the first two examples, the offset was zero, in the last example it was 1. I use a quite simple string representation as a fingerprint for the cycle detection. If we know the value of every individual group, all we have to do is how often each group will go. All the groups which don't cycle must be added exactly once to the final result. The number of these groups will be \(o\).

All other groups will need to go exaclty \(\left\lfloor\frac{C-o}{|g| - o}\right\rfloor\) times. Okay, not exactly. We need to fill the rest, if the number doesn't fill a full cycle. But we simply add one to each group as we go. The complete algorithm can then look like this:

var inputs = readline().split(' ');
var L = +inputs[0];
var C = +inputs[1];
var N = +inputs[2];
var P = [];
for (var i = 0; i < N; i++) {
    P.push(+readline());
}

function compute(P, L, C) {

    var g = []; // Group value Storage
    var q = [P.toString()]; // Sequence Storage

    var t = P.shift(); // Pop the first value off the beginning

    var o; // Cycle offset

    var res = 0; // Final result

    // Calculate offset and groups
    do {

        var s = 0;

        // Generate a group
        for (var i = 0; i <= P.length && s + t <= L; i++) {
            P.push(t); // Push current value to back
            s+= t; // Sum for group
            t = P.shift(); // Pop a new value from the front
        }

        o = q.indexOf(P.toString()); // Check for Cycle offset
        q.push(P.toString()); // Remember current sequence

        g.push(s); // Found a new group

    } while (o === -1); // Loop until we get a cycle

    // Sum up the first elements occuring just once
    for (var i = 0; i < o; i++) {
        res+= g[i];
    }

    // Calculate the rest, which doesn't fit into a group
    var r = (C - o) % (g.length - o);

    // Run over the other groups
    for (; i < g.length; i++) {

        // Group value times the number of occurences plus the rest
        res+= g[i] * (Math.floor((C - o) / (g.length - o)) + (r > 0));
        r--; // Reduce rest
    }
    return res;
}
print(compute(P, L, C));

Go to overview