Editorial for An Animal Contest 6 P5 - Rock Painting
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1 Hint
What is the probability of rock being the first or last rock with some colour ?
Subtask 1
Let's create an array of length to represent the initial state of the rocks. If , the rock has not been coloured. Otherwise, will denote the colour of the rock.
We also define to be the probability of rock being the rightmost rock and to be the probability of rock being the leftmost rock with some colour . We have:
where is the number of non-coloured rocks to the right of rock and is the number of distinct non-zero to the right of rock . Calculating is the same as but in reverse.
Therefore, the final answer to this problem is:
Time Complexity:
Subtask 2
For this subtask, we can generalize the definition of to be . Using , we have:
Using some algebra, we have:
Substituting the sum of geometric series formula into the equation, we get:
Time Complexity:
Subtask 3
This subtask is an extension of subtasks 1 and 2 and is left as an exercise for the reader.
Time Complexity:
Comments