CHEFPSA - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Ritesh Gupta
Tester- Encho Mishinev
Editorialist- Abhishek Pandey

DIFFICULTY:

Medium

PRE-REQUISITES:

\sout{Dynamic Programming} Combinatorics, Mathematics

PROBLEM:

Given an array X consisting of prefix and suffix values of some array A, find how many arrays A exist for a given array X. Report your answer modulo 10^9+7.

Note- For entire editorial, please take note of below conventions to avoid confusions:

  • P_i=Prefix[i]
  • S_i=Suffix[i]
  • Sum=\text{sum of all array elements}
  • 1-based indexing is followed unless mentioned otherwise.
  • Suffix[i]=S_i= Sum of last i elements in A, which is exactly same as how suf is defined in the problem. The conventional definition of Suffix[i]= Sum of elements from [i,N] is NOT used in the editorial!!

QUICK-EXPLANATION:

Key to AC- Prefix[i]+Suffix[n-1-i]=\text{Sum of all elements of array}. With this in mind, think in terms of combinatorics on what we can do!

Let the sum of all elements in A be Sum. If we insert 2 zeroes in X and sort it, then we get X_i+X_{2n-i}=S (using 1-based indexing) for all elements in X. If this is not true for all indices i in X, then there are no valid A's in existence. Henceforth, we are dealing with this modified array X and 1-based indexing.

If valid A's exist, then we will pair each unpaired X_i with its corresponding X_{2n-i}. Now, take note of following-

  • One of these (i.e. X_i or X_{2n-i}) will be P_j and other will be S_{n-j} for original array A. We essentially have 2 choices here.
  • If I fix one of X_i or X_{2n-i} to be some prefix P_j, then the other element is forced to be S_{n-j}. We do not have a choice here!

With these 2 in mind, we first keep a frequency or count of all the pairs we have. Let y_1,y_2,...,y_m be the frequency of the pairs, with y_m being frequency of pairs with X_i==X_{2n-i}. We use following intuition to find the answer:

  • X_i can be Prefix or Suffix! X_{2n-i} will take the leftover option. So we have 2 choices except for when X_i==X_{2n-i}. This contributes a factor of 2^{N-1-y_m} to the answer.
  • All the X_i's can be assigned indices in (N-1)! ways if they are all distinct. With this in mind, we use the formula to arrange N objects where y_1,y_2,...,y_m are duplicates. This contributes a factor of \large \frac{(N-1)!}{y_1!*y_2!*...*y_m!)} where y_i is frequency of the pair.

Final Answer =\large \frac{(N-1)!}{y_1!*y_2!*...*y_m!}*2^{N-1-y_m}

EXPLANATION:

We will deal with following in the Explanation Section:

  • What I feel is the necessary mindset if you want to solve this (and similar) question(s) easily.
  • Play with the X array.
  • Discussing the Combinatorics and Deriving the Formula.

So, lets begin without delay :slight_smile:

The necessary mindset

