I was having a look at your solution to the Bar game problem (thanks so much for uploading these problems by the way). And I think you can do it in O(nlogn) where n is the number of numbers.
The algorithm is this:
Sort pairs of format (value, player) in increasing order of value.
Iterate from the LHS of pairs counting how many values you pass before you have passed K distinct players: l
Iterate from the RHS, counting how many values you pass before you have passed N - K + 1 distinct players: r
Subtract r - 1 and l - 1 from the total number of values. (This is the answer).
Here it is in C++ (the O(nlogn) comes from the insertion sort, for which I used a standard C++ STL set): Solution
I was having a look at your solution to the Bar game problem (thanks so much for uploading these problems by the way). And I think you can do it in O(nlogn) where n is the number of numbers.
The algorithm is this:
(value, player)
in increasing order of value.l
r
r - 1
andl - 1
from the total number of values. (This is the answer).Here it is in C++ (the O(nlogn) comes from the insertion sort, for which I used a standard C++ STL set): Solution