Discussion for PERMUTE

Please provide explanation and logic behind the problem.

1 Like

the question just required some pattern searching…u can make a matrix for each n,m maybe till n=8…then for given n,m see n-1,m-1 and n-2,m-2…so on till m=2n-1…u wil notice that (m-n+1)! is being multiplied by m-n ans m-n+1 alternatively thats it then just use modular expo to solve…!!!

2 Likes

The number of elements that could possibly conflict is given by k = 2*n - m.
The remaining (n-k) elements can be placed without causing any conflicts among themselves and the number of ways to place them is (n-k)!. There are n-k+1 gaps(or slots).

The conflicting elements are
N, N-1, N-2, N-3, …, N-(k-1)

N conflicts with all other conflicting elements, so we choose one of the (n-k+1) gaps and place it there in (n-k+1)C(1) ways, effectively reducing the number of gaps to n-k. Also since, N-(k-1) + N-1 = 2*N-k = m <= m, therefore, N-(k-1) can no longer be considered a conflicting element.

N-1 conflicts with every other remaining element except N-(k-1).
So let’s place N-(k-1) in one of (n-k) gaps in (n-k)C(1) ways. But inserting this element creates another gap, making the number of gaps n-k+1 again. Next we place N-1, in one of the (n-k+1) gaps in (n-k+1)C(1) ways, reducing the number of gaps back to (n-k) since all the remaining elements conflict with it and can’t be placed in it’s slot.

Similarly, N-2 conflicts with all the remaining elements except the 2nd last element (N-(k-2)). We then place (N-(k-2)) in one of the (n-k) gaps in (N-k)C(1) ways, creating another gap. Then we place N-2 in one of the (n-k+1) gaps, reducing the number of gaps back to (n-k).

The number of gaps keeps oscillating between (n-k+1) and (n-k).

So the answer comes out to be (n-k)! * (n-k+1)^((k+1)/2) * (n-k)^(k/2)

30 Likes

See the simple code at http://www.codechef.com/viewsolution/2276715.

This problem yields a beautiful recurrence.
Let k=M-N and line up the numbers in increasing order

1,2,3,4,…k,1+k,2+k,…,N-3,N-2,N-1,N

Note that:


N can have 1,2,3,…k as its neighbors (k neighbors)

N-1 can have 1,2,3,…k,k+1 as its neighbors (k+1 neighbors)

N-2 can have 1,2,3,…k,k+1,k+2 as its neighbors (k+2 neighbors)


and so on.

Lets call the numbers 1,2,3,…,k-1,k as safe, i.e. they can be cast as neighbor of any other number without fear.

Let F(N,k) = Possible ways we are asked to compute with neighbors arrangement as above

So, essentially we are being asked to compute F(N,k)

Let’s first try placing N. There are 2 possibilities:

  1. Either N comes at first position (or last position which is symmetric to first position)
  2. Or, N is placed somewhere in between first and the last position.

Let G(N,k) = No. of permutations corresponding to 1 above

Let H(N,k) = No. of permutations corresponding to 2 above.

Then we have: F(N,k) = 2*G(N,k) + H(N,k) (2 time G(N,k) is due to symmetry of placing either at 1st or last position)

Let’s calculate both G(N,k) and H(N,k) independently

Computation of G(N,k):

Once N is placed at first position, it can only have one of 1,2,3…k as it neighbour at 2nd position. So, there are k ways of choosing its neighbor. Without loss of generality lets choose its neighbour as k.

So, the remaining numbers are
1,2,3,4,…k-2,**k-1,k+1,**k+2,…,N-3,N-2,N-1 (Note that k and N are no longer present)

Let’s relabel these remaining numbers as:

1,2,3,4,…k-2,k-1,k,k+1,…,N-4,N-3,N-2

where:

1,2,3,…k-1 remain as it is

k+1 becomes k

k+2 becomes k+1

N-2 becomes N-3

N-1 becomes N-2

With this:


N-2 can have 1,2,3,…k-1,k as its neighbors (k neighbours)

N-3 can have 1,2,3,…k-1,k,k+1 as its neighbors (k+1 neighbours)

N-4 can have 1,2,3,…k-1,k,k+1,k+2 as its neighbors (k+2 neighbours)


There are N-2 numbers and this is precisely the definition of F(N-2,k) (refer the definition of F(N,k) above)