\text{`` Omg this Q is solved by only X people in my division! "}
\text{`` This MUST be dp. I do not know dp. Bye bye!"}

Ditch the first viewpoint entirely. You are defined by YOUR skills. You know, eons eons ago when I was solving a particular long in summer what happened?

I did P_1,P_2,P_3. Got only partials in P_4,P_5, thanks to my huge knowledge gap in time complexity and sheer stupidity, and I then fully solved P_6! Thats when I felt that hey, I can do more. I know its very tempting to just come to long, solve what you can and then quit. I understand when people criticise that 10 days for 11 problems is perhaps not the best rate of learning.

But give some time. What I see many people doing, they do not invest enough time at all. If they cannot think of the solution within 15 minute they quit. They sometimes do not even pick up pen and paper. Cmon! How are you going to do that derivation? Or see that observation which can be seen when trying some test cases?

My second quote deals with misjudging the topic. Be OPEN. Do NOT be narrow- being narrow will hurt you everywhere- in interviews, studies and jobs all alike. Be open. It is fine to feel that it is a dp problem, but be open to possibilities! Just because the modulo is 10^9+7 does not mean its a dp problem, does it?

I will be honest, I do not know if this can be solved via dp or not myself. Perhaps there can be some advanced tricks. IDK. But what I see, is, that very simple, obvious observations are used in this question and it is still medium. I see that this question just utilizes the very fundamental basics of combinatorics and is medium. I see a lot of people panicking and being narrow. I see a lot of peple losing hope and giving up! I also see the same people not coming back to read the editorial. Lets change that. :slight_smile:

Playing with the X array

I will first begin with how I feel a good coder can begin with the problem. We are given the array X which has prefix and suffix sums jumbled up. What to do?

OBSERVE! The first step to solve any problem is OBSERVATION. Can we think of any special observation here?

No, wait! I am wrong at one place. Observations are MADE special by our approach. We will observe anything and everything we can and decide which ones can be made special by our approach :slight_smile: .

The first thing coming to my mind is, that, X must have P_N and S_1 must be in the array. And they are nothing but sum of the entire array A ! Great, we have found one constraint, that Sum must be present in X and must be present twice!

Now, a lot of elements can be present twice or more, so this doesn’t really help. Can we somehow expand or work on this observation?

The above observation on Sum doesn’t directly help, but opens up the mind to think of another critical observation -

P_i+S_{n-i} is bound to be equal to Sum. This means that it must be possible to pair elements (except P_N and S_1) of X such that sum of each pair same and equal to Sum !!

From here, we are almost done playing with array X. We insert two 0's into the X for convenience in implementation, as that allows us to pair P_N and S_1 with the 0's (why?). To pair the elements, we simply sort the array X and pair X_i and X_{2n-i}. It can be proved that only these 2 could be paired together. (How?)

We maintain the frequency of each pairs and proceed to the next section :slight_smile:

Discussing Combinatorics and Deriving Formula

We will first tackle the factor of 2^{N-1-y_m} and then the factorial one.

We keep the count of frequency of each pair y_1,y_2,...,y_m where y_i is the frequency of i'th pair and y_m represents count of pair which has X_i==X_{2n-i}. Note that only 1 such pair will exist where X_i=X_{2n-i}=Sum/2.

Factor of 2^(N-1-y_m)

For each pair (X_i,X_{2n-i}), X_i can either represent P_i or S_{n-i}. Once X_i is fixed, X_{2n-i} will take the remaining choice.

Now, note this - When we added two 0's to X, we made total pairs from N to (N+1). Now, among all these (N+1) pairs, our above rule does not apply to the pairs (0,Sum) as the Sum's position is fixed! Hence, the 2 pairs are not counted in there.

Next, we know that if X_i==X_{2n-i} then it really doesn’t matter which is prefix or which is suffix. Hence, these y_m pairs are also counted out.

Hence, we have (N-1-y_m) such pairs for which we have 2 options , i.e. assign X_i to represent prefix, or assign it to represent suffix. Hence, total factor of 2^{N-1-y_m}

The factorial factor in Ans

For every pair (X_i,X_{2n-i}), if we fix the position of X_i, the position of X_{2n-i} gets fixed as well. In other words, say X_i gets assigned index j (prefix or suffix - doesn’t really matter), then X_{2n-i} has to be assigned index N-j.

Hence, essentially for each pair, we have only 1 independent element whose position we can freely decide. (Bonus - Why is this valid? Why doesn’t this lead to duplicates?)

After adding the two 0's, we have (N+1) pairs in X. Out of which, we do count the pairs (0,S) because their position is fixed. This leads to a total of (N-1) pairs.

Now, if frequency of each pair is known, we can simply use the standard formula of arranging N-1 objects when y_1,y_2,...,y_m are same, which is \large \frac{(N-1)!}{y_1!*y_2!*...*y_m!)}. Note that if the pair is occurring only once, then its y_i=1 so it has no effect on the formula.

Based on above sections, we get the final answer as-

Final Answer =\large \frac{(N-1)!}{y_1!*y_2!*...*y_m!}*2^{N-1-y_m}

SOLUTION

Setter
TBA
Tester
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long llong;
 
const llong MOD = 1000000007LL;
 
llong FastPow(llong k, llong p)
{
    if (p == 0)
        return 1LL;
 
    llong P = FastPow(k, p/2LL);
    P = (P * P) % MOD;
 
    if (p % 2 == 1)
        P = (P * k) % MOD;
 
    return P;
}
 
llong Inv(llong x)
{
    return FastPow(x, MOD-2);
}
 
llong facts[100111];
llong invFacts[100111];
 
int t;
int n;
int x[200111];
vector<int> reps;
 
int main()
{
    int test;
    int i,j;
 
    facts[0] = 1LL;
    invFacts[0] = 1LL;
    for (i=1;i<=100000;i++)
    {
        facts[i] = (facts[i-1] * i) % MOD;
        invFacts[i] = Inv(facts[i]);
    }
 
    scanf("%d",&t);
 
    for (test=1;test<=t;test++)
    {
        scanf("%d",&n);
 
        for (i=1;i<=2*n;i++)
        {
            scanf("%d",&x[i]);
        }
 
        x[2*n+1] = 0;
        x[2*n+2] = 0;
 
        sort(x+1,x+1+2*n+2);
 
        llong ans = facts[n-1];
        pair<int,int> cur;
        int skip0s = 2;
        bool first = true;
        llong swappableCoef = 1;
        reps.clear();
 
        int sum = x[1] + x[2*n+2];
        for (i=1;i<=n+1;i++)
        {
            int num1 = x[i];
            int num2 = x[2*n+3-i];
 
            if (num1 + num2 != sum)
                ans = 0;
 
            if (num1 == 0 || num2 == 0)
            {
                if (skip0s > 0)
                {
                    skip0s--;
                    continue;
                }
            }
 
            if (first)
                cur = make_pair(num1, num2);
 
            if (first || make_pair(num1, num2) != cur)
            {
                cur = make_pair(num1, num2);
                reps.push_back(1);
            }
            else
            {
                reps.back()++;
            }
 
            if (first)
                first = false;
 
            if (num1 != num2)
            {
                swappableCoef *= 2LL;
                swappableCoef %= MOD;
            }
        }
 
        if (skip0s > 0)
            ans = 0;
 
        for (i=0;i<reps.size();i++)
        {
            ans *= invFacts[ reps[i] ];
            if (ans >= MOD)
                ans %= MOD;
        }
 
        ans *= swappableCoef;
        ans %= MOD;
 
        printf("%lld\n",ans);
    }
 
    return 0;
}
  

Time Complexity=O(NLogN)
Space Complexity=O(N)

CHEF VIJJU’S CORNER :smiley:

Why 2 zeroes are inserted into X?

Have a look at the prefix array P and Suffix array S for array A-

P=A_1,A_1+A_2, A_1+A_2+A_3,...,Sum
S=Sum,Sum-A_N,...,A_2,A_1

What if we insert a 0 in both, P and S to correspond as P_0 and S_{N+1}? (Note we are using 1-based indexing!)

P=0,A_1,A_1+A_2, A_1+A_2+A_3,...,Sum
S=Sum,Sum-A_N,...,A_2,A_1,0

Now for every i, we see that P_i + S_{n-i}=Sum.

Why only Xi and X(2n-i) can be paired

Let us say that a valid pairing between X_i and X_{2n-i} does not exist. Without loss of generality, let us assume X_i got paired by X_{2n-i-1}.

Now, X_i+X_{2n-i} \neq Sum while X_i+X_{2n-i-1}=Sum.

Since X is sorted, we know that X_{2n-i-1} < X_{2n-i} (they cannot be equal else X_{2n-i} would have worked). This means that X_{2n-i} had more value than required to have the sum as Sum. Now, the next element after X_i, i.e. X_{i+1} has even greater value than X_i. Similarly holds for all elements after X_i. Hence, pairing is impossible with X_{2n-i}

Why can we chose position of Xi freely without worrying about duplicates

For each array A, we only have one Prefix and only one Suffix array. If on changing the position/index of X_i we are still getting an already counted array A, then this means that this array A has 2 or more prefix/suffix arrays, which is not possible!

Setter's Notes

Let A = {a_1, a_2, ..., a_n} consider 1-based indexing.

prefix_sum array P = {p_1, p_2, ..., p_n} where p_i denote the sum of first i elements.

suffix_sum array S = {s_1, s_2, ..., s_n} where s_i denote the sum of last i elements.

We can say that p_i + s_{n-i} = S, where S is the sum of the elements of array A. We are given an array X that contains all the elements of both prefix_sum array and suffix_sum array.

To solve the question, lets introduce the two zero elements in this array so we can divide this array into equal sum pairs. Lets sort the array and make pairs like this - first with last, second with second last element and so on. If all these pairs have same sum then we can construct some array A otherwise answer is zero.

Now, there are two types of pair(a,b) -

  1. a == b
  2. a \neq b

Remove two pairs which are equivalent to (0,S).

Let’s, we know the frequency of each type of pairs, y_1,y_2,..y_m where y_m is the frequency of pair of the first type then answer is given by -

count of array = \frac{(n-1)!}{y_1!*y_2!*...*y_m!}*2^{n-1-y_m}

lets take an example -

you are given array B = {1, 2, 5, 2, 5, 4, 4, 5, 1, 1, 3, 3, 6, 6}

Introduce two zero elements and sort the array.

B = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6}

