PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Imagining each kid as a point in 2D plane of Height-Weight axis can help in visualzing a solution quickly. Given some points in 2D, the kids who are not afraid form a stair-case called the maximal points. No maximal point is afraid of any other point. The problem is to find maximal set of points, remove them, find next maximal set… and so on, peeling off the maximal stair-case in each step. If the points are sorted either by Height or Weight, we can find the maximal set in O(N) time, but this direct adoption results in overall O(N*N) solution, which is too slow.
See the figure on left for the sample case 2 : N = 6, {(7,7), (4,7), (5,5), (1,2), (3,4), (2,1)}. Each color represents a maximal point set, and hence a team formed in that round.
We can solve using a sweep-line approach. Sort the points by their Y-values ( say, Height ) and process them in non-increasing order. We maintain the current set of maximal lines, by storing the X-values ( Weight ) of the bottom-most point from each of them. The point under consideration can start a new maximal line or can extend an already existing maximal line. This can be found by a simple binary search on the X-values stored. If the X-values of the maximal lines are stored in non-increasing order, we look for the smallest index i such that cur_x > X[i] and cur_x ? X[i-1]. The cur point is then added to the ith maximal line and X[i] is updated to cur_x. A count array is maintained along with this, to store the sizes of each of the maximal lines. Overall complexity is O(N logN)
Alternate Solution: ( in tester’s words ) – The idea of solution for TRAINING (I will operate with players as 2d-points): Lets sort the points in y-decreasing order (points with same y’s in x-decreasing order). This order is used to pick points for the next team: take the first point in this order as first member of the team, remove all points that are illegal to be added to this team (i.e. x or y is less or equal than coordinate of the first member of the team), take the first point among remaining points, etc. Pick points till the list of points isn’t empty. When you finish, you form a team. Go on to form new team. The slow part of this algorithm is removing points that lay on left or below than new point. I use one more order of points: x in increasing order (point with same s’s in y-increasing order). So, if you add a point to the team, all points that could be added to the team are on right of the point in the second order. I build RMQ based on array sorted with the second order, but values of elements in RMQ are indexes in array sorted with the first order. So, when I add the new point to the current team, I could ask RMQ the next point that I could add to the team. I remove a element from RMQ by setting its value to infinity.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.