Need help in solving this problem : Modified Hamming Distance

Revision en1, by viralm, 2016-06-14 14:53:00

How to solve the following problem ?

For any 3 bit strings (consisting only of 1s and 0s) A, B and C, f(A,B,C) is defined as:

f(A,B,C)=(no. of 1s in ((A XOR B) AND C))/(no. of 1s in C).

We are given N bit strings initially. Then we are given Q queries. Each query contains 2 bit strings B and C. For each query output a single bit string A from the initial set of N bit strings, such that f(A,B,C) is minimum.

It is given that the size of all the bit strings given in the input = 2048 (constant).

Input: First line contains 2 integers N and Q. Then N lines follow, each containing a single bit string of length = 2048. Then Q lines follow, each containing 2 bit strings B and C each of length = 2048. B and C are space separated. Output: For each query output one line containing the string A and f(A,B,C) (space separated). Constraints: 1<=N<=10000 1<=Q<=10000 |A|=|B|=|C|=2048 (fixed for all strings)

Example: Input: 2 1 1001 1011 1 1111 1111 Output: 1011 0.25

Eagerly waiting for your replies. Thanks in advance.

Tags strings, bit manipulation, hashing, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English viralm 2016-06-14 14:56:50 78
en2 English viralm 2016-06-14 14:54:18 10
en1 English viralm 2016-06-14 14:53:00 1177 Initial revision (published)