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.

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

Leave a Reply

Your email address will not be published. Required fields are marked *