Tuesday, July 15, 2014

Next Round - A problem from Codeforces

This problem is from Codeforces. If you want to solve this problem on your own, follow this link.

Here is the simplified problem statement.

Given a list of scores of contestants in a competition, arranged in decreasing order. We have to calculate the number of people qualified for the next round.
This is determined as follows, consider the score at a given index, Whoever scored more than this score, qualifies for the next round as long as they have a score of greater than zero.

For example, let us consider the scores {10, 9, 8, 7, 7, 7, 5, 5} and the index (starts from 1) to take as bench mark is 5. we have a total of 6 candidates who qualify for next round.

If the scores are {0,0,0,0} and the index is 2, no one qualifies for the next round because none of them have a score greater than zero.
In case of {1, 0, 0, 0} and index 2, we have one candidate qualifying for the next round.

Let us look at the way of solving this problem. We have to handle two cases here.

Case 1: score[index] > 0
    In this case, we have to find the right most occurrence of the cutoff, which will give the required answer

Case 2: score[index[ <= 0
    In this case, we have to find the left most occurrence of zero, and count the remaining elements from the beginning.

Here is the C++ implementation of the above. Since finding the left most and right most elements in a sorted array can be found using binary search, the time complexity of this solution is O(log n).