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)$ ~\mathcal{O}(2^N)~

Subtask 2

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

Time Complexity: $\mathcal{O}(N^2)$ ~\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$ ~dp~ values of all alpacas $j$ ~j~ $(1 \le j < i)$ ~(1 \le j < i)~ that are outside the range of the $i^\text{th}$ ~i^\text{th}~ alpaca into the BIT. Since the positions of alpacas are in increasing order, all alpacas after the $i^\text{th}$ ~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}$ ~i^\text{th}~ alpaca, which we do by querying the BIT for the maximum $dp$ ~dp~ value in the range from $1$ ~1~ to $a_i - b_i$ ~a_i - b_i~.

Time Complexity: $\mathcal{O}(N \log N)$ ~\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)$ ~\mathcal{O}(N \log N)~

Comments

There are no comments at the moment.