Counting Problem - Codeforces

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	164
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

Greetings Everyone,

I know this sounds pretty much like a homework problem that's why I was hesitant to ask it in the first place. (I could have asked someone through a PM but I have lost faith in such methods lately)

Anyways,

There are 3n balls in total, of 3 different colours , (i.e. n balls of each colour) find the number of ways you can arrange them in a row such that no two balls of the same colour are adjacent

The various approaches which I could google include,

1 ) Principle of Inclusion and Exclusion :- It stated Find the total number of ways of arranging 3n balls with the constraints (i.e. n identical balls of each colour) then subtract from it the number of ways in which atleast two balls of same colour are together. But I couldn't derive a formula from it :( the one I derived was wrong.

2 ) Someone on Quora said to brute force till n=5 and guess the formula.

3 ) Suggestions of O(n^3) DP from a freind. Don't know how to do it.

I still think this is a pretty standard Permutations problem but sorry I guess my googling sucks.

Any Resource / Approach / Formula would be deeply appreciated.

I am sorry if this is a stupid problem, Also if you would like to answer a follow up.

I was thinking of generalizing this problem to kn balls and k different colours. How to do it ?

Thanks in Advance.

for(int i = 1 ; i <= N ; ++i){ for(int r = 0 ; r <= i && r <= n; ++r){ for(int g = 0 ; g + r <= i && g <= n ; ++g){ int blue_used = i-(r+g); if(blue_used>n){ //Set the dp to 0 for all colors for the given (i,r,g) } else{ //use the relation mentioned in post. } } } }

Comments (10)

Write comment?

-emli-

9 years ago, # |

I can solve by DP

→ Reply

gkeesh7

9 years ago, # ^ |

Great! you can tell me about the solution if you like.

StoneCold_

← Rev. 5 →

+10

O(n³) DP:

dp[i][c][r][g] is the number of valid combinations uptill index i such that current colour is c , r red balls have been used and g green ones, Obviously number of blue balls remaining can be figured out from the index,number of reds used and number of greens used.

If you place red at current index. dp[i]['r'][r][g] = dp[i - 1]['b'][r - 1][g] + dp[i - 1]['g'][r-1][g]

For blue: dp[i]['b'][r][g] = dp[i - 1]['r'][r][g] + dp[i - 1]['g'][r][g].

Similarly you can derive for green.

Also you only need to declare the array as dp[2][3][n][n] because of state-compression.

Thanks , Nice solution! :) I guess N in the first for loop must be for N=3*n else everything understood.

Yeah N is 3n

← Rev. 2 →

Let

Unable to parse markup [type=CF_TEX]

S — set of all possible strings having n red , n blue and n green balls .

S₁ -> set of all possible strings in S such that atleast two red are adjacent.

S₂ is for blue and

is for green.

By inclusion-exclusion

Let's find S_i first.

Basically it is the set of all possible strings in which atleast two balls of color i are adjacent .

So lets merge any two i colored balls as a single object and then find the number of permutations possible considering those two i balls as an attached object.

Similarly for finding

we first merge any two i color balls as a single object and then merge two j color balls as a single objects .

You can figure out similarly for

Obviously

and also

as the number of red,green,blue are same and hold the same constraints.

So the answer can be easily found out now.