PROBLEM LINK:
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 
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.
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 .
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
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 type pair will exist where X_i=X_{2n-i}=Sum/2 (i.e. y_m is the only variable needed to account for pairs where both elements are same).
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 
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) -
- a == b
- 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!
????????
.
editorial
