HAL9000's blog

Help with this problem
By HAL9000, 11 years ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

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 subset

Or 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 clearer

sorry, 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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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:

xxxx...xxxx0
xxxx.....x01
xxxxx...x011
xxx....x0111
.
.
.
.
xx0111111111
x01111111111
011111111111

for example set: {xxxx} removing 1111 from it will make the representation:

xxx0
xx01
x011
0111

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

→ Reply