11481 - Arrange the Numbers

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

11481 - Arrange the Numbers

Post by Ron » Sat Sep 13, 2008 8:21 pm

need help...!!!
i am stuck since contest time, but i have no ability to solve it myself.
please, give me some hints.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11481 - Arrange the Numbers

Post by Robert Gerbicz » Sat Sep 13, 2008 9:33 pm

Use inclusion-exclusion principle.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11481 - Arrange the Numbers

Post by andmej » Sun Sep 14, 2008 4:16 am

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

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

Re: 11481 - Arrange the Numbers

Post by Naani » Sun Sep 14, 2008 6:57 am

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.
I am signing an important document!

srrajesh
New poster
Posts: 23
Joined: Sun Sep 30, 2007 9:02 pm

Re: 11481 - Arrange the Numbers

Post by srrajesh » Sun Sep 14, 2008 9:10 am

Robert Gerbicz wrote:Use inclusion-exclusion principle.
Can you explain a little more?
Inclusion and exclusion on what?

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Re: 11481 - Arrange the Numbers

Post by Monsoon » Sun Sep 14, 2008 11:12 pm

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

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11481 - Arrange the Numbers

Post by mmonish » Thu Sep 18, 2008 5:06 am

I tried to solve this prob but getting WA.Anyone please check the following I/O..
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
My Output:

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.

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 11481 - Arrange the Numbers

Post by Ron » Thu Sep 18, 2008 8:43 am

Input :

Code: Select all

2
1000 500 200
15 5 3
My Ac's output :

Code: Select all

Case 1: 762643459
Case 2: 27967972

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Re: 11481 - Arrange the Numbers

Post by DP » Sat Sep 20, 2008 6:14 am

@ srrajesh,
srrajesh wrote:
Robert Gerbicz wrote:Use inclusion-exclusion principle.
Can you explain a little more?
Inclusion and exclusion on what?
See the following links:
http://answers.yahoo.com/question/index ... 200AAXSD4I
http://mathworld.wolfram.com/Derangement.html ("Nicholas Bernoulli also solved the problem using the inclusion-exclusion principle")

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11481 - Arrange the Numbers

Post by mmonish » Sun Sep 21, 2008 1:03 pm

thx Ron..
silly mistake in my coding.now i get AC..
i solved it with dp.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 11481 - Arrange the Numbers

Post by newkid » Tue Jun 14, 2011 8:26 pm

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 (n-m)P(m-k)
Now we have remaining n-m positions and n-m numbers
We can fill that with (n-m)!

So in my thinking the solution to (n,m,k) is simply mCk * (n-m)P(m-k) * (n-m)!

I know I am missing something. Can anyone verify
Thanks
hmm..

Post Reply

Return to “Volume 114 (11400-11499)”