WA#4 - I know the test which fails my program, and after I correct it, it's accepted. But please, cen somebody explain me why it works?))
Neumann (
http://acm.timus.ru/forum/thread.aspx?id=10813&upd=632432089473593750) wrote a beautiful test:
input:
2
bbaa
output:
abab
If you 're using fast-BWT transform, you know that input with position indexes looks like this (I'll call this arrays "lastIndex" and "lastLetter", all arrays are numbered from zero):
b 0
b 1
a 2
a 3
And after you sort this pairs of data in problem's lexicographic order (I'll call this arrays "firstIndex" and "FirstLetter", all arrays are numbered from zero):
2 a
3 a
0 b
1 b
I'd mention that I use basket sort (it's stable, and I do not use indexes while comparing, only char codes).
Then we are ready to decode our message with initial value = 2-1 = 1 (we subtract one because we're numbering our arrays from zero)
But when you tries to decode using that indices you can notice that:
FirstIndex[1] = 3
FirstIndex[3] = 1
It's a loop with length less than the length of initial string!!
But if you unroll this loop several times (until total number of [] operations will match the number of symbols in lastLetter array) you'll get the right answer.
Can somebody explain why unrolling this loop several times produces the right answer???