Binary Sequence Block

Question

More of an informatics question, rather than applied mathematics -

Source - Zonal Informatics Olympiad 2011 Question Paper

Although, I've tried a few brute methods, I haven't really understood the actual logic with which it was meant to be solved.

Answer 1

Seems familiar. Check Burrows–Wheeler transform.

Answer 2

I just found a solution for the (a) sequence :

0 0 1 1 0 1 1 1 (first row)

The complete ordered matrix is as follows :

0 0 1 1 0 1 1 1

0 1 1 0 1 1 1 0

0 1 1 1 0 0 1 1

1 0 0 1 1 0 1 1

1 0 1 1 1 0 0 1

1 1 0 0 1 1 0 1

1 1 0 1 1 1 0 0

1 1 1 0 0 1 1 0

During the solutions development i found some useful theorems that help accomplish the solution.

I'll post this as soon as possible.--> No more necessary, the inversion algorithm provided in the wikipedia page provide the necessary solution.

Cheers,

Yassine