I have a hard time with this problem. Could you please give me some hints? I feel really bad about it as so many people solved it, even during the contest.
So far I have O(n^3) solution based on "guessing" first few bits and then figuring others out.
Guessing can be done quite fast  it takes O(n^3) in my current implementation, but I believe that the first 1 is on position k iff first k primes generate group Z_p*. I think this can be checked in O(n log n).
I don't know how to speed up the second part.
10866  Magic Bitstrings
Moderator: Board moderators

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
First, it's easy to see that the complement of a magic string is also a magic bitstring.
From this observation, the first bit of the lexicographicaly smallest bitstring must be 0.
Now, consider a particular case n=7. I'll use letters a, b, c... to denote the bits. The matrix looks like:
Observe that, since the leftmost column of the matrix is a copy of the bitstring, and since a=0, the ith row of the matrix is a complement of the bitstring if and only if the ith bit is 1.
This fact gives the following formula for the matrix:
It immediately implies A_{i,i} = s_i XOR s_i = 0.
The remaining bits of the bitstring (i.e. those which are not on the main diagonal) seems to be always 1's, but I don't know how to prove this analytically. I checked by brute force.
From this observation, the first bit of the lexicographicaly smallest bitstring must be 0.
Now, consider a particular case n=7. I'll use letters a, b, c... to denote the bits. The matrix looks like:
Code: Select all
1 2 3 4 5 6
1 a b c d e f
2 b d f a c e
3 c f b e a d
4 d a e b f c
5 e c a f d b
6 f e d c b a
This fact gives the following formula for the matrix:
Code: Select all
A_{i,j} = s_i XOR s_j
(where A_{i,j} is the element at ith row, jth column of the matrix; s_i is the ith bit; XOR stands for `exclusive or'.)
The remaining bits of the bitstring (i.e. those which are not on the main diagonal) seems to be always 1's, but I don't know how to prove this analytically. I checked by brute force.

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
This is quite easy. The diagonal consists of the elements that are quadric residues modulo n. There are (n1)/2 such distinct elements. When we mark them as 0, there are (n1)/2 elements left. But a magic bitstring has equal number of 0's and 1's, so the remaining elements are 1.The remaining bits of the bitstring (i.e. those which are not on the main diagonal) seems to be always 1's, but I don't know how to prove this analytically. I checked by brute force.