Recover the Sequence

Merge sort is one of the classic sorting algorithms. It divides the input array into two halves, recursively sorts each half, then merges the two sorted halves.

In this problem merge sort is used to sort an array of integers in ascending order. The exact behavior is given by the following pseudo-code:

function merge_sort(arr):
    n = arr.length()
    if n <= 1:
        return arr

    // arr is indexed 0 through n-1, inclusive
    mid = floor(n/2)
    
    first_half = merge_sort(arr[0..mid-1])
    second_half = merge_sort(arr[mid..n-1])
    return merge(first_half, second_half)

function merge(arr1, arr2):
    result = []
    while arr1.length() > 0 and arr2.length() > 0:
        if arr1[0] < arr2[0]:
            print '1' // for debugging
            result.append(arr1[0])
            arr1.remove_first()
        else:
            print '2' // for debugging
            result.append(arr2[0])
            arr2.remove_first()
            
    result.append(arr1)
    result.append(arr2)
    return result

A very important permutation of the integers 1 through N was lost to a hard drive failure. Luckily, that sequence had been sorted by the above algorithm and the debug sequence of 1s and 2s was recorded on a different disk. You will be given the length N of the original sequence, and the debug sequence. Recover the original sequence of integers.

Input

The first line of the input file contains an integer T. This is followed by T test cases, each of which has two lines. The first line of each test case contains the length of the original sequence, N. The second line contains a string of 1s and 2s, the debug sequence produced by merge sort while sorting the original sequence. Lines are separated using Unix-style ("\n") line endings.

Output

To avoid having to upload the entire original sequence, output an integer checksum of the original sequence, calculated by the following algorithm:

function checksum(arr):
    result = 1
    for i=0 to arr.length()-1:
        result = (31 * result + arr[i]) mod 1000003
    return result

Constraints

5 ≤ T ≤ 20
2 ≤ N ≤ 10000

Examples

In the first example, N is 2 and the debug sequence is 1. The original sequence was 1 2 or 2 1. The debug sequence tells us that the first number was smaller than the second so we know the sequence was 1 2. The checksum is 994.

In the second example, N is 2 and the debug sequence is 2. This time the original sequence is 2 1.

In the third example, N is 4 and the debug sequence is 12212. The original sequence is 2 4 3 1.

Example input

5
2
1
2
2
4
12212
5
1122211
10
121221212111122121212

Example output

Case #1: 994
Case #2: 1024
Case #3: 987041
Case #4: 570316
Case #5: 940812

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;

public class Checkpoint {
public static void main(String[] args) throws IOException {
BufferedReader leer= new BufferedReader(new InputStreamReader(System.in));
int T= Integer.parseInt(leer.readLine());
int r[]=coefBin(4500);
for (int i = 1; i <= T; i++) {
int n= Integer.parseInt(leer.readLine());
int t=Integer.MAX_VALUE;
for (int j = 1; j*j <= n; j++) {
if(n%j==0){
int a=r[j]==Integer.MAX_VALUE/3?j:r[j];
int b=r[n/j]==Integer.MAX_VALUE/3?n/j:r[n/j];

t=Math.min(a+b,t);
}
}
System.out.println("Case #"+i+": "+t);
}
}
public static int[] coefBin(int N){
int c[][]= new int[N][N];
int r[]= new int[10000001];
Arrays.fill(r, Integer.MAX_VALUE/3);
r[0]=0;
r[1]=1;
for (int i = 0; i < N; i++)
c[i][0] = c[i][i]=1;
for (int i = 1; i < N; i++){
if(c[i-1][1]==0 && i>1)
break;
for (int j = 1; j < i; j++){
if(c[i-1][j-1]+c[i-1][j]<=10000000){
c[i][j]=c[i-1][j-1]+c[i-1][j];
r[c[i][j]]=Math.min(r[c[i][j]], i);
}
else{
c[i][j]=Integer.MAX_VALUE/3;
}
}
}

return r;

}
}

sophiebits/gist:1696739