Problem Link:
Difficulty:
Medium-Hard
Pre-requisites:
ad-hoc, math
Problem:
Given integers N and M, find how many permutations are there from 1 to N, such that the sum of adjacent numbers does not exceed M. You have that N < M < 2*N
Explanation:
Let us fill in our numbers from N downwards, let us also have two special symbols {L, R}, which denote that L an “element” to the left of all 1 to N, and R is also an “element” to the right of all 1 to N. With these {L, R} added to our 1 to N set, then when we fill in values N downwards, we just ensure that we have picked something to the left, and something to the right as well. (without {L, R}, we would have cases of whether to surround the number on two sides, or on one side).
Now, let us define “safe segments”. Basically, when we insert the number ‘n’, we would like to merge it with either a segment/number/L to the left, and a segment/number/R to the right. Further, we will consider numbers as potential “safe segments”, to avoid notational changes: that is, a safe segment is either a previously merged block, or a single number that can be merged with ‘n’.
Here are some cool things to note:
The safe segments for value n=N are {1, 2, 3, …, M-N}.
Once we merge ‘n’ with some two safe segments, then this entire merged quantity is a safe segment for ‘n-1’.
This is because, if we merge elements n with some safe segments, then the endpoints of those segments will clearly be safe to be merged with n-1 as well!
If we merge ‘n’ with L or with R, then we will be left with a segment that is ‘L’ or ‘R’.
This is basically saying that if ‘n’ is merged with ‘L’, then the left of the permutation comes before ‘n’, and nothing is changed to the left of ‘n’. In other words, the merged segment for ‘n’ now acts as a left-boundary point for future mergings.
Finally, and the most important thing to note about this, is that we need to mainly worry only about the NUMBER of safe segments when we fill in value ‘n’. This defines for us the number of choices we can make at this stage.
Initially, we have #safe segments = M-N. Interestingly, this number of safe segments will remain constant throughout! This is because, when we merge ‘n’ with two safe segments, we get one new safe ‘merged’ segment, as well as the new safe segment which is safe for ‘n-1’, but was unsafe for ‘n’ (namely the number M-n+1). Similarly, when we merge ‘n’ with one safe segment, and one of {L, R}, we reduce one safe segment (since the new ‘merged segment’ is now {L, R}) and increase one safe segment, again as the value M-n+1.
To illustrate, consider M = 17, N = 10.
For N = 10, safe segments are {1, 2, 3, 4, …, 7}
If we merge with L, we have 7 choices for the right element, and our safe segments for 9 are now {1, 2, …, 7} \ {element chosen to right of 10} U {8}. If we merge with two elements, then we get a new safe-segment, and also have 7*6 choices for this merging, while we get safe segments for 9 as {1, 2, …, 7} \ {2 elements chosen to merge with 10} U {safe segment formed from merging with 10} U {8}.
Thus, because we are adding “8” to our safe-segment set, the number of safe segments we have to consider for 10 is the same as for 9. This holds in general for n.
Ultimately, we will reach a point when all segments are safe for ‘n’, and at that point, we can permute the safe segments arbitrarily among themselves. This threshold n is in fact the value (M+1)/2.
Illustration:
The above may well have been confusing - I myself was at a loss as to how to “define” everything I needed. When definitions fail, examples work, and so…
Notations:
S = set of safe segments.
s(n) = safe segment formed by merging n with some two other safe segments
Take N = 10, M = 14.
Now, filling in n = 10:
S = {1, 2, 3, 4}
Lets say I put 2 10 3 together. That means, putting 2 10 3 together makes a new safe segment “s(10)”.
Now, filling in n = 9:
S = {1, 4, s(10), 5} : Notice how 2, 3, and 10 have merged to form “s(10)”, and how 5 was added to the set of safe segments.
Lets say I put L 9 s(10) together. That means, I now have 9 2 10 3 at the left of the permutation. I have merged 9 with L and s(10) to get L.
Now, filling in n = 8:
S = {1, 4, 5, 6}
Lets say I put 4 8 6 together. I now have a new safe segment “s(8)” which corresponds to 4 8 6.
Finally, when I consider n = 7, I notice that I can permute the remaining safe segments any way I like! I now have the elements {1, 5, s(8), 7} that can be permuted arbitrarily.
Lets say I take the permutation 5, s(8), 1, 7. Then, this case will correspond to the overall permutation of 9 2 10 3 5 4 8 6 7. Note that I’ve expanded “L”, s(10), s(8) and “R” to get the above, which is clearly feasible.
If I finally permuted it as 1, s(8), 5, 7, I would get my overall permutation as 9 2 10 3 1 4 8 6 5 7 etc.
Rest of the computation:
Let f(n, k) = number of ways of filling in the numbers such that we are filling in from n and downwards, and we have k safe segments. Then,
f(n, k) = (2 * k + k * (k-1)) * f(n-1, k).
2 * k is due to putting one safe segment to left, or to right, and k * (k-1) is due to putting one to left and another to right.
Thus, f(n, k) = (k * (k+1)) * f(n-1, k) = (k * (k+1))^2 * f(n-2, k) etc.
We also have, f((M+1)/2, k) = g(k). Now, if M is odd, we will be left with k safe segments as well as the number (M+1)/2, so g(k) = (k+1)! in this case. If M is even, we will be left with “k-1” safe segments along with the number M/2, so that leaves us with k!. (M even is given in the illustration).
Thus, our final answer is
f(N, M-N) = ((M-N) * (M-N+1)) ^ (N - (M+1)/2) * (M-N)!, if M is even
f(N, M-N) = ((M-N) * (M-N+!)) ^ (N - (M+1)/2) * (M-N+1)!, if M is odd
The above can be easily computed by precomputing factorials, and using logarithmic exponentiation. The time complexity is thus O(maxN + T * logN).
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
. but every people can solve this problem with math. just find some of N, for example you just find answer for N=1…9 then it is easy to find formula this my code