I have input consisting of ranks in some contest (let's say a marathon) with values in the range [0, N). There are several sub-contests (e.g. based on age, gender etc.) that are only interesting for a subset team and for which another subset not_eligible do not qualify.
I am looking for an efficient algorithm (preferably written in terms of the Standard Library), that will update the ranks. Example:
auto team = std::vector<int>{ 1, 2, 9, 13 };
auto not_eligible = std::vector<int>{ 8, 10, 12 };
std::vector<int> result;
// some algorithm
assert(result == std::vector<int>{ 1, 2, 8, 10 });
Because only 1 constestant below #9 (i.e. #8) wasn't eligible, the rank of #9 is decreased by 1, and because there were 3 non-eligible finishers (i.e. #8, #10 and #12) before #13, that rank is updated by 3 from #13 to #10 for that particular sub-contest.
Note 8 and 10 are part of result but not because they were merged from non_eligible, but because their ranks were being taken by 9 and 13 from team.
How can I achieve the above using a combination of standard algorithms? I was hoping to be able to do it in O(N + M) complexity for input ranges of length N and M (e.g. through the 5-legged std::transform).
UPDATE: I am also interested in the inverse algorithm: given the ranking of a sub-contest, how to update the ranks of the contenders in the subcontest when adding the previously non-eligible participants?
I managed to find a simple wrapper around the 3-legged version of std::transform, both for the original and the inverse problem (both algorithms are O(N + M) in the input sequences)
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt remove_ranks(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
auto delta = 0;
return std::transform(first1, last1, d_first,
[&, first2](int rank) mutable {
while (first2 != last2 && rank > *first2) { ++first2; ++delta; }
return rank - delta;
});
}
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt insert_ranks(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first)
{
auto delta = 0;
return std::transform(first1, last1, d_first,
[&, first2](int rank) mutable {
while (first2 != last2 && rank + delta >= *first2) { ++first2; ++delta; }
return rank + delta;
});
}