Codingame Solution: Roller Coaster

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));