You are not logged in. Please login at to post your questions!


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

Can anyone help me to solve hidden password (ACM 2003, abridged) problem ?

link :

spoj link :

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

dhavalmehta's gravatar image

accept rate: 30%

edited 15 Jun '16, 19:58

admin's gravatar image

0★admin ♦♦

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

disisbig's gravatar image

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) dhavalmehta2★

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

brijs's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 10 Jun '16, 22:12

question was seen: 1,331 times

last updated: 17 Jan '17, 02:57