Need Help. - Codeforces

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:00:50
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя 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.

khatribiru
9 лет назад
12

Комментарии (12)

Написать комментарий?

Sumeet.Varma

9 лет назад, # |

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

→ Ответить

AlexanderBolshakov

9 лет назад, # |

-11

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

→ Ответить

khatribiru

9 лет назад, # ^ |

lightoj.com/volume_showproblem.php?problem=1329

→ Ответить

kingofnumbers

9 лет назад, # ^ |

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?

→ Ответить

khatribiru

9 лет назад, # ^ |

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

→ Ответить

kingofnumbers

9 лет назад, # ^ |

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

→ Ответить

TsunamiNoLetGo

9 лет назад, # ^ |

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

→ Ответить

shakil_AUST

9 лет назад, # |

← Rev. 5 →

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 ;
}

→ Ответить

Marcil

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?

→ Ответить