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.