### khatribiru's blog

By khatribiru, 8 years ago,

Suppose we are given a array of N numbers. In How many ways we can arrange Numbers ,so that no two same numbers are together. 1<=N<=50 and 1<=array[i]<=16.

• +15

 » 8 years ago, # |   0 I m not able to come up with a perfect formula but i do think that the answer would be sort of related to inclusion-exclusion on array[i] .
 » 8 years ago, # |   -11 I know how to solve this problem, but please give its source first.
•  » » 8 years ago, # ^ |   +3 lightoj.com/volume_showproblem.php?problem=1329
•  » » » 8 years ago, # ^ |   +3 the problem you described in this blog is very different than the one in the link!first in the problem in the link there can't be more than 4 elements of the same value while you didn't mention this constraint in the blogalso as you described the problem all elements of the same value are identical while it is not in the problem in the link so different ordering of the elements of the same value make different ways or arranging which need to be countedfurthermore, the problem in the link have T<=20,000 test cases which affect majorly on the acceptable complexity of the solution.I have solved the problem as you described it then wanted to submit to make sure my idea is correct before I describe the solution here but it turned out to be different so I can't submit it.do you want to know the solution of the problem in the link or the problem as you described it?
•  » » » » 8 years ago, # ^ |   0 Sorry For the Mistake.. Actually i thought there will be at most 13 values. I want Some Hint to Solve this Problem.
•  » » » » » 8 years ago, # ^ |   0 since you didn't answer my question I will assume that you want hint for the problem in the link:hint: let A be an array of 13 elements each element is between 0 and 4let F(A) be a function that gives us the number of ways to arrange A[0] of elements of value 0 and A[1] elements of value 1 and so onwe have 5^13 states to compute but this will TLE so here is the key: if B is another array that is permutation of A then F(A)=F(B) so you can only compute F(A) only for arrays that is in increasing order the number of such arrays is much less than 5^13
•  » » » » 8 years ago, # ^ |   +6 What is your idea for the original problem in the post?
 » 8 years ago, # | ← Rev. 5 →   0 We can solve it by 2 state dp . we need to work on current position with previous position number , if both are not same then we move . Your code here...const int NX = 55 ; int Array[NX] ; // number array int dp[NX][NX] , n ; // dp array and total number limit int vis[NX] ; // global visited array to track which number is already taken or not int DP(int cur , int last) { if( cur == n ) return 1; int &ret = dp[pos][last]; if( ret != -1 ) return ret ; ret = 0 ; for( int i = 0 ; i < n ; i++ ) { if( vis[i] || Array[last] == Array[i] ) continue ; vis[i] = 1 ; ret += DP( cur + 1 , i ); vis[i] = 0 ; } return ret ; } 
•  » » 8 years ago, # ^ |   +12 in your DP solution we can reach the same state while we have different sets of numbers to use in future, so this will produce wrong answer ... right?
•  » » » 8 years ago, # ^ |   +3 yes , i mislead the solution . Thank you Marcil .
 » 8 years ago, # |   +1 So, what is the solution? @All
 » 8 years ago, # | ← Rev. 2 →   0 O(1) formula In [1]: print 16 * pow(15, n - 1);