Editorial for An Animal Contest 6 P2 - G-Pop
Submitting an official solution before solving the problem yourself is a bannable offence.
Solution for 20%
Note that if , then we need exactly distinct bands.
Solution for 50%
An example of an ordering that is valid is .
Solution for 100%
Let be the plan that we output. For the remaining , we must maximize the number of indices where . Let's call good if we can do this. First, let's define as the minimal such that . If there is no such that , then . Observe that is good if and only if . This is because if there exists some such that . So, if we make , then there will be identical bands playing within some . On the other hand, if , there clearly exists no where and are in . Initially, set . Then, for each , if . Otherwise, , making sure that if we set it to .