PROBLEM LINK:
[Practice][111]
[Contest][222]
Author: Pavel Sheftelevich
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
DIFFICULTY:
HARD
PREREQUISITES:
Maths related to functions, Backtracking, Bitmasks
PROBLEM:
You are given M sets with N variables(N <= 5) where each variable can be either true or false and you want to find some key subsets with minimal total length that cover all given sets and exactly them (no extra sets). All the given sets contain all the variables.
EXPLANATION:
Let’s define some terms first:
Argument:
An argument is a set of boolean inputs to a function.
Example: If there is a function with 3 variables namely (X, Y, Z) then (X = 1, Y = 0, Z = 1), (X = 0, Y = 1, Z = 1) are two examples of arguments.
Conjunction:
A conjunction is LOGICAL AND of several variables Xi or not Xi.
Example: If there is a function with 3 variables namely (X, Y, Z) then (X AND Y AND Z), (X AND Y), (X AND (not Y) AND (not Z)) are three examples of conjunctions.
Function:
A Function is a mapping from a set of inputs to a set of outputs. In another way it can be stated as a LOGICAL OR of a set of conjunctions. The set of outputs is {0, 1} and set of inputs contains the N people in our problem.
Example: ((X AND Y) OR (Y AND Z)), this function takes value 1 for the following arguments
- (X = 1, Y = 1, Z = 0)
- (X = 1, Y = 1, Z = 1)
- (X = 0, Y = 1, Z = 1)
Now lets reformulate our problem in another words: You have a boolean function F on N variables and you are given M arguments where function takes the value 1 and on all other arguments it takes 0. We can see that each set(or key set) is some conjunction on N variables.
Let’s denote Xi with upper case letter and not Xi with lower case letter (like in the problem statement). You are to find a function equivalent to initial function, which is OR of several conjunctions with minimal total number of variables contained.
The most straightforward approach:
Generate all possible conjunctions. Each conjunction covers some arguments of the initial function. So the problem boil downs to minimal set cover problem with weighted covering subsets. The number of conjunctions on N variables is 3^N. So for N = 5, there are 243 conjunctions, and we have to check all 2^243 possible sets of conjunctions, which is impossible to pass in acceptable time even with best optimizations.
Here one of the key observations goes: many conjunctions are redundant - they are included in others, can be obtained as combination of some other conjunctions and some even doesn’t fit our function(they take the value 1 for arguments which F doesn’t have).
An elementary conjunction is called an implicant if F takes the value 1 on all the arguments which the conjunction takes the value 1.
So we want find group of implicants of more acceptable size than 243 and work only with them.
Let’s find them using the following algorithm:
Put all sets(arguments) where F takes 1 and while possible do the following
- If there are implicants A, B and if the set of arguments covered by A is subset of set of arguments covered B then get rid of A.
- If there are implicants A, B with form: A = xC and B = XC then A, B can be replaced by one implicant C.
After some iterations we will get group of implicants(prime implicants). The universal upper-bound of the number of prime implicants is 3^N/N. For N = 5 upper bound of prime implicants is 3^N/N = 48 - much better, but it turns out that maximal number of prime implicants for boolean function on 5 variables is 32(author checked all possible functions on 5 variables: 2^32).
So now we have cover set problem with 32 available sets. It’s well-known NP problem, but in our case we can make one more observation: the covering sets we have are a bit specific, more precisely, if we have many prime implicants then most of them will cover few arguments and reversely, if each implicant covers many arguments then there are few implicants.
That gives us an idea that recursive brute-force solution(with O(2^N)) can perform well if we use some optimizations.
Let us say that we have K prime implicants finally. Now lets have 3 arrays cost[1…K], covers[1…K], or_to_end[1…K].
cost[i] stores the length of i’th implicant, covers[i] is a bit mask which stores the set of arguments which evaluate i’th implicant to 1, or_to_end[i] stores bitwise OR of all covers[j] such that i <= j <= K.
Now take a look at the following recursive code for further implementations:
void backtrack (int pos, long long current_mask, int current_cost) {
if (current_cost >= ans) // there is no meaning in going further because we already crossed our current answer
return;
if (current_mask | or_to_end[pos]) != required) // As we cannot cover all the arguments even if we take all the implicants from this position
return;
if (current_mask == required) {
ret = current_cost; // We found a better solution
return ;
}
if ((current_mask | covers[pos]) != current_mask) // if current implicant covers atleast one argument which was already not covered
backtrack(pos + 1, current_mask | covers[pos], current_cost + cost[pos]); // then take this implicant and go to next one
backtrack(pos + 1, current_mask, current_cost); // Go to next implicant without considering the current one
}
In the above psuedo code there are 3 key optimizations, all of them are simple if-break clause. With them recursive solution works very fast(several millions recursive calls in the worst case instead of 2**32) and without any of them solution becomes slower 3-20 times slower. Important moment of the solution is effective implementation, solution should use bit-masks(two ints for false variables and true variables in the authors’s solution) and optimizations in recursion. Without them it’s unlikely to pass.
One more major optimization we can do is to sort all the K prime implicants in the increasing order of their costs before calling the backtrack function, then we converge on the answer a lot faster in most of the cases. This is because of a small heuristic, that the smaller prime implicants cover more arguments, and also have less cost.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution
[111]: http://www.codechef.com/problems/LPARTY
[222]: http://www.codechef.com/APRIL15/problems/LPARTY
