Editorial for An Animal Contest 1 P6 - Alpaca Distancing
Submitting an official solution before solving the problem yourself is a bannable offence.
This subtask was intended to reward brute force solutions.
Let represent the maximum number of friends that William can keep among the first alpacas. Sort the alpacas by position. Brute forcing the transition suffices, using to update if the alpacas at positions and are outside each other's ranges.
There are many approaches hereafter. A binary indexed tree (BIT) for prefix maximum queries will be used in this solution.
To optimize the transition, we add the values of all alpacas that are outside the range of the alpaca into the BIT. Since the positions of alpacas are in increasing order, all alpacas after the are also outside the range of alpacas in the BIT. The last step is to satisfy the range requirement of the alpaca, which we do by querying the BIT for the maximum value in the range from to .
For full marks, coordinate compression of the values used in the BIT is required.