Please, help with this problem: suppose we are allowed to represent a set of binary strings (that is, consisting only of '0' and '1') with some other set of strings. In the latter set, we can use characters '0', '1' and 'X', where the character 'X' means that both '0' or '1' can occur in that position.
As a matter of example, we can represent the set {001,011,101} with the set {0X1,101}.
Now the problem: given a positive integer N and the set of all the possible binary strings of length N, what is the subset that is most difficult to represent? Here, difficult means that requires the largest amount of strings with the 'X' character allowed.
Thanks for the help.
P.S.: Since I realised that contribution is random and unfair, I don't give a f*** if I'm downvoted. This disclaimer is only for saving the time of downvoters.
Logically adding more strings to a set may make it more difficult but ofcourse will not make it easier to represent so optimal way is to choose all strings and add them to the solution subsetOr maybe I'm misunderstanding the problem so I suggest you to put the constrains of the problem and add a sample input and output to make the problem clearersorry, I misunderstood the problem here's counter test of my idea {00,10,01,11} choosing all string we get {xx} choosing first three {x0,01}. I think this is a nice problem can you give us the constrains
Sorry. I don't have the constraints of the problem since that problem came to my mind when I was trying to solve something else. I could say that for solving the original problem that inspired this one efficiently, N could grow up to the order of 10^6 or so. Nevertheless, it doesn't means that it is possible at all to solve it with such constraints.
Thanks for your reply.
I don't think this kind of psychological trick (I don't care if I'm downvoted) would work, because the mainline downvoters are probably trolls who don't really read the contents. Besides, it seems to be impossible for (mentally healthy) humans :D
To the problem: I suppose you mean the minimum (by number of strings in total) representing set, and are asking for the most difficult minimum representing set of a subset of given strings. To be honest, I don't see a good way of describing the minimum representing set or proving that some rep. set is minimum. You should start from there — show some properties of this set; finding the most difficult one might prove quite easy afterwards.
Yes, I refer to the minimum representing set. Such nomenclature gives a more clear description.
I tried to represent such set with something like regular expressions. In particular, I tried to relate it to the minimum number of states of certain DFA (Deterministic Finite Automaton), but with no success. Perhaps an exponential lower bound of the answer (with respect to N) would make me abandon the problem.
Thanks for your reply.
Well I have an idea (but not quite sure) let's assume we have set of strings with length N {xxx..xx} , removing 1111...111 from the set will make the representation like this:
for example set: {xxxx} removing 1111 from it will make the representation:
that mean set {xxx...xx} with length N after removing 111...111 we will need N strings to represent it so the solution:
find minimum number of strings needed to represent a set of all strings of input then for each string add to solution K , Where K is the number of X's in this string
finding minimum number of strings needed to represent a set of all strings can be done naively in O(M^3*N) worst-case Where M is the number of strings in input and N the length of strings