COVERING - Editorial

cook52
divide-and-conq
editorial
inclusn-exclusn
medium-hard
sets

#1

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* += f[ i + len ]; 
		g* += g[ i + len ]; 
		h* += 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


#2

Setter and tester’s solutions link to Access denied XML (seriously, Codechef finds new ways to say “Access denied” every contest, how do they do that? :D).

Question at everyone: do you realize that the SPOJ judge will let only a small subset of optimal solutions pass? Also, is there a sane argument why my O(N*2^N) solution that doesn’t use divide and conquer shouldn’t pass, or is it just “because it doesn’t use the exact same algorithm as the author’s solution”?


#3

Guys!! fix the setter and tester solutions pls. One week, still they error out


#4

Do you have any % operations in your solution? If you use them a lot then it could be the reason why you are getting TLE.


#5

No, I only have exactly 3*(1<<N) of them, which can’t slow down an O(N*2^N) algorithm significantly. I am aware of slow modulos and avoid using them too much.