Pairs are formed:

  • (0,6) - 2

  • (1,5) - 3 = y_1

  • (2, 4) - 2 = y_2

  • (3, 3) - 1 = y_3

Now, we just need to put this in formula and get the answer. It is very easy to deduce the formula.

Kudos to Setter

I need to give credit where its due.

If you see and think thoroughly on the question, it is a Medium difficulty question which beautifully combines basic and fundamental concepts of Combinatorics. Such questions are innovative and are not easy to come up with. Also, look at his notes he wrote so you guys can understand the solution and the thinking process better! Kudos to him for that! :slight_smile:

????????

Meme%20jan20

Related Problems
36 Likes

Fast editorial… Thanks.!

5 Likes

Why did you only subtracted the frequency of the last pair ie ym ? Shouldn’t it be the sum of all yi ?

Think! What is the reason for this factor of 2 ? The reason is that X_i can either be prefix or suffix - which is true for all pairs except when X_i == X_{n-i}

1 Like

Dont let @alei know tho :stuck_out_tongue:

1 Like

Can anyone suggest a resource for modular arithmetic for solving similar problems and more advanced concepts? Because even I got to a similar formula as in editorial but I didn’t get to know how to mod a/b in a proper way. Thanking you in advance :slightly_smiling_face: .

for those who want more easy explanation.

