CHEFCOL - Editorial

editorial
, , , ,
1

Problem Links:

Practice

Contest

Author : Aman Kedia

Tester : Himanshu Jaju

Editorialist : Aman Kedia

Difficulty:

Medium

Explanation

Let us assume that there are x distinct coloured balls with chef and Bakku initially (leaving special balls). Now let y be the number of colors common between the balls of chef and bakku.
If we can find solution for a fixed value of x and y then we can iterate over possible values of x and y for the total number of ways.

For a fixed value of x and we can find number of ways to color N balls with chosen x colors using the following recurrence:

dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1]

To calculate number of ways we need to multiply the dp[n][x]2 by number of ways of choosing these x colors for coloring simultaneously keeping y colors common between both selection of x colors.
So the number of ways for coloring 2N balls will be C(K,2x-y)* C(2x-y, x) C(x,y)*dp[n][x]2

Now we can colour two special balls in 3 ways:

  1. We can color both of them with any of K-(2*x-y) colors so that both chef and bakku have x+1 distinct colored balls after any distribution.
  2. Color both of them with any of y common colors so that both chef and bakku have x+1 distinct colored balls after any distribution.
  3. Color one with any of (x-y) colors that only chef has and other with any of (x-y) colors that only bakku has. Now for one distribution both of them will have x distinct balls and for other both of them will have x+1 distinct balls.