You are not logged in. Please login at www.codechef.com 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 : 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.

asked 10 Jun '16, 22:12

dhavalmehta's gravatar image

3★dhavalmehta
563
accept rate: 30%

edited 15 Jun '16, 19:58

admin's gravatar image

0★admin ♦♦
17.1k347485513


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)

link

answered 10 Jun '16, 23:17

disisbig's gravatar image

3★disisbig
11
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) dhavalmehta3★

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!

link

answered 17 Jan, 02:57

brijs's gravatar image

5★brijs
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×494
×72

question asked: 10 Jun '16, 22:12

question was seen: 1,143 times

last updated: 17 Jan, 02:57