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.

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 184 |

2 | adamant | 178 |

3 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 164 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 149 |

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.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/06/2023 04:51:09 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

lightoj.com/volume_showproblem.php?problem=1329

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?

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

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

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

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 .

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?

yes , i mislead the solution . Thank you Marcil .

So, what is the solution? @All

O(1) formula