PROBLEM LINK:Author: Pavel Sheftelevich 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 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
After some iterations we will get group of implicants(prime implicants). The universal upperbound 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 wellknown 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 bruteforce 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:
In the above psuedo code there are 3 key optimizations, all of them are simple ifbreak 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 320 times slower. Important moment of the solution is effective implementation, solution should use bitmasks(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:
This question is marked "community wiki".
asked 13 Apr '15, 16:06

I just random 1024 times and choose subsets which can cover the most parties first. answered 15 Apr '15, 05:15

Is this problem an application of Quine Mcluskey algorithm ? answered 14 Apr '15, 20:51

And a bit different approach :) Dynamic programming [3^n][2^(2^n)] is obvious  minimum cost to cover given mask of possible strings by using only first X possible sets. This solution is already good enough to solve first subtask. How to handle second one? We have 3^5*2^32. A bit too much :) First let's make 2^16 out of 2^32. Divide all possible sets in two groups  those which don't have letter A/a and those which have. We have to cover all possible suffixes (without letter A/a), and for every suffix we have 2 possibilities  either it is covered by set without letter A/a, or it have to be covered in other way (then there should be two used sets for it  one with A and one with a). Now we can solve 3 similar tasks  do a 3^4*2^16 dp for covering suffixes with sets containing A, with sets containing a, and with sets without A/a. Then try all possible variants of splitting strings between (A/a+) and (A/a) groups and pick best one. This solution should already be good enough to pass a single testcase within 1.2 seconds, but for 120 tests you have to optimize it a lot :) Throw away dominated sets  there are no reason to take Ab or AB when you can take A. Throw away sets of size N  you can always take them in greedy way later, there is no need to put them in DP. Check only reached states of DP, there is no need to run a cycle over all 2^16 states every time. Sort sets by size and update DP with short sets first to postpone growing of set of reachable states. With those optimizations my solution runs precisely 1.20 seconds on one of tests in subtask 2 :) But I guess it can be further optimized. answered 14 Apr '15, 17:19

"During all these parties something had gone wrong. We can notice that when there is subset Ab(A was in good mood, but B was in bad mood) party is spoiled and the mood of friend C doesn't matter" What this lines means How it is violating any condition? answered 14 Apr '15, 18:24

please give me some test cases where my solution give wrong answer.... it should it be easy to find because I got AC only in 1 test case and I can't find out where my solution give wrong answer Admin please http://www.codechef.com/viewsolution/6777820 answered 15 Apr '15, 03:44
I have the same situation that i get wa on all test cases for N > 3 whereas i can`t find a single testcase where i got wrong : :) I think we all(those who solved using Quine Mcluskey or k maps ) have some common mistake. My doubt is that "THe minimum total size" and "Minimum number of total terms " .Is there any situation when both cases get different results ? bcz what we did was minimum terms and then count the terms.., Here is the link to my solution http://www.codechef.com/viewsolution/6777036
(15 Apr '15, 16:46)
for n=3, there are not much possibilities, and hence much less room for error, but for n=4,5, kmaps are much more complicated and most solutions crumbled in larger cases...
(16 Apr '15, 05:16)

Answer is hidden as author is suspended. Click here to view.
answered 02 May '15, 12:07
