### Sammmmmmm's blog

By Sammmmmmm, history, 11 days ago,

Given an array of n integers. In 1 operation you can swap 2 adjacent elements a[i] and a[i + 1] if and only if a[i] + a[i + 1] <=

k. Count the number of possible arrays that can be created using a series of operations (possibly none). Two arrays a and b are

considered different if there exists an index i so that a[i] != b[i]

N <= 1e5

K <= 1e9

Ai <= 1e9

Thanks!

• +1

 » 11 days ago, # | ← Rev. 2 →   +13 correct me if i'm wronglet mn be the min element if A[i] + mn > k then pos i is fixed lets make new array B which contains all A[i] such that A[i] + mn <= k ans will be all possible permutations of B edit : above soln is for the case when we can swap any 2 positions for the case of swaping only adjacent positions break the array into subarrays such that for each subarray max - min <= k ans will be product of no. permutation of all subarrays. 
•  » » 11 days ago, # ^ |   0 No it is wrong Consider this array K=10, arr = [3,100,2] your algorithm will give 2 permutations, but actual answer is 1
•  » » » 11 days ago, # ^ |   0 you are correct. i misread the problem please verify the edit part. Thanks!
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 [1, 10, 2, 10, 3, 10], k: 5the answer here is one since you can't swap any two adjacent element, but the B array will be: 1,2,3, which the number of permutations are 6
•  » » » 11 days ago, # ^ |   0 yes, you are correct i misread the problem i have corrected it can you please verify it again
•  » » » » 11 days ago, # ^ |   0 Bro, I typed all that s**t as a solution, and u explained it in 2 sentences, yes it's indeed correct.
•  » » » » » 11 days ago, # ^ |   0 thanks bro for verifying it.
 » 11 days ago, # |   0 why downvotes this is a good question
 » 11 days ago, # | ← Rev. 5 →   +1 I have this solution:(the indexing for the array is one based):If too long to read: https://codeforces.com/blog/entry/129493?#comment-1149165 simplifies itEDIT: Now that I think about it, there exist a more clever and cleaner way to implement this approach, but I wrote the first thing that came to mind, so if you wanna read it:Although the part for calculation the permutations is indeed required, even if u use the other clever implementation. So yes that might be helpful Detailed solution, also talked about details way of implementationmaintain a variable ans initially set to 1, and a vector tmp. (having it always sorted like a multiset won't bother). You start from index 2, if you could swap the element with index 1, you'll insert $a_1$ and $a_2$ into the tmp, otherwise leave it empty, now going to next index, there are 2 possible scenarios:1. tmp is empty: you just check if you can swap $a_i$ with $a_{i-1}$, if u can, insert both into tmp, otherwise advance to the next index.2. tmp is not empty, there are again 2 scenarios:2.1: there exist an element less or equal to $a_i - k$, in that case, you insert $a_i$ into the multiset and advance to the next index.2.2: there doesn't exist ...: multiply the ans variable by the number of permutations the multiset can have, empty the multiset and advance.after the n'th element, just multiply the answer by the number of permutations the multiset has, and then output it.For calculating the permutations, it's generally like this: $x! / (cnt_1! * cnt_2! * \cdots)$, where the $cnt_k$ is the number of occurrences of the k'th element(since 1,2,1 and 1,2,1 are the same, the number of permutations of this example is: $3!/(2!*1!)$ which is 3. To calculate that, have a variable: dominator, every time you insert a new element to the multiset, the dominator will get multiplied by the current count of that element in the multiset, which can be accessed using a map.and for the numerator, use a standard factorial calculation. The overall time complexity would be a O(n*log(n)) but it has a lot of constant factors, for map, multiset, and multiplying big integers module a mod.of course, the answer of the problem should be calculated modulo a prime otherwise it's not practical for cp.
•  » » 11 days ago, # ^ |   0 You don't need to have a multiset, have 3 variables: mn, mx, and length, while advancing the new vertex, if the new_mn - new_mx <= k, the length gets incremented.otherwise, the answer gets multiplied by (length! / (all those cnt factorials)). which may help the complexity to lose some constant factor
•  » » » 11 days ago, # ^ |   0 Also, keeping the dominator and numerator in 2 different variables all the time and calculating the mod division only once is a good performance boost
 » 11 days ago, # |   -8 Bro this comment section turned into a place for specialists(everyone who commented was spec)
•  » » 11 days ago, # ^ |   0 oops