Problem Link: contest, practice
Difficulty: Medium-Hard
Pre-requisites: Set Theory, Divide-and-Conquer, Inclusion-Exclusion Principle
Problem:
Given a set S of N different elements numbered from 0 to N - 1. A triple (A, B, C) of subsets of S covers a subset D of S, if D is a subset of the union of subsets A, B and C. In other words, every element of D is an element of at least one of A, B, or C.
Given three functions F, G and H, each takes a subset of S as the only parameter and returns a non-negative integer. You are given the values of F(i), G(i), and H(i) for each 0 ≤ i < 2**N**.
The value of a function R of a subset X of S is equal to the sum of F(A) × G(B) × H© for all triples (A, B, C) of subsets of S that cover X.
Your task is to calculate R(0) + R(1) + … + R(2N - 1).
Explanation:
This problem is the hardest one, it was supposed to be solved by a very few number of contestants.
First of all, I want you to get familiar with this problem and its editorial. It would be rather helpful for you to understand my editorial. The “solution fount by contestants” of this problem may also help you to understand one of the keypoints of the following solution.
It seems like some of the contestants came up with quite easier solutions, I will be grateful if you, guys, share your approaches in the comments.
Let’s consider a function P(A, B, C) that is equal to F(A) × G(B) × H© × 2the number of elements in the union of A, B and C.
The first observation: R(0) + R(1) + … + R(2N - 1) equals to P(0, 0, 0) + P(0, 0, 1) + … + P(2N - 1, 2N - 1, 2N - 1), i.e. the answer equals to the sum of all possible P’s. So, from now we are interested only in calculating the second sum.
The second observation is based on De Morgan’s laws: if D is a subset of the union of subsets A, B and C, then the intersection of ~A, ~B and ~C is a subset of ~D, where ~X is equal to S \ X. So, after that observation we can say that the function P(A, B, C) equal to F(A) × G(B) × H© × 2N - (the number of elements in the intersection of ~A, ~B and ~C).
Let’s reverse the arrays of the functions F, G and H, i.e. assign the following:
- F(i) := F(2N - 1 - i);
- G(i) := G(2N - 1 - i);
- H(i) := H(2N - 1 - i).
This can be done in O(N) time by simply reversing each of the arrays.
After doing that we can consider another function Q(A, B, C) that is equal to F(A) × G(B) × H© × 2N - (the number of elements in the intersection of A, B and C).
The third observation: P(0, 0, 0) + P(0, 0, 1) + … + P(2N - 1, 2N - 1, 2N - 1) before reversing equals to Q(0, 0, 0) + Q(0, 0, 1) + … + Q(2N - 1, 2N - 1, 2N - 1) after reversing.
Now, let’s make another transformation of the arrays of the functions F, G and H:
- F(i) := F(s1) + F(s2) + … + F(sK), where each sj is a superset of i;
- G(i) := G(s1) + G(s2) + … + G(sK), where each sj is a superset of i;
- H(i) := H(s1) + H(s2) + … + H(sK), where each sj is a superset of i.
This part can be done in O(N Ă— 2N) time by a divide-and-conquer approach on each of the arrays. The approach is described here(problem 449D - Jzzhu and Numbers).
Here’s a part of Setter’s solution that does this transformations:
void rec( int l, int r )
{
if ( l == r ) return;
int x = ( l + r ) / 2, len = ( r - l + 1 ) / 2;
rec( l, x );
rec( x + 1, r );
for ( int i = l; i <= x; i++ )
{
f[i] += f[ i + len ];
g[i] += g[ i + len ];
h[i] += h[ i + len ];
}
}
Let’s consider another function T(X) that is equal to the F(X) × G(X) × H(X). In other words, it’s the sum of F(A) × G(B) × H© for all triples(A, B, C) such that X is a subset of the intersection of A, B and C.
At the same time, we can say, that the sum of F(A) × G(B) × H© for all triples(A, B, C) such that X is equal to the intersection of A, B and C can be simply calculated with a help of the inclusion-exclusion principle. For example, if X = 0 then it’s equal to T(0) - T(1) - T(2) + T(3) - T(4) + T(5) + … + (-1)the number of elements in X × T(X). For arbitrary set X the sum equals to the similar linear combination of supersets of X.
The answer is equal to the sum of the following values: 2N - (the number of elements in X)
× (the sum of F(A) × G(B) × H© for all triples(A, B, C) such that X is equal to the intersection of A, B and C) for all X from 0 to 2N - 1. As we have just discussed, the second multiplier is a linear combination of T’s, so the answer is also a linear combination of T’s. The question is how to find the coefficients of that linear combination.
Let’s first assign coefficientX := 2N - (the number of elements in X). Then, we can do a similar divide-and-conquer approach as we did while transforming the arrays of the functions of F, G and H:
void rec( int l, int r )
{
if ( l == r ) return;
int x = ( l + r ) / 2, len = ( r - l + 1 ) / 2;
rec( l, x );
rec( x + 1, r );
for ( int i = l; i <= x; i++ )
{
coefficient[ i + len ] -= coefficient[ i ];
}
}
We are doing exactly what the inclusion-exclusion principle tells us: since the sets X and X + {a} differ in exactly one element, then we should increase coefficientX + {a} by (-1) Ă— coefficientX, because if two sets differ in the odd number of elements, then the coeffient is -1.
The only thing that is left to do is to calculate the answer:
for ( int x = 0; x < 2N; x++ ) answer += coefficient[x] Ă— t[x];
The total complexity of the solution is O(N Ă— 2N).
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link