PROBLEM LINK
Author: Yash Chandnani
Tester: Mayank Pugalia
Editorialist: Mayank Pugalia
DIFFICULTY:
MEDIUM
PREREQUISITES:
A bit of observation and simple pattern recoginition
PROBLEM:
Chef has an array A which is a permutation of natural numbers till n. He defines value of an array as no of elements in the array whose neighboring elements have sum at least k.(Note that first and last element of an array have only 1 neighboring elements where as remaining elements have 2 neighboring elements each.)
You don’t know the permutation that chef has, so you decide to find the sum of the values of all possible permutations. Given n and k you need to find this sum and output it modulo 1000000007 (109+7).
EXPLANATION:
For a certain permutation we have find how many elements are there such that sum of their neighbouring element’s >= K. let the number of of such elements be X, so we have to report the sum of all such X for every permutation.
If we check for all permutation then the complexity becomes O(n!), so brute is not possible!
So we can look for some patterns! One thing to notice here is that we just have to count the number of pairs such that their sum is >= K!
Apart from these we also can count those single numbers that are >= k (for single neighbor case)
Such elements can be kept at position 2 and n-2
let us split the solution into two parts and one special case!
First: When n<=k
Lets take an example to understand the pattern
n=7,k=6
lets consider (x,y) to be a pair,
y 1 2 3 4 5 6 7
x
1 0 0 0 0 1 1 1 ->3 pairs
2 0 0 0 1 1 1 1 ->4 pairs
3 0 0 1 1 1 1 1 ->5 pairs (3,3) same element pair
4 0 1 1 1 1 1 1 ->6 pairs (4,4) same element pair
5 1 1 1 1 1 1 1 ->7 pairs (5,5) same element pair
6 1 1 1 1 1 1 1 ->8 pairs (6,6) same element pair
7 1 1 1 1 1 1 1 ->9 pairs (7,7) same element pair
wherever it is 1 it means the pair is valid!
Here we can see that the number of pairs is
(3+4+5+6+7 - (3)(same element pair (x,x)) ) + (7+7 - (2)(same element pair (x,x)))
(3+4+5+6+7 - (3)) can be reduced to (1+2+3+…+n)-(1+2+…+n-k+1)-(k-ceil(k/2)(for same element pair)
which is equal to → ((n(n+1))/2)-(((n-k+1)(n-k+2))/2)-(k-ceil(k/2)). O(1)
(7+7 -(2)) can be reduced to ((n-1)(n-k+1)). O(1)
let P be the total number of pairs, we can see that each pair can be placed at (n-2) places and for every place remaining (n-2) elements can be placed in (n-2)! (! means factorial) ways.
so in the final answer these P pairs will contribute Px(n-2)x((n-2)!) Points O(1)
Along with the above answer we need to consider the single elements which are >=k and <=n.
lets say there are C single elements, so these elements can be placed at position 2 ans n-2,
So it can be placed at 2 places and the rest elements can be placed in (n-1)! (! means factorial)
So again we add (2C((n-1)!)). O(1)
So the Final answer will be Px(n-2)x((n-2)!) + (2C((n-1)!))
Second: When n>k
Lets take an example to understand the pattern
n=7,k=10
lets consider (x,y) to be a pair,
y 1 2 3 4 5 6 7
x
1 0 0 0 0 0 0 0 ->0 pairs
2 0 0 0 0 0 0 0 ->0 pairs
3 0 0 0 0 0 0 1 ->1 pairs
4 0 0 0 0 0 1 1 ->2 pairs
5 0 0 0 0 1 1 1 ->3 pairs (5,5) same element pair
6 0 0 0 1 1 1 1 ->4 pairs (6,6) same element pair
7 0 0 1 1 1 1 1 ->5 pairs (7,7) same element pair
wherever it is 1 it means the pair is valid!
Here we can see that the number of pairs P is
(1+2+3+4+5 - (3)(repeating same element (x,x)) )
(1+2+3+4+5 - (3)) can be reduced to:
(1+2+…+(2n-k+1))-max(0,(n-ceil(k/2)+1)(for repeating element pairs)
which is equal to → (((2n-k+1)*(2n-k+2))/2)-max(0,n-ceil(k/2)+1). O(1)
We take max because (n-ceil(k/2)+1) might go negative meaning no same element pair exists!
Here C will be zero because there are no elements >=k and <=n
So the Final answer will be Px(n-2)x((n-2)!)
Special Case
It is nothing but when the answer will be Zero, It will be zero when k-n>=n
We should use % at right places to avoid overflow and data loss!
COMPLEXITY:
Factorial can be precalculated and for each case it takes constant time i.e O(1)
So over all the Complexity is O(T)
SOLUTION:
can be found here