# Competitive Programming: POJ 1147 – Binary Codes

### Description

Consider a binary string (b1…bN) with N binary digits. Given such a string, the matrix of Figure 1 is formed from the rotated versions of the string.

 b1 b2 … bN-1 bN b2 b3 … bN b1 … bN-1 bN … bN-3 bN-2 bN b1 … bN-2 bN-1

Figure 1. The rotated matrix

Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’. You are to write a program which, given the last column of the sorted matrix, finds the first row of the sorted matrix.

As an example, consider the string (00110). The sorted matrix is

 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0

and the corresponding last column is (1 0 0 1 0). Given this last column your program should determine the first row, which is (0 0 0 1 1).

### Input

The first line contains one integer N <= 3000, the number of binary digits in the binary string. The second line contains N integers, the binary digits in the last column from top to bottom.

### Output

The first line contains N integers: the binary digits in the first row from left to right.

```5
1 0 0 1 0
```

### Sample Output

```0 0 0 1 1
```

Solution below . . .

### Solution

```/*
* The process of forming a matrix from rotated versions of a string,
* sorting the rows, and taking the value from the right-hand column
* is called a Burrows-Wheeler Transform, and is part of the
* Burrows-Wheeler Data Compression Algorithm.
*
* This link has a discussion of the algorithm, as well as how to
* invert the transform back to the sorted matrix:
*
* http://www.cs.princeton.edu/courses/archive/fall07/cos226/assignments/burrows.html
*/
import java.util.Arrays;
import java.util.Scanner;

public class Main {

static void invert(int bwtArr[]) {
int i;
int len = bwtArr.length;
int[] lShift = new int[len];

int[] sortedBwt = bwtArr.clone();

// Index at which original string appears
// in the sorted rotations list
int x = 0;

Arrays.sort(sortedBwt);

@SuppressWarnings("unchecked")
for (int j = 0; j < arr.length; j++) {
arr[j] = new LinkedList<Integer>();
}

for (i = 0; i < len; i++) {
}

for (i = 0; i < len; i++) {
computeLShift(arr, sortedBwt, i, lShift);
}

// Decodes the BWT
for (i = 0; i < len; i++) {
x = lShift[x];
System.out.print(bwtArr[x] + " ");
}
}

static void computeLShift(LinkedList<Integer>[] arr, int[] sortedBwt, int index,
int[] lShift)
{
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();

int[] bwtArr = new int[N];

for (int i = 0; i < N; i++) {
bwtArr[i] = sc.nextInt();
}

sc.close();

invert(bwtArr);
}
}
```