Competitive Programming: POJ 1147 – Binary Codes

Description

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

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

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.

Sample Input

5
1 0 0 1 0

Sample Output

0 0 0 1 1

Link to problem

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.LinkedList;
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")
    LinkedList<Integer>[] arr = new LinkedList[2];
    for (int j = 0; j < arr.length; j++) {
      arr[j] = new LinkedList<Integer>();
    }

    for (i = 0; i < len; i++) {
      arr[bwtArr[i]].addLast(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)
{
    LinkedList<Integer> head = arr[sortedBwt[index]];
    lShift[index] = head.getFirst();
    head.removeFirst();
}

  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);
  }
}