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!
No it is wrong
Consider this array
K=10, arr = [3,100,2]
your algorithm will give 2 permutations, but actual answer is 1you are correct. i misread the problem please verify the edit part. Thanks!
[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 6yes, you are correct i misread the problem i have corrected it can you please verify it again
Bro, I typed all that s**t as a solution, and u explained it in 2 sentences, yes it's indeed correct.
thanks bro for verifying it.
I have this solution:(the indexing for the array is one based):
If too long to read: https://mirror.codeforces.com/blog/entry/129493?#comment-1149165 simplifies it
EDIT: 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
maintain 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
ansvariable 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, thedominatorwill 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.
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
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
Bro this comment section turned into a place for specialists(everyone who commented was spec)
oops