Minimal String Xoration

3000ms

524288K

Description:

You are given an integer $$$n$$$ and a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet. The characters of the string $$$s$$$ are $$$s_0s_1s_2\cdots s_{2^n-1}$$$.

A string $$$t$$$ of length $$$2^n$$$ (whose characters are denoted by $$$t_0t_1t_2\cdots t_{2^n-1}$$$) is a xoration of $$$s$$$ if there exists an integer $$$j$$$ ($$$0\le j \leq 2^n-1$$$) such that, for each $$$0 \leq i \leq 2^n-1$$$, $$$t_i = s_{i \oplus j}$$$ (where $$$\oplus$$$ denotes the operation bitwise XOR).

Find the lexicographically minimal xoration of $$$s$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

$$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 18$$$).

The second line contains a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet.

Output:

Print a single line containing the lexicographically minimal xoration of $$$s$$$.

Sample Input:

2
acba

Sample Output:

abca

Sample Input:

3
bcbaaabb

Sample Output:

aabbbcba

Sample Input:

4
bdbcbccdbdbaaccd

Sample Output:

abdbdccacbdbdccb

Sample Input:

5
ccfcffccccccffcfcfccfffffcccccff

Sample Output:

cccccffffcccccffccfcffcccccfffff

Sample Input:

1
zz

Sample Output:

zz

Note:

In the first test, the lexicographically minimal xoration $$$t$$$ of $$$s =$$$"acba" is "abca". It's a xoration because, for $$$j = 3$$$,

$$$t_0 = s_{0 \oplus j} = s_3 =$$$ "a";
$$$t_1 = s_{1 \oplus j} = s_2 =$$$ "b";
$$$t_2 = s_{2 \oplus j} = s_1 =$$$ "c";
$$$t_3 = s_{3 \oplus j} = s_0 =$$$ "a".

There isn't any xoration of $$$s$$$ lexicographically smaller than "abca".

In the second test, the minimal string xoration corresponds to choosing $$$j = 4$$$ in the definition of xoration.

In the third test, the minimal string xoration corresponds to choosing $$$j = 11$$$ in the definition of xoration.

In the fourth test, the minimal string xoration corresponds to choosing $$$j = 10$$$ in the definition of xoration.

In the fifth test, the minimal string xoration corresponds to choosing either $$$j = 0$$$ or $$$j = 1$$$ in the definition of xoration.

Informação

Provedor Codeforces

Código CF1654F