11481  Arrange the Numbers
Moderator: Board moderators
11481  Arrange the Numbers
need help...!!!
i am stuck since contest time, but i have no ability to solve it myself.
please, give me some hints.
i am stuck since contest time, but i have no ability to solve it myself.
please, give me some hints.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11481  Arrange the Numbers
Use inclusionexclusion principle.
Re: 11481  Arrange the Numbers
Is this DP?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com
Re: 11481  Arrange the Numbers
Yep, I solved it during the contest using a recurrence relation.
Hint : Think of how to get a recurrence relation to find the number of derangements of n numbers.
Hint : Think of how to get a recurrence relation to find the number of derangements of n numbers.
I am signing an important document!
Re: 11481  Arrange the Numbers
Can you explain a little more?Robert Gerbicz wrote:Use inclusionexclusion principle.
Inclusion and exclusion on what?
Re: 11481  Arrange the Numbers
on which elements won't move:
first we choose which k elements won't move at first m positions (m choose k)
then we want to count how many there are permutations of n' = n  k elements that all of m' = m  k first elements will move
we use in/out
+ all permutations
 all permutations that have at least two elements that won't move
+ all permutations thath have at least three elements that won't move
and so on
first we choose which k elements won't move at first m positions (m choose k)
then we want to count how many there are permutations of n' = n  k elements that all of m' = m  k first elements will move
we use in/out
+ all permutations
 all permutations that have at least two elements that won't move
+ all permutations thath have at least three elements that won't move
and so on
Re: 11481  Arrange the Numbers
I tried to solve this prob but getting WA.Anyone please check the following I/O..
Input:
My Output:
Input:
Code: Select all
15
1000 500 200
15 5 3
117 111 6
958 54 54
666 654 55
545 21 12
878 500 465
900 250 150
88 54 12
20 10 8
18 18 18
12 5 4
545 500 1
42 32 12
6 5 4
Code: Select all
corected after AC...
Case 1: 762643459
Case 2: 27967972
Case 3: 998177293
Case 4: 531446229
Case 5: 980126982
Case 6: 648615184
Case 7: 329986694
Case 8: 9598617
Case 9: 920587914
Case 10: 125855874
Case 11: 1
Case 12: 176400
Case 13: 399786634
Case 14: 387022056
Case 15: 5
Last edited by mmonish on Sun Sep 21, 2008 2:54 pm, edited 1 time in total.
Re: 11481  Arrange the Numbers
Input :
My Ac's output :
Code: Select all
2
1000 500 200
15 5 3
Code: Select all
Case 1: 762643459
Case 2: 27967972
Re: 11481  Arrange the Numbers
@ srrajesh,
http://answers.yahoo.com/question/index ... 200AAXSD4I
http://mathworld.wolfram.com/Derangement.html ("Nicholas Bernoulli also solved the problem using the inclusionexclusion principle")
See the following links:srrajesh wrote:Can you explain a little more?Robert Gerbicz wrote:Use inclusionexclusion principle.
Inclusion and exclusion on what?
http://answers.yahoo.com/question/index ... 200AAXSD4I
http://mathworld.wolfram.com/Derangement.html ("Nicholas Bernoulli also solved the problem using the inclusionexclusion principle")
Re: 11481  Arrange the Numbers
thx Ron..
silly mistake in my coding.now i get AC..
i solved it with dp.
silly mistake in my coding.now i get AC..
i solved it with dp.
Re: 11481  Arrange the Numbers
Whats wrong with my thinking 
From first m we need to choose k, thats mCk
for remaining m  k positions we can't use the first remaining m  k numbers..
So we fill those positions with from end n  m number.
The way we can do that is (nm)P(mk)
Now we have remaining nm positions and nm numbers
We can fill that with (nm)!
So in my thinking the solution to (n,m,k) is simply mCk * (nm)P(mk) * (nm)!
I know I am missing something. Can anyone verify
Thanks
From first m we need to choose k, thats mCk
for remaining m  k positions we can't use the first remaining m  k numbers..
So we fill those positions with from end n  m number.
The way we can do that is (nm)P(mk)
Now we have remaining nm positions and nm numbers
We can fill that with (nm)!
So in my thinking the solution to (n,m,k) is simply mCk * (nm)P(mk) * (nm)!
I know I am missing something. Can anyone verify
Thanks
hmm..