consider n=4 then lets say array is a, b, c ,d then we are given a ,a+b,a+b+c,a+b+c+d(prefix sums) and also suffix sums d,c+d,b+c+d,a+b+c+d. then what you can do is that there must be an element in the given prefix and suffix summ arrays which have frequency >=2;

then what you can do is that add all these elements such that a+a+b+a+b+c+a+b+c+d+d+c+d+b+c+d+a+b+c+d=total sum now see the magic we have these LHS sum as 5a+5b+5c+5d=total sum of the array then a+b+c+d=(total sum)/5; now these 5 came when we took n=4 and so the number for which frequency >=2 must be total sum of prefix suffix arrays /(n+1).
half of the task is over we got which value must have frequency>=2
now you can see if assumed array is a,b,c,d then prefix array is a,a+b,a+b+c,a+b+c+d and suffix array is a+b+c+d,b+c+d,c+d,d observe carefully that when ith element of prefix array is summed with i+1th element of suffix arrays then we get the sum a+b+c+d so the task further reduces to

finding those pairs in the given prefix suffix array whose sum is a+b+c+d. after taking out 2 occurrences of a+b+c+d as pivot. ,so the map of c++ stl comes in picture here so lets say we have got n=3. and prefix suffix array as 10 3 7 3 7 10 so the picture is very clear so by applying the above derived formula we got pivot element as 10 10 then we have to find all disjoint pairs which sum up to 10 we got 2 pairs 3 7 3 7 then lets first make prefix array obviously the remaining elements would consist of suffix array so it is insensible to make both the arrays at the same time.

now we are constructing prefix array first . so 10 is fixed 2 positions are remaining which can be occupied by anyone of 3,7 so whole possibilities are 2C12C1 now permutation part also but here we can see 3 3 are equal or 7 7 are equal so we are multiplying the answer 2!/2!. but in these case these two pairs are equal thus we divided with 2! now take another case 10 10 3 7 4 6 we fixed 10 10 as pivots remaining pairs formed are 3,7 and 4,6 now 2 places are left which can be filled in both the ways 2C12C1 and also 3!=4 thus we have to multiply the answer by 2!/1!. we can get another answer for another test case 10 10 3 7 5 5 so in these case 10 10 are pivots fixed remaining 2 places can be filled by 2C1*1C1(as 5 and 5 are equal). and also we can permute by 2! places finally multiply combinatorics part with multiplication part.

6 Likes

waiting for ENGLISH :heart_eyes: editorial

2 Likes

With only this question in mind i performed binary search to get pairs. :cry:

Totally agreed. Excellent problem @rishup_nitdgp

1 Like

I deleted the post as I thought is irrelevant. :joy:

Can someone also explain the modular arithmetic in this question. I did exact same thing but only 20 points, rest were showing SIGFPE error, and that is due to division or mod by 0 or integer overflow.
Here’s my solution

https://www.codechef.com/viewsolution/28960826

Can someone explain why am i getting TLE for similar approach.
https://www.codechef.com/viewsolution/28987176

Yuuup, the SIGFPE is being caused by a division by 0 @line 61 of your solution.

You may go through my submission for CHEFPSA here and at the top you’ll find a link to a cute article explaining the precomputation part of the modular arithmetic involved in this problem.

I hope it becomes clearer when you see how I incorporated that in my code. :slight_smile:

1 Like

Can any one help me my code passing only some of the test cases
I used two pointers approach to find pairs similar to the editorial
https://www.codechef.com/viewsolution/28988619

check “modular division blogarithms” you will get the proof of fermats theorem also

\LARGE {\color{green}BEST }\space {\color{blue} EDITORIAL } ever I seen :heart_eyes:

1 Like

Thanks a lot for the great editorial !

1 Like

Best editorial till date I have read!! Thanks

1 Like

I’m trying to submit my code in PRACTICE for CHEFPSA and I’m getting:
“Status: Error Message: No such contest exists, recheck the contest code and try again”
anyone else getting the same error??