Editorial for An Animal Contest 1 P6 - Alpaca Distancing - Olympiads Online Judge

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

Subtask 2

Let $dp[i]$ $d p [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]$ $d p [j]$ $(1 \le j < i)$ $(1 \leq j < i)$ to update $dp[i]$ $d p [i]$ if the alpacas at positions $i$ $i$ and $j$ $j$ are outside each other's ranges.

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

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

Comments

There are no comments at the moment.