Блог пользователя khatribiru

Need Help.
Автор khatribiru, 9 лет назад, По-английски

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
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 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] .

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    lightoj.com/volume_showproblem.php?problem=1329

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +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 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?

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 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 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

          → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

        → Ответить
»
9 лет назад, # |
← 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 ;
}
→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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?

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

So, what is the solution? @All

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

O(1) formula

In [1]: print 16 * pow(15, n - 1);
→ Ответить