One more problem, did you check whether sum divides 2?
When we will get the setters solution… Tbh the tester solution doesn’t look user friendly anyway
Really what a beautiful Editorial! Thank u:grinning: 
1 Like
How did the tester calculated inverse factorial? I am unable to undertand that…pls elaborate that part only else soln is fine.
Hi,
The fact that the Prefix[i]+Suffix[n-1-i]=S relation holds it quite obvious (at least to me). But would it be possible to explain in a bit more detail why after the sorting of X the following relation X_i + X_{2n-i} = S still holds? I mean, this means that all the prefixes will be to the left of the sorted array and all the suffixes will be to the right of the sorted array. What’s more, their order will be such that the i-th element of the sorted array (a prefix sum) will match the (2n-i)-th element of the sorted array (a suffix sum). Is that really so easy to see and prove? Normally, I’d expect that after sorting we are going to have a bigger mess than before sorting (prefix sums and suffix sums would take arbiraty positions in the sorted array).
Best wishes
tadek
if p is any prime number and a is an integer not divisible by p,
a ^ {-1} \equiv a ^ {p - 2} \mod(p)
In this case, MOD = 1000000007 is the prime number.
In the tester’s solution,
Inv(llong x) : @line 26,
x^{-1} \mod(MOD)
is being calculated via the call to the function FastPow
return FastPow(x, MOD-2);
Considering that you understood how the factorials are being calculated @line 46, the inverse factorials are being calculated @line 47 by assigning invFacts[i] with the value of fact[i] ^{-1} which is returned by Inv with parameter fact[i].
Hope it is clear to you now. 
Thanks man I got it now!
1 Like
Hi, can someone explain how after adding 2 zeros and sorting the X holds the condition Xi+X2n-i = S with an example. Thanks in advance 
i get why we are dividing with yi but the fact that we are multiplying with 2n-1-ym means we are considering different configurations of a particular pair.
like take the example 3 3 3 3 10 7 7 7 7 10
so it can be written as (3/7) (3/7) (3/7) (3/7) and 10,10 is anyways fixed.
i cant understand the fact why we are dividing everything with yi
cause for the configuration 3 3 3 7 10 we should divide with 3!
for 3 3 7 7 10 we should divide with 2!2!
can someone please explain this .
Let’s sort the array X and only consider the first half, i.e. the first n elements, viz X1, X2, …, Xn. Some of the Xi will be Prefix and some of it will be Suffix, we don’t and can’t know which one is which but what we do know for sure that X1 <= X2 <= …<= Xn and this because we just sorted the array. Let’s for simplicity denote every Xi in [X1, Xn] by Li(the left part of the array). Now we will start generating the second part of the array, i.e. Xn+1, Xn+2, …, X2n. Let’s for simplicity, call each Xi in [Xn+1 X2n] by Ri(the right part of the array). So, for each Li we will generate it’s corresponding Ri. We will use the rule Prefix (i) + Suffix(n-i) = Sum of Array = S. Hence Li + Ri = S or Ri = S - Li.
Now, If we can prove that after generating the Right part, i.e. R1…Rn the array is completely sorted then we can prove that on sorting X the condition stated in editorial i.e. Xi and X2n-i forms a pair is satisfied. This is because we just generated the second half of the array - R, using the same condition.
Now, all we have to prove is that Ln <= R1 <= R2 <= R2 <= … <= Rn. If we can prove this than we are done.
Since Ri = S - Li, so greater the Li smaller the Ri and vice versa. So, more we move to the right of L, the element will be more to the left of R. Hence the condition that R is sorted is satisfied. This also makes the entire X sorted as L is already sorted.
1 Like
It is later proved later that there is only one way of pairing every element in array such that sum of each pair is same.
1 Like
I used same approach to solve the problem using maps,but i don’t know where it is going wrong.can you please help me.
Make all possible suffix and prefix combination by fixing the pivot.
Then try retrieving the original arrays from the combination which led to the prefix and suffix sum array. For this particular example :
Let P denote Prefix sum array and S denote suffix sum array :
One combination I could get is :
a:) P : 5 3 10
S : 10 5 7
OR
b:) P : 7 5 10
S : 10 3 5
Retrieving original array from a we have [5 -2 7] and from b we have [7 -2 5]
Similarly
Other combination :
c:) P : 3 5 10
S : 10 7 5
OR
d:) P : 5 7 10
S : 10 5 3
Retrieving original array from c we have [3 2 5 ] and from d we have [5 2 3]
Hence we have 4 initial arrays.
A can have negative values too
suffix[2] =k1 represents one sequance A1
suffix[2]=k2 represents the anthor sequence A2
k1 and k2 must be present in the input
and we dont need to know the values of A
n=2
x=4,3,2,4
after adding 2 zeros x become 0,0,4,3,1,4
after sorting X become 0,0,1,3,4,4
X[0]=0,X[1]=0,X[2]=1,X[3]=3,X[4]=4,X[5]=4
is it required to add 2 zeros or only one zero is enough?
please let me know
Read this article
@vijju123 I don’t think that ym can only be 1 or 0. it can take any value.
consider the array 1,2,3,0,0,0,0,3,2,1.
The sum of above array is 12 and there will be five pairs with both elements being 6.
okay what i meant to say is, that the original array is 1,2,3,0,0,0,0,3,2,1.
It’s prefix sum will be -> 1, 3, 6, 6, 6, 6, 6, 9, 11, 12.
It’s suffix sum will be -> 12, 11, 9, 6, 6, 6, 6, 6, 3, 1.
When you add two zeroes and merge the above two array and sort this merged array, we can see that there will be five pairs whose both the elements will be 6 -> 12/2 -> sum/2.
If my argument is wrong please point out the mistake.
@vijju123
So, I think I wrote it a bit ambiguously in the editorial to have this doubt arisen. I am treating pairs and their frequencies as different things.
When I said there would be only one pair which will have both elements equal, I meant that y_m is the only variable needed to deal with these type of pairs, for all other y_i's both elements are not the same. This helps in understanding why y_m is deducted at several places in the formula. I will change it to “one type of pairs” to be more clear. Thanks.