Editorial for An Animal Contest 1 P6 - Alpaca Distancing


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: samliu12

Subtask 1

This subtask was intended to reward brute force solutions.

Time Complexity: \mathcal{O}(2^N)

Subtask 2

Let dp[i] represent the maximum number of friends that William can keep among the first i alpacas. Sort the alpacas by position. Brute forcing the transition suffices, using dp[j] (1 \le j < i) to update dp[i] if the alpacas at positions i and j are outside each other's ranges.

Time Complexity: \mathcal{O}(N^2)

Subtask 3

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 dp values of all alpacas j (1 \le j < i) that are outside the range of the i^\text{th} alpaca into the BIT. Since the positions of alpacas are in increasing order, all alpacas after the i^\text{th} are also outside the range of alpacas in the BIT. The last step is to satisfy the range requirement of the i^\text{th} alpaca, which we do by querying the BIT for the maximum dp value in the range from 1 to a_i - b_i.

Time Complexity: \mathcal{O}(N \log N)

Subtask 4

For full marks, coordinate compression of the values used in the BIT is required.

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.