ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1322. Spy

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?))
Posted by Leonid (SLenik) Andrievskiy 17 Jul 2011 16:44
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???