Editorial for An Animal Contest 6 P2 - G-Pop

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.

Authors: andrewtam, julian33

Solution for 20%

Note that if X = \max(r_i - l_i + 1), then we need exactly X distinct bands.

Solution for 50%

An example of an ordering that is valid is 1, 2, 3, \dots, X, 1, 2, 3, \dots.

Solution for 100%

Let A be the plan that we output. For the remaining 50\%, we must maximize the number of indices j (2 \le j \le N) where A_j = A_{j-1}. Let's call j good if we can do this. First, let's define f_j as the minimal l_i such that l_i \le j \le r_i. If there is no i such that l_i \le j \le r_i, then f_j = j. Observe that j is good if and only if f_j = j. This is because if f_j < j there exists some i such that l_i \le j-1 < j \le r_i. So, if we make A_j = A_{j-1}, then there will be 2 identical bands playing within some [l_i, r_i]. On the other hand, if f_j = j, there clearly exists no i where j and j-1 are in [l_i, r_i]. Initially, set A_1 = 1. Then, for each j (2 \le j \le N), A_j = A_{j-1} if f_j = j. Otherwise, A_j = A_{j-1}+1, making sure that if A_j = X+1 we set it to 1.

Time Complexity: \mathcal{O}(N)


There are no comments at the moment.