10866 - Magic Bitstrings

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10866 - Magic Bitstrings

Post by Krzysztof Duleba » Sat Jul 16, 2005 5:06 pm

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:

Post by mf » Sat Jul 16, 2005 5:27 pm

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.

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

Post by Krzysztof Duleba » Sat Jul 16, 2005 5:43 pm

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:

Post by mf » Sat Jul 16, 2005 7:02 pm

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.

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

Post by Krzysztof Duleba » Sat Jul 16, 2005 7:15 pm

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.

Post Reply

Return to “Volume 108 (10800-10899)”