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: Riolku
Subtask 1
For the first subtask, it suffices to run a brute-force check of all possible outputs to determine if there is a
piece that will satisfy the clarinet players.
Subtask 2 hint
If a subarray is good, what is the max length of the subarray?
Subtask 2
For the second subtask, note that no sequence of length 
~3~ or higher is good. Also, all sequences of length 
~1~ are good.
Thus, we should try to find a piece with 
~K - N~ good samples of length 
~2~. We can build it as we go. From
the left, if we still need good samples, we can swap to the other pitch, otherwise, we can keep the same
pitch. Note that all values between 
~N~ and 
~2N - 1~ inclusive are possible and no others are.
Subtask 3 hint
Can we build on the last subtask? Can we solve 
~M = 3~, 
~M = 4~ and so on until we see a pattern?
Subtask 3
For the third subtask, we can build on our solution to the second subtask. As before, suppose we are building
a piece, our current sequence is 
~S~, and our required count is ~K - N~. Depending on how many more good
samples we need, we can decide what to append to our sequence ~S~. For instance, if we no longer need any
good samples, we can simply add a value equal to the current last value of the sequence. If we need ~3~ more,
we can add the note 
~4~ notes back. That way, there are ~3~ additional good samples. We can also pick a new
number if we want even more good samples. It suffices to greedily choose the number that gives us the most
samples up to the remaining amount. When implementing this idea, it's a good idea to keep track of the
longest suffix of your sequence ~S~ that is good.
Subtask 4
The last subtask involves the same idea but when adding a new number to the end, we have to instead do
a proper check to see if the new number is too large.
Comments