## 10866 - Magic Bitstrings

Moderator: Board moderators

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

### 10866 - Magic Bitstrings

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Start by proving that in the square matrix (like the one, shown in the table in the problem statement),
the diagonal elements are always 0's if the first bit of the bitstring is 0.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Thanks for help. This observation seems to be the key. How did you spot it?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
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:

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``````
Observe that, since the leftmost column of the matrix is a copy of the bitstring, and since a=0, the i-th row of the matrix is a complement of the bitstring if and only if the i-th bit is 1.

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 i-th row, j-th column of the matrix; s_i is the i-th bit; XOR stands for `exclusive or'.)``````
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.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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.
This is quite easy. The diagonal consists of the elements that are quadric residues modulo n. There are (n-1)/2 such distinct elements. When we mark them as 0, there are (n-1)/2 elements left. But a magic bitstring has equal number of 0's and 1's, so the remaining elements are 1.