×

# need help to solve - hidden password (ACM 2003, abridged)

 0 Can anyone help me to solve hidden password (ACM 2003, abridged) problem ? 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. asked 10 Jun '16, 22:12 56●3 accept rate: 30% 0★admin ♦♦ 18.5k●348●495●529

 0 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) answered 10 Jun '16, 23:17 3★disisbig 1●1 accept rate: 0% 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. (10 Jun '16, 23:36)
 0 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! answered 17 Jan '17, 02:57 5★brijs 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×619
×75

question asked: 10 Jun '16, 22:12

question was seen: 1,331 times

last updated: 17 Jan '17, 02:57