#2645 Inverse Move-to-Front Transform

1 s   128 MB  

Description

The Move-to-Front (MTF) transform is an encoding scheme which maps the input data into
a sequence of numbers. Entropy encoding schemes often achieve better compression ratio on
the data encoded by the MTF transform. The MTF transform is quite simple. The following
scheme is the MTF transform on string consisting of only characters in lowercase.
1. Maintain a list of characters in lowercase. Initially, the list is sorted in the lexicographic
order. I.e., the list is [abcdefghijklmnopqrstuvwxyz] at the beginning.
2. Read a character ↵ from the string. Output the index of ↵ in the list, then move ↵ to the
front of the list.
3. Repeat the previous step until all characters in the string are read.
For example, the following is how the transform above works on the string hakka.
1. The first character h has index 7 in [abcdefghijklmnopqrstuvwxyz]. Output 7, then
move h to the front of the list.
2. The second character a has index 1 in [habcdefgijklmnopqrstuvwxyz]. Output 1, then
move a to the front of the list.
3. The third character k has index 10 in [ahbcdefgijklmnopqrstuvwxyz]. Output 10, then
move k to the front of the list.
4. The fourth character k has index 0 in [kahbcdefgijlmnopqrstuvwxyz]. Output 0, then
move k to the front of the list.
5. The fourth character a has index 1 in [kahbcdefgijlmnopqrstuvwxyz]. Output 1, then
move a to the front of the list.
The MTF transform maps hakka into the sequence (7, 1, 10, 0, 1). Please write a program
to inverse the MTF transform. In other words, your program reads a sequence of numbers
($a_1$, $\dots$ ,$a_n$), then compute the string s such that the MTF transform maps s into ($a_1$, $\dots$ ,$a_n$),

Input

The first line of the input contains an integer $T$, $T \leq 50$, which indicates the number of
test cases. Each test case consists of two lines. The first one contains a positive integer $n$,
$1 \leq n \leq 100$, which indicates the length of the sequence. The second line contains $n$ integers
$a_1$, $\dots$ ,$a_n$ separated by blanks. The input sequence is ($a_1$, $\dots$ ,$a_n$), and $a_i$  {$0 \leq a_i \leq 25$} for
$i$ ($1 \leq i \leq n$)

Output

For each test case, output the string s such that the MTF transform maps s into ($a_1$, $\dots$ ,$a_n$).

Sample Input

Sample Output

3
5
7 1 10 0 1
6
1 1 13 1 1 1
8
7 1 1 1 20 4 0 1
hakka
banana
hahauccu

Source

2015 ACM-ICPC Taiwan Online Programming Contest