So, G(N,k) = F(N-2,k)

Computation of H(N,k):

Now let’s try putting N at any place between 1st and last. It can have k * (k-1) safe neighbors.

So, some particular permutation might look like

1,2,3,…,k-3,k-2,(k-1,N,k),N-1,k+1,N-2,k+2,…

and some other might look like, say:

3,N-2,1,N-1,2,…,(k-1,N,k), 4,5,…,k-3,k-2,k+1,k+2,…

Both are valid permutations for H(N,k)

Whatever be the permutation, one thing is certain that (k-1,N,k) will always move together as a group
since both k-1, and k are safe, we can equivalently write the permutation immediately above as:

3,N-2,1,N-1,2,…,k,4,5,…k-3,k-2,k+1,k+2,…

Now, following relabeling scheme of G(N,k) we similarly have:


N-2 can have 1,2,3,…k-1,k as its neighbors (k neighbours)

N-3 can have 1,2,3,…k-1,k,k+1 as its neighbors (k+1 neighbours)

N-4 can have 1,2,3,…k-1,k,k+1,k+2 as its neighbors (k+2 neighbours)


There are N-2 numbers and this is precisely the definition of F(N-2,k) (refer the definition of F(N,k) above)

So, H(N,k) = k * (k-1) * F(N-2,k)

So, F(N,k) = 2 * G(N,k) + H(N,k) becomes

F(N,k) = 2 * k * F(N-2,k) + k * (k-1) * F(N-2,k)

i.e,

F(N,k) = k * (k+1) * F(N-2,k)

Since k is constant, having it part of function F is confusion, let’s get rid of it
Lets instead write it as:

F(N) = c * F(N-2) where c = k * (1+k)

or F(N) = (c^2) * F(N-4)

or F(N) = (c^3) * F(N-6)

or F(N) = (c^r) * F(N - 2 * r)

Note that F(N) = N! if k=N-1 (all numbers are safe)

So, the idea is to find N - 2 * r such that it just becomes equal to k or k+1 (depending on parity of difference between N and k being even or odd respectively)

e.g.,


Example 1.

For N=7, M=10, k=M-N becomes 3, c=k*(1+k) becomes 12, so

F(7,3) -> (12^1) * F(5,3) -> (12^2) * F(3,3) = (12^2) * 3! = 864 [Stop here since 3 >= 3, last such possible step]

Example 2.

For N=7, M=9, k=M-N becomes 2, c=k*(1+k) become 6, so

F(7,2) -> (6^1) * F(5,2) -> (6^2) * F(3,2) = (6^2) * 3! = 216 [Stop here since 3 >= 2, last such possible step]

Example 3.

For N=6, M=8, k=M-N becomes 2, c=k*(1+k) become 6, so

F(6,2) -> (6^1) * F(4,2) -> F(6^2) * F(2,2) = (6^2) * 2! = 72 [Stop here since 2 >= 2, last such possible step]

Example 4. (sample input given in problem)

For N=5, M=8, k=M-N becomes 3, c=k*(1+k) become 12, so

F(5,3) -> (12^1) * F(3,3) = (12^1) * 3! = 72 [Stop here since 3 >= 3, last such possible step]


So, in general F(N) = (c^r) * (N - 2 * r)! where r is largest integer such that N - 2 * r >= k

i.e., N - 2 * r >= (M - N)

i.e., r is largest integer such that: 2 * r <= 2 * N - M

i.e., r is largest integer such that: r <= (2 * N - M)/2

so, r = (2 * N - M)/2 (this division is C/Java integer division)

So, final answer is:

(c^r) * (N - 2 * r)!

where r = (2 * N - M)/2, c = k * (1+k), and k = M-N

Field test: http://www.codechef.com/viewsolution/2251005

14 Likes

Brilliant solution @gsbatia. Very neatly explained :slight_smile: !

2 Likes

brilliant answer

Thanks for the answer Ishan. I spent 2 days to solve this question, still couldn’t do it. Some eccentric pattern recognition there. You need codey sense(~ spidey sense for coders) to think that :D.

gud way of thinking… i solved this problem by generating solutions till n=11 and m=21 using next_permutation(). Then derived formula from them.

This could well be the editorial…

3 Likes

crystal clear answer… thank you

1 Like

Excellent explanation. Thanks!!