CHEFPSA algorithm

editorial
1

Let us consider sequence of n numbers as follows:

x1 x2 x3 . . . xn

The prefix sums are:

x1 (x1+x2) (x1+x2+x3) (x1+x2+x3+x4) . . . (x1+x2+x3+…xn)

= n.x1 + (n-1).x2 + (n-2).x3 + . . . xn

Similarly, the suffix sums are:

xn (xn+x(n-1)) (xn+x(n-1)+x(n-2)) (xn+x(n-1)+x(n-2)+x(n-3)) . . . (xn+x(n-1)+x(n-2)+x(n-3)…x1)

= n.xn + (n-1).x(n-1) + (n-2).x(n-2) + . . . x1

If we add all prefix and suffix sums, the combined term becomes:

n.x1 + (n-1).x2 + (n-2).x3 + . . . xn
+
x1 + 2.x2 + 3.x3 + . . . n.xn

= (n+1)x1 + (n+1)x2 + (n+1)x3 + . . . (n+1)xn

= (n+1)(x1+x2+x3+…+xn)

= (n+1) . sum(x)

The value for sum(x) can be determined as follows:

sum(x) = (sum of all prefix and suffix sums) / (n+1)

Note that sum(x) may not be always the largest value especially if any of numbers in original list (x1 to xn) contains negative values. We can use above formula to determine the value of sum(x) in all cases, whether original sequence contains +ve or -ve numbers, it doesn’t matter, the formula will give us the correct sum(x) value.

For example, consider following example with suffix and prefix sums (in some random order):

5 3 10 7 5 10

Sum of all above numbers is: 40 and n=3 so the sum of original numbers is 40/(3+1) = 10

I generated above prefix and suffix sums using 5 -2 7. There are other possible sequences that can result in same prefix and suffix sums, but their sum has to be 10.

Note that 10 appears twice. If sum(x) does not appear twice in given prefix and suffix sums, then, it is an invalid input and no solution is possible. So the result in such case is zero.

Remove the two sum(x) numbers from the list, and arrange the remaining numbers in ascending order:

3 5 5 7

This forms a list of numbers whose count is 2(n-1) which is 2.(3-1) = 4 in this case.

Notice that addition of first and last numbers is also sum(x). Similarly, the addition of second and last but one is also sum(x). This is the case for all such pairs. If it is not, then, solution is not possible and the result is zero.

Why is this so? How can we draw such a conclusion?

Consider the original sequence: 5 -2 7
following table shows prefix and suffix sums for each of the position as follows:

Original numbers : 5 -2 7
Prefix sums(up to the position) : 5 3 10
Suffix sums(up to next position) : 5 7 0
Addition of prefix & suffix sum : 10 10 10

In above table, in each column, the value for prefix and suffix sums mentioned are for the two sub-lists of the origianl sequence. The addition of these two sub-lists equals the addition of all numbers from the entire list.

For example:
at position 1, the two sub-lists are: (5) (-2 7)
at position 2, the two sub-lists are: (5, -2) (7)
and at position 3, the two sub-lists are: () (5 -2 7)

The first sub-list is the prefix sum at that particular position, second sub-list is the suffix sum. Their sum must equal sum(x). Basically, it does not matter at which position the list of numbers is split in two parts; the sum of two sub-lists always must equal to the sum of entire list. Hence the proof.

Hence for each prefix sum there must exist one suffix sum such that their addition is equal to sum(x). If this is not the case, then, solution is not possible. And the answer is zero in such case.

So in above example, there are 2 pairs of prefix and suffix sums: (3 7) and (5 5).

One particular sequence of prefix sums uniquely defines sequence of original numbers. So to compute the number of original sequences, we need to determine the number of possible sequences of prefix sums.

For the given example, following are all possible permutations:

                                                          Case 1           Case 2          Case 3          Case 4

Prefix sums : 3 5 10 7 5 10 5 3 10 5 7 10
Suffix sum up to next position: 7 5 0 3 5 0 5 7 0 5 3 0
original numbers : 3 2 5 7 -2 5 5 -2 7 5 2 3

For this example, the answer i.e. the count for different possible sequences is 4.

