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)
25 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…
2 Likes
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:
- Either N comes at first position (or last position which is symmetric to first position)
- 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
13 Likes
Brilliant solution @gsbatia. Very neatly explained 
!
2 Likes
crystal clear answer… thank you
1 Like
Excellent explanation. Thanks!!