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

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

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

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 i-th row, j-th column of the matrix; s_i is the i-th 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.

- Krzysztof Duleba
- 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 (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.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.