PARPOLY - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dynamic Programming, Binomial Coefficients

EXPLANATION:

More than writing code, this problem requires you to sit down and work out equations on a sheet. So get yourself a piece of paper and try working out these equations yourself as you go through the editorial.

We will see two different approaches with different complexities for this problem:

SETTER’S SOLUTION:

Will be updated soon.

APPROACH

Complexity: O(MND2)

Let us define dp[m][n] = f(m,n,X)

(For ease, we will write f(m,n,X) as f(m,n) thoughout this editorial. This will not make any difference as X is constant for any particular case.)

f(m,n) = Σ P(k1x)P(k2x)…P(kmx)
where Σ ki = n

= Σk P(kx) Σ P(k1x)P(k2x)…P(km-1x) for k = n to 0

= Σk P(kx) Σ f(m-1,n-k)

= P(nx).f(m-1,0) + P((n-1)x).f(m-1,1) + … +
P(0x).f(m-1,n)

= P(nx).dp[m-1][0] + P((n-1)x).dp[m-1][1] + … +
P(0x).dp[m-1][n]

By expanding the P(cx) functions we get:

= (C0(nx)0 + C1(nx)1 + C2(nx)2 +…+ CD(nx)D) . dp[m-1][0]

+ (C0((n-1).x)0 + C1((n-1).x)1 + C2((n-1).x)2 +…+ CD((n-1).x)D) . dp[m-1][1]

.

.

+ (C0(0x)0 + C1(0x)1 + C2(0x)2 +…+ CD(0x)D) . dp[m-1][n]

Note that 0^0 is considered as 1 here.

Now, let us define another variable.
Let

sum[m][n][k] = dp[m-1][0] * n^k +
dp[m-1][1] * (n-1)^k + … +
dp[m-1][n] * 0^k

Also, let C[k] = Ck . xk

Thus, the above equation can be rearranged and we get:

f(m,n) = dp[m][n] = sum[m][n][0] *
C[0] + sum[m][n][1] * C[1] +
… + sum[m][n][D] * C[D]

And sum[m][n][k] can be calculated as:

if k=0, then sum[m][n][0] =
sum[m][n-1][0] + dp[m-1][n]

if k=1,
then sum[m][n][1] = sum[m][n-1][1] +
sum[m][n-1][0]

if k=2, then
sum[m][n][2] = sum[m][n-1][2] +
2*sum[m][n-1][1] + sum[m][n-1][0]

because

sum[m][n][2] - sum[m][n-1][2]

= dp[m-1][0] * (n2 - (n-1)2) + dp[m-1][1] * ((n-1)2 - (n-2)2) +
… + dp[m-1][n-1] * (12 - 02)

= dp[m-1][0] * (2n + 1) + dp[m-1][1] * (2(n-1) + 1) + … + dp[m-1][n-1] * (2*0 + 1)

= 2*sum[m][n-1][1] + sum[m][n-1][0]

And for generalized k (>= 1), we have

sum[m][n][k] = Comb(k,k) *
sum[m][n-1][k] + Comb(k,k-1) *
sum[m][n-1][k-1] + Comb(k,k-2) *
sum[m][n-1][k-2] + … + Comb(k,0) *
sum[m][n-1][0]

where Comb(a,b) = a!/(b! * (a-b)!)

Comb(a,b) can be calculated easily as Comb(a-1,b) + Comb(a-1,b-1) and use the precomputed values without having to compute it repeatedly.

Thus, for every (m,n) pair, we are doing approximately D2 operations(k operations to calculate each sum[m][n][k] and there are D such values of k).

Hence the order of the solution will be O(MND2). But a naive implementation will not pass the time limit. The problem asks you to find the answer modulo 10^9 + 7. The ‘%’ operator is a very costly operator. So we must use it wisely. Too many % operations will give you a TLE. There are several methods to reduce the number of such operations.
A simple if condition can reduce it to a very large extent. For example,

if(ans >= MOD)
	ans%=mod;

This will perform the ‘%’ operation only when required. A better optimization for this problem is as follows:

for(k=0;k<n;k++) 
	sum = (sum + a[k]*b[k])%MOD;

We can use the fact that a[k] and b[k] are already calculated using %MOD i.e. both of them are less than MOD.
So we define LIM as 2^63 - 1 – MOD ^ 2. Thus, LIM + a[k]*b[k] will always fit in long long of C/C++.

Therefore we can replace

for(k=0;k<n;k++) 
	sum = (sum + a[k]*b[k])%MOD;

with

for(k=0;k<n;k++){
	sum += a[k]*b[k];
	if(sum > LIM) 
		sum %= MOD;
}
if(sum >= MOD) sum %= MOD;

