Page **1** of **1**

### 11481 - Arrange the Numbers

Posted: **Sat Sep 13, 2008 8:21 pm**

by **Ron**

need help...!!!

i am stuck since contest time, but i have no ability to solve it myself.

please, give me some hints.

### Re: 11481 - Arrange the Numbers

Posted: **Sat Sep 13, 2008 9:33 pm**

by **Robert Gerbicz**

Use inclusion-exclusion principle.

### Re: 11481 - Arrange the Numbers

Posted: **Sun Sep 14, 2008 4:16 am**

by **andmej**

Is this DP?

### Re: 11481 - Arrange the Numbers

Posted: **Sun Sep 14, 2008 6:57 am**

by **Naani**

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.

### Re: 11481 - Arrange the Numbers

Posted: **Sun Sep 14, 2008 9:10 am**

by **srrajesh**

Robert Gerbicz wrote:Use inclusion-exclusion principle.

Can you explain a little more?

Inclusion and exclusion on what?

### Re: 11481 - Arrange the Numbers

Posted: **Sun Sep 14, 2008 11:12 pm**

by **Monsoon**

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

### Re: 11481 - Arrange the Numbers

Posted: **Thu Sep 18, 2008 5:06 am**

by **mmonish**

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
```

### Re: 11481 - Arrange the Numbers

Posted: **Thu Sep 18, 2008 8:43 am**

by **Ron**

Input :

My Ac's output :

Code: Select all

```
Case 1: 762643459
Case 2: 27967972
```

### Re: 11481 - Arrange the Numbers

Posted: **Sat Sep 20, 2008 6:14 am**

by **DP**

@ 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")

### Re: 11481 - Arrange the Numbers

Posted: **Sun Sep 21, 2008 1:03 pm**

by **mmonish**

thx Ron..

silly mistake in my coding.now i get AC..

i solved it with dp.

### Re: 11481 - Arrange the Numbers

Posted: **Tue Jun 14, 2011 8:26 pm**

by **newkid**

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