2015-05-04

Codility Challenge “Argon 2015” solution

Codility might not be the best way to assess a candidate (especially if it is the only one!), but there is definitely something in it that I like. The idea of my solution to a programming task being automatically evaluated after I deem it ready is not unfair—after all, programs are run by machines and have to be correct, efficient (more or less, depending on the context), and handle corner cases.

But the thing I like most of Codility are, of course, the challenges. I find them both difficult (I envy those who can solve them in 15 minutes at the first attempt) and fun. For me they are more workable than Project Euler’s problems, which are indeed interesting but difficult to understand if you don’t hold a degree in mathematics.

Good solutions for Codility challenges are not easy to find, and when you find one, in most cases it’s a huge blob of code with no explanation. Let’s try to solve Argon 2015 step by step.

You are given an array of 0s and 1s. You have to find the length of a longest slice of it that can be split into two non-empty parts: in the left part, there should be more 0s than 1s; in the right part, there should be more 1s than 0s. The algorithm must run in linear time and linear additional space with respect to the size of the input array.

Example. The result for the input [ 1 1 0 1 0 0 1 1 ] is 7, the longest slice being highlighted in bold with the left part in red and the right part in blue.

Of course the problem can be solved in place with a handful of nested for loops achieving O(n3) time complexity, but linear time complexity is a requirement.

The first observation we can make is that every sequence starting with a 0 and ending with a 1 does respect the rule of being “splittable” in two non-empty parts, where the left one has more 0s than 1s, and the right one has more 1s than 0s. For 0 1 this is trivially true, and for 0 ? ? ? ... ? ? ? 1 we can say that if among the question marks there are more 0s than 1s they all belong to the left part, if there are more 1s than 0s they all belong to the right part, otherwise they may all belong to either.

A good step towards the solution is to select the subsequence starting with the first 0 and ending with the last 1. But that’s not enough: depending on the actual split point between the left and the right part, the subsequence we have selected may be able to “grab” more 1s from the left and/or more 0s from the right. If we take our example: [ 1 1 0 1 0 0 1 1 ], we see that the subsequence starting from the first 0 and ending with the last 1 is [ 1 1 0 1 0 0 1 1 ] (highlighted in bold), but we can definitely grab another 1 from the left if we split the sequence at the right point: [ 1 1 0 1 0 0 | 1 1 ].

The idea is to try every possible split point and see which one allows us to grab more 1s from the left and/or 0s from the right. In fact, the amount of elements we can grab depends on how many “spare” 0s we have in the left part, and how many “spare” 1s we have in the right part. Therefore we can build two auxiliary arrays, the first one (#1) telling how many spare 0s we have in the left part if it ends at a given position, the second one (#2) telling how many spare 1s we have in the right part if it begins at a given position:

#1:                 0 -1  0  1  0 -1
#2:                -1  0 -1  0  1  0
            [ 1  1  0  1  0  0  1  1 ]
split pos:          0  1  2  3  4  5

If we split between positions 3 and 4, we can grab a 0 from the left and a 1 from the right (which does not exist in this case). This is the solution for the example instance.

#1 and #2 can be built in linear time by using an accumulator, and that’s simple to understand by just looking at the code.

Here is the full solution (also on GitHub):

#include <vector>
#include <algorithm>

int solution(std::vector<int>& input)
{
    // find first zero and last one
    int first_zero = -1, last_one = -1;
    for (int i = 0; i < input.size(); i++)
    {
        if (input[i] == 0 && first_zero == -1)
            first_zero = i;
        else if (input[i] == 1)
            last_one = i;
    }

    if (first_zero == -1 || last_one == -1 || first_zero > last_one) // no solution
    {
        return 0;
    }

    // Compute "head" and "tail" length
    const int head_length = first_zero;
    const int tail_length = input.size() - 1 - last_one;

    // Isolate the region of the vector from the first zero to the last one
    const std::vector<int> core(input.begin() + first_zero, input.begin() + last_one + 1);

    // Compute maximum elements that we can grab from the "head" or the "tail"

    int spare;
    std::vector<int> spare_left(core.size()), spare_right(core.size());

    spare = -1;
    for (int i = 0; i < core.size(); i++)
    {
        spare_left[i] = (core[i] == 0) ? ++spare : --spare;
    }

    spare = -1;
    for (int i = core.size() - 1; i >= 0; i--)
    {
        spare_right[i] = (core[i] == 1) ? ++spare : --spare;
    }

    int max_grab = 0;

    for (int split_pos = 0; split_pos < core.size() - 1; split_pos++)
    {
        const int grab_left = std::max(0, std::min(head_length, spare_left[split_pos]));
        const int grab_right = std::max(0, std::min(tail_length, spare_right[split_pos + 1]));
        max_grab = std::max(max_grab, grab_left + grab_right);
    }

    return core.size() + max_grab;
}

If there is anything unclear, or you spotted a mistake, or you have an alternative (possibly better) solution, please post a comment.

comments powered by Disqus
Fork me on GitHub