Can anyone help me to solve hidden password (ACM 2003, abridged) problem ?
link : https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=756
spoj link : http://www.spoj.com/problems/MINMOVE/
I found many solutions which use suffix array but I didn’t get anyone of them. I know what is suffix array but don’t know how to apply it here. I just want method to solve this problem.
Suffix array is just all the suffixes of the string in sorted order,
and the answer to the question would be “suffixarray[0]”+“rest of the string”, because that would be the lexicographically smallest string possible!
Eg:
string = cba;
suffixarray = {a,ba,cba}
answer to question = “a”+“cb” = acb
Complexity: O(nlogn) (for building suffix array) + O(n) (for traversing the string for building answer)
= O(nlogn)
In question, minimum rotations are asked.
let string = “aaa”. then suffix array will be { a, aa, aaa }.
according to your solution I use suffix “a” to obtain answer. To achieve required suffix, I must rotate string 2 times, so answer of question will be 2 rotations.
but “aaa” is already lexicographical minimal string so answer is 0 rotations.
I couldn’t solve “Hidden Password” nor “MINMOVE” but “BEADS” on SPOJ is also similar and I solved it using suffix arrays.
I don’t know what’s the problem with the Live Archive because no matter what I get RE.
With MINMOVE I get TLE, and that may be because it requires some more optimization on suffix arrays. (It’s also said to have a O(n) solution in the comments below the problem statement,maybe that’s the answer to it.)
If you already know how to create a classic suffix array, what I did in BEADS (and which most probably also applies to MINMOVE and Hidden Password) is that instead of initializing the second value in the tuple to be -1 when the second index(which is at 2^k distance from first index for step k) exceeds the length of string, I actually initialized it with the value at index (first_index+(2^k))%N.
Hope this helps!