Solution to oxygenium2014 (Count-Bounded-Slices) by codility

27 Feb


Question Name: oxygenium2014 or CountBoundedSlices

For this question, I was unable to solve it with a golden answer. Instead, I tried to get two silver solutions. Both of them cheated the grading system to have the detected time complexity O(n), while they do not. I will list them here for later review and possible improvements.

The first one is derived from the brute force method. And it got 90 points. The key of this solution is to return when reach the end of input.

The second one is similar with the official silver solution, get 80 points. It uses the Cartesian tree. Actually, according the article, if we carry further works to implement the range minimum query in a <O(N), O(1)> algorithm, this solution should be able to pass all the test, and be a golden one. But such a <O(N), O(1)> algorithm is too complicated for such a small question. And I am still learning it.

Finally, the official golden solution is here. I tried to improve it as following, but sadly failed. It works a little more quickly for two tests, but worse for another one.

2 thoughts on “Solution to oxygenium2014 (Count-Bounded-Slices) by codility

  1. Hey Sheng,
    About the golden solution – I don’t get when do you increment j?
    I can see that you increment it only “if (maxQ[firstMax] – minQ[firstMin] <= K)"

    I think there should be an increment also when you increment i.
    Otherwise j can stay behind i, for example when the condition is never satisfied…

    • It is not possible. Consider the time that i catched up with j (i == j), A[i] == A[i]. Therefore, maxQ[firstMax] – minQ[firstMin] = 0 <= K. Then j must be moving ahead. As a result, j can never stay behind.

Leave a Reply

Your email address will not be published. Required fields are marked *