See the original problem on HackerRank.
Solutions
This problem has two main solutions. The first fully exploits the structure of the constraints, the second is more general.
Tradeoffs of both:
 we remove all the duplicates. In a different context this could be forbidden and then we would have to use extra space or another logic;
 we don’t really change the score table. Instead, in a real game it’s very likely that we need to update the current scores (e.g. for visualization).
Stateful Linear
For each Alice’s score \(score\), we iterate through current scores backwards from \(curr=n1\).
If \(score\) is larger than the leaderboard’s \(curr\), we’ll decrement \(curr\), iterating through the scores in the leaderboard and stop when we find a score that \(score\) is not greater than.
We have 3 cases:
 \(curr = 1\): \(score\) is bigger than every other score. Alice’s rank is 1,
 \(scores[curr] = score\): Alice’s rank is the same as \(curr + 1\) (1based),
\(scores[curr] > score\): Alice’s rank is one more than \(curr + 1\) (1based).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
int n, m, score; cin >> n; vector<int> scores(n); copy_n(istream_iterator<int>(cin), n, begin(scores)); scores.erase(unique(begin(scores), end(scores)), end(scores)); cin >> m; int curr = scores.size()1; while (m) { cin >> score; auto rank = 0; while (curr >= 0 && score >= scores[curr]) curr; if (curr == 1) rank = 1; else if (score == scores[curr]) rank = curr+1; else if (score < scores[curr]) rank = curr+2; cout << rank << "\n"; }
Pros:
 linear
Cons:
 maintains a state among the iterations
Stateless Binary Search
\(scores\) is sorted in descending order, so we could use the binary search to quickly lookup the array.
For each Alice’s score \(s\) we need to find the first score that is greater or equal than \(s\). The 1based position of such score results in Alice’s rank:


Pros:
 stateless: each iteration is independent from the others (we can use this method for querying the table randomly)
 simple
Cons:
 slower than the other solution
Stateful Binary Search
In this variant, for each step we use the position \(ub\) found at the previous to narrow the binary search into \(beginub\). Compared to the previous solution this is clearly faster:


Pros:
 quicker than the previous solution
 simple
Cons:
 still a bit slower than the first one
 maintains a state among the iterations
Another solution that doesn’t allocate space for returned array, but overwrites the input array.

