Let S be the set f0; 1; : : : ; n 1g and let 2S denote the set of all subsets of S. Let
• be a function that assigns to every subset A S, an arbitrary integer value f(A). Corresponding to any such function f, we can de ne a function F , where
X
F (A) = f(X)
X A
In the rst part of the problem, given the values of f(A) for every subset A, you have to compute the value of F (A) for every subset A. Every subset A S can be represented uniquely by a number
n(A) = X 2a:
a2A
This is just the number whose binary representation is the n-bit representation of the subset, where the ith bit is 1 i i belongs to the subset.
In the second part of the problem, you are given exactly one of the values f(A) or F (A) for every subset A, and also told whether it is f(A) or F (A). You have to nd for each set the value that is not given, so that f and F satisfy the above relationship.
Input/Output The rst line of input will specify n which will be at most 20. The next line will contain 2n integers, each at most 106, separated by a space. For the rst part of the problem, these will correspond to the values of f, the ith value will be the f value for the set whose corresponding number is i. Thus the values will be f(;); f(f0g); f(f1g); f(f0; 1g); f(f2g); : : : in this order. For the second part of the prob-lem, the same values will be the values given for each set, but the next line will specify whether it an f or F value. The line will contain 2n integers, each being 0 or 1. If the ith integer is 0, it indicates the ith value in the rst line is an f value, otherwise it is an
• value.
For output, in the rst part, print out the F values for each set in the same order as the input on one line separated by a space. Please print out the output for the rst part as soon as you complete it, so that it can be evaluated independent of the other part. For the second part, print out on a new line the value that is not given for each set, in the same order as input. The time limit is less than 5 seconds. Note that computed values may become large so better use long long int.
Sample Input
Output
2
1 3
1 4
1
2 0
1
1 1
-1
2
0
1 1
0
Hint First consider subsets of f0; 1; : : : ; n
2g and solve the problem for them. Then
consider subsets that contain n 1, solve the problem for them and combine appropriately. The recurrence for the time is given by T (n) = 2T (n 1) + 2n 1. The solution for this is O(n2n) which is much better than the obvious O(4n). For the second part, consider what happens if only F values are given and generalize. Submission Submit a single le named RollNo 5.cpp
1
