Here is the problem E - Colorful Blocks . I have gone through the discussions on Codeforces but I simply don’t understand the logic behind solving this problem. Can anyone please explain the solution to this problem, especially how we get that formula that has been mentioned by many and has been included in the editorial.
First notice that there are n-1 adjacent pairs, out of which at most k can be equal. For now let’s say we need exactly k. Therefore k out of the n-1 pairs are equal.Since we can choose any k pairs, Our first term is \binom{n-1}{k}.
Now let’s go from left to right. The leftmost element has no conditions, so has m possible choices. The 2^{nd} color has m-1 choices if it has to be different from the first color, otherwise it has only 1 choice. So does the 3^{rd} color depending on whether it has to be different from the 2^{nd} color.
We can keep going left to right like this, and we know k elements will have to be same and n-k-1 elements will have to be different. So we multiply it by 1^k \times (m-1)^{n-k-1}.
Therefore the answer is m\binom{n-1}{k}1^k(m-1)^{n-1-k}
This is the answer for exactly k. For at most k, our answer becomes \sum_{i=0}^k m\binom{n-1}{i}1^i(m-1)^{n-1-i}. This can be computed in linear time.
3 Likes