The prefix sums can be generated by permuting in following manner:

  1. From the pair of prefix and suffix sum that adds to sum(x), any number can be prefix sum. So if these are different numbers, then, the possibilities are doubled.

  2. We can arrange (n-1) prefix sums in any order. If all the prefix sum values are different, then, we will have (n-1)! number of counts for prefix sums. But if some prefix sums are repeated, then, the count can be obtained by using npr formula.

In general, there exists (n-1) pairs of prefix and suffix sums that add exactly to sum(x). Out of these, if any pair repeats, then we maintain a count of how many times that pair repeats. Let us say we have got “k” different pairs of prefix and suffix sums with counts as n1, n2, n3, . . . , nk where k is the number of unique pairs. And let us say “u” as the number of pairs containing different values for prefix and suffix sum, then the formula for count is:

(n-1)! * 2 ^ u

(n1! * n2! * n3! . . . nk!)

For above example:
n = 3
k = 2
n1 = 1 (pair: (3 7) appears once)
n2 = 1 (pair: (5 5) appears once)
u = 1 because there is only one pair (3 7) that has prefix sum != suffix sum.

Hence the count becomes:

(3-1)! * 2 ^ 1
________________ = 2*2 / 1 = 4
(1! * 1!)

4 Likes
2

@rushikdm will you please help me, I am getting WA and TLE by using this logic :

for _ in range(int(input())):
    n = int(input())
    x = list(map(int,input().split()))
    xsm = sum(x) 
    sm = xsm//(n+1)
    x.append(0)
    x.append(0)
    x.sort()
    if xsm%(n+1)!=0 or x[-1]!=sm or x[-2]!=sm:
        print(0)
        continue
    y = {}; tmp = []; flag = False; u = 0
    for i in range(2,n+1):
        if x[i]+x[2*n-i+1]==sm:
            if [x[i],x[2*n-i+1]] in tmp:
                y[str(x[i])+str(x[2*n-i+1])] += 1
            else:
                y[str(x[i])+str(x[2*n-i+1])] = 1
                tmp.append([x[i],x[2*n-i+1]])
            if x[i]!=x[2*n-i+1]:
                u += 1
        else:
            flag = True
            break
    if flag:
        print(0)
        continue
    f=1
    for i in y:
        prod = 1
        for j in range(1,y[i]+1):
            prod = (prod*j)
        f = (prod*f)%100000007
        
    facto = 1
    for i in range(1,n):
        facto = (facto*i)%100000007
    print((int((facto)*2**u)//f)%100000007)
3

Hello @nagesh_reddy,

Nice to connect with you. I went through your code and here is what I think may be the reason for WA:

What is the need to append 0 (two times) to x?

In above code, first condition is proper. But second and third conditions are incorrect. This is because, after sorting, the last two entries need not be equal to “sm”. This can happen if the original sequence contains negative numbers. For example the prefix and suffix sums for sequence [3 -5 2] are [3 -2 0 2 -3 0], after sorting the second list, it becomes [-3 -2 0 0 2 3]. For this example, sm = 0 but the last two numbers (after sorting in ascending order) are NOT equal to 0.

The algo needs to be modified as follows:

After sorting the input numbers, delete two entries from it whose values are equal to sm. If the list does not contain 2 elements with value = sm, then, answer is 0.

Above modification will most probably solve WA problem with your code. I could not completely understand the logic and your code for the computation of prod, facto and finally the answer. The final formula is: n! / (n1! * n2! * n3! . . . nk!) * 2 ^ u But I could not find division happening anywhere in your code.

And the reason for TLE is because of the time consumed in computing prod, facto etc. You can pre-compute values for modulo and inverse modulo for factorials of numbers from 1 to 10^5. Here is link to the related discussion : Best known algos for calculating nCr % M - #2 by gamabunta

I am not a python expert. You can find my C++ code here: CodeChef: Practical coding for everyone

I hope it helps you in figuring out the problem and implementing correct solution. Best of luck to you and happy coding and learning :slight_smile:

Thanks & Regards,
-Rushikesh.

2 Likes
4

Thanks a lot bhai @rushikdm for spending time on my query. I understood where am I going wrong.
I have modified my logic according to your explanation. But still giving me wrong answer. It’s been 4 to 5 days now I am on this problem. I think I am not up to this level of understanding capabilities. BTW you also don’t the Python, I won’t give up on it but will give some gap to this problem, may be will look into this when I reach this level of ability to understand may be in a couple of weeks.

Thanks a lot bro :hugs: for the time.