This optimized code has at most ceil(n/8) % operations.

TESTER’S SOLUTION:

Can be found here.

APPROACH:

Complexity O(NMD)

Let’s begin exactly like the way we did for the previous solution.

f(m,n) = Σ P(k1x)P(k2x)…P(kmx)
where Σ ki = n

= Σk P(kx) Σ P(k1x)P(k2x)…P(km-1x) for k = n
to 0

= Σk P(kx) Σ f(m-1,n-k)

= Σk P((n-k)x) Σ f(m-1,k)

Now let’s try and calculate P((n-k)x)

From the definition of P(x) , we get:

P((n-k)x) = ?j
Cj(n-k)jxj for j = 0 to D

= ?j Cj ?i Comb(i,j)
n(j-i) (-1)i
ki xj

= ?i ki (-1)i ?j Cj
Comb(i, j) n(j-i)
xj

Let a[n][i] = (-1)i ?j Cj Comb(i, j) n(j-i) xj

Hence, f(m,n) = ?k?i a[n][i] . ki . f(m-1,k)
= ?i a[n][i] ?k ki . f(m-1,k)

Clearly, total number of operations to calculate f(m,n) are N.D.M. Hence the complexity of the solution is O(NMD).
This solution can be optimized in the same way as the above solution by reducing the number of % operations.

ALTERNATE TESTER’S SOLUTION:

Can be found here.

APPROACH:

We saw that

f(m,n) = ? P(k1x)P(k2x)…P(kmx)
where ? ki = n

Let A[j] = P(x*j). Hence the above equation can be rewritten as:

f(m,n) = ? f(m-1, k) * A[n-k] for
0<=k<=n

So, f(m) = f(m-1) * A where A * B is the convolution of sequences A and B:

C = A * B if C[n] = Sum[A[k] * B[n-k],
0<=k<=n]

We need to find f[M][N]. We have

f(M) = f([M-1) * A = (f(F[M-2) * A) * A =
… = (((f[0] * A) * A) …) * A,
where f[0] = {1, 0, …, 0}.

Since convolution has both associative and commutative properties, we can simply write:
f(M) = AN * f(0) where AN = A * A * … * A is the convolution power.

14 Likes

There’s another solution with Complexity O(N^2 * logM)

All of the above solutions calculate f(M,N) = sum of f(1,k)*f(M-1,N-k) and then various methods of calculating convolutions, because that can’t run in time with simple DP.

A much simpler approach that passes comfortably is to use f(M,N) = sum of f(floor(M/2),k)*f(ceil(M/2),N-k). This can be computed directly with memoisation .

9 Likes

Sorry i dont really understand the derivation of this f(M,N) = sum of f(1,k)*f(M-1,N-k). Could someone pls explain to me? Tks. My email is tungnk1993@gmail.com

1 Like

For those that didn’t understand this equation from editorial (like me)

alt text

It simply says, that when we want to generate all possibilities the algorithm is following:

  1. at the beginning we want to get sum n as addition of m numbers
  2. we can choose first number k from interval [0; n]
  3. when we have k, we want to generate sum (n-k) as addition of m-1 numbers

Here is example for m = 3, n = 3 (link to the image)

edit: there was missing Pi (product) in first equation

6 Likes

one thing is given wrong, instead of
sum[m][n][2] = sum[m][n-1][2] + 2sum[m][n-1][1] + sum[m][n-1][0]
it should be
sum[m][n][2] = sum[m][n-1][2] + 2
sum[m][n-1][1] - sum[m][n-1][0]

Can anybody help/explain as to how should one find/generate “k” values using “M” and “N”? Or does that beat the purpose of this question? I’ve done everything except for that… ie. precalculate the coefficients, powers of the numbers etc.

You can find it as ALTERNATE TESTER’S SOLUTION :slight_smile: The attached code contains quite descriptive explanation of this solution in comments.

1 Like

I did exactly the same,(http://www.codechef.com/viewsolution/1081595)
very short code :smiley:

2 Likes

Oh didn’t see that :slight_smile: … but i meant another solution which uses dp[i][j] as the solution if M = 2^i and N = j …

If I am not mistaken, what you meant was a solution using
f(2m, n) = f(m, 0) * f(m, n) + f(m, 1) * f(m, n-1) + … + f(m, n) * f(m, 0).
So, if m is even, do like above, and when m is odd, do like the editorial suggested.

I found that accidentally, but can’t proof it yet.

@tungnk1993: look at my “answer” :wink:

thank you! that clarified things :smiley:

excellent bro :slight_smile: