hackercupai/hackercup

1<p>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.</p>2 3<p>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:</p>4 5<pre>function merge_sort(arr):6    n = arr.length()7    if n <= 1:8        return arr9 10    // arr is indexed 0 through n-1, inclusive11    mid = floor(n/2)12    13    first_half = merge_sort(arr[0..mid-1])14    second_half = merge_sort(arr[mid..n-1])15    return merge(first_half, second_half)16 17function merge(arr1, arr2):18    result = []19    while arr1.length() > 0 and arr2.length() > 0:20        if arr1[0] < arr2[0]:21            print '1' // for debugging22            result.append(arr1[0])23            arr1.remove_first()24        else:25            print '2' // for debugging26            result.append(arr2[0])27            arr2.remove_first()28            29    result.append(arr1)30    result.append(arr2)31    return result</pre>32    33<p>A very important permutation of the integers 1 through <strong>N</strong> 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 <strong>N</strong> of the original sequence, and the debug sequence.  Recover the original sequence of integers.</p>34 35<h3>Input</h3>36<p>The first line of the input file contains an integer <strong>T</strong>. This is followed by <strong>T</strong> test cases, each of which has two lines. The first line of each test case contains the length of the original sequence, <strong>N</strong>. 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.</p>37 38<h3>Output</h3>39 40<p>To avoid having to upload the entire original sequence, output an integer checksum of the original sequence, calculated by the following algorithm:</p>41 42<pre>function checksum(arr):43    result = 144    for i=0 to arr.length()-1:45        result = (31 * result + arr[i]) mod 100000346    return result</pre>47 48<h3>Constraints</h3>49<p>505 &le; <strong>T</strong> &le; 20<br/>512 &le; N &le; 10,00052</p>53 54 55<h3>Examples</h3>56 57<p>In the first example, N is 2 and the debug sequence is <tt>1</tt>. 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.</p>58 59<p>In the second example, N is 2 and the debug sequence is <tt>2</tt>. This time the original sequence is 2 1.</p>60 61<p>In the third example, N is 4 and the debug sequence is <tt>12212</tt>. The original sequence is 2 4 3 1.</p>62