BOJ 2340

I spent some time carefully thinking through and solving a problem for the first time in a while.

I usually spend a couple of hours thinking before looking at the solution, but this time there was no editorial available.

Problem

BOJ 2340 이진 수열 회전
Rotate a binary sequence of length $N$ to create a total of $N$ sequences. Sort them lexicographically and obtain a new sequence from the last digits. The problem is to find the original sequence.
The transformation that creates a string by appending the last character of rotated strings is called BWT (Burrows–Wheeler transform), and the problem is to compute the inverse transformation in better than $O(N^2)$ time.

Solution

Let’s denote the input sequence as $S$ and the answer as $A$. Both sequences have length $N$.
The first thing to consider is how to verify whether a candidate sequence $A$ is valid. By concatenating $A$ twice and constructing a suffix array from the resulting sequence of length $2N$, we can sort all rotations starting from $A_0, …, A_{N - 1}$ and compute the BWT in $O(N\log N)$ time (see [wikipedia] for suffix array details). We can then construct a candidate $A$, compute its BWT, and output it if it matches $S$, or output $-1$ otherwise.

The next observation we can make is that $S_0 = A_{N - 1}$. Since $A$ is the lexicographically smallest string among the rotated sequences, the last character of $A$ becomes the first character of $S$. Now the sequence becomes $A = A_0\, A_1\, …\, A_{N - 2}\, S_0$.

Most importantly, let’s find $A_{N - 2}$. When obtaining $S$, the sequence $A’ = S_0\, A_0\, … \, A_{N - 2}$, which is $A$ rotated once to the right, is also included. As mentioned earlier, since $A$ is the lexicographically smallest string among the rotated sequences, $A’$ is lexicographically first among sequences starting with $S_0$. Depending on the value of $S_0$, we can know at which position $A’$ is located lexicographically, and the value of $S$ at that position becomes $A_{N - 2}$. Expressed as a formula, it’s as follows. Here, $zcnt$ is the number of $0$s in $S$.

\[A'_{N-1} = A_{N - 2} = \begin{cases} S_0 & \text{$S_0 = 0$} \\ S_{zcnt} & \text{$S_0 = 1$} \\ \end{cases}\]

If $S_0 = 0$, $A’$ is the first among all rotated sequences. If $S_0 = 1$, it’s the first excluding sequences starting with $0$, so it’s at the $zcnt$-th position (zero-based).

Based on this observation, if we know the lexicographic position of a sequence $T$, we can determine the position of $T’$ (which is $T$ rotated right by one). Lexicographically, if $T_{N-1}=0$, then $T’$ is positioned immediately after all sequences ending with $0$. Similarly, if $T_{N-1}=1$, it’s positioned immediately after all sequences ending with $1$. The first sequence ending with $0$ is at position $0$, and the first sequence ending with $1$ is at position $zcnt$. In the implementation, array $t$ is filled based on this logic at the beginning of the solve function.

We construct $A$ in reverse order and check if the BWT matches $S$. I recently reorganized my templates and re-implemented the suffix array as well. The implementation can be found here.

#include <bits/stdc++.h>
using namespace std;

int N;
string S;
int t[50000];

void solve() {
	cin >> N >> S;
	int zcnt = 0;
	for (int i = 0; i < N; ++i) if (S[i] == '0') ++zcnt;
	int zcur = 0, ocur = zcnt;
	for (int i = 0; i < N; ++i) {
		if (S[i] == '0') t[i] = zcur++;
		else t[i] = ocur++;
	}
	int cur = 0;
	string ans;
	for (int i = 0; i < N; ++i) {
		ans += S[cur];
		cur = t[cur];
	}
	reverse(ans.begin(), ans.end());
	string tans = ans; tans += ans;
	auto sfx = getSuffixArray(tans);
	string tmp;
	for (auto i: sfx) if (i < N) tmp += tans[i + N - 1];
	if (tmp != S) cout << -1;
	else cout << ans;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

Problems always seem difficult while solving them, but straightforward in retrospect.