3
$\begingroup$

More of an informatics question, rather than applied mathematics -

Problem Statement Problem Statement

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.

2 Answers 2

3

Seems familiar. Check Burrows–Wheeler transform.

  • 0
    That's it! Thanks a lot mate... – 2012-10-31
1

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