khatribiru's blog

Need Help.
By khatribiru, 9 years ago, In English

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.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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] .

→ Reply
»
9 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I know how to solve this problem, but please give its source first.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    lightoj.com/volume_showproblem.php?problem=1329

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 blog

      also 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 counted

      furthermore, 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?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry For the Mistake.. Actually i thought there will be at most 13 values. I want Some Hint to Solve this Problem.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 4

          let 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 on

          we 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

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        What is your idea for the original problem in the post?

        → Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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 ;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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?

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

So, what is the solution? @All

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

O(1) formula

In [1]: print 16 * pow(15, n - 1);
→ Reply