Let S be the set {0,1,...,n − 1} and let 2S denote the set of all subsets of S. Let f be a function that assigns to every subset A ⊆ S, an arbitrary integer value f(A).
Corresponding to any such function f, we can define a function F, where
F(A) = X f(X)
X⊆A
In the first 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.
a∈A
This is just the number whose binary representation is the n-bit representation of the subset, where the ith bit is 1 iff 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 find for each set the value that is not given, so that f and F satisfy the above relationship. Input/Output The first 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 first 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({0}),f({1}),f({0,1}),f({2}),... in this order. For the second part of the problem, 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 first line is an f value, otherwise it is an F value.
Sample Input Output
2 1 3 1 4
1 2 0 1
0 1 1 0 1 1 -1 2
Hint First consider subsets of {0,1,...,n − 2} 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 file named RollNo 5.cpp
1
