upobir's blog

Help or insight into CSES String Transform Problem
By upobir, history, 4 years ago, In English

I was happily browsing internet 2 days ago until I saw this problem String Transform. Been stuck at it for two days now, and the best I could come up with is a rough $$$O(n^2)$$$ idea. Would be greatful for some hints.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

It can be solved using suffix array. If you don't know what it is there a course in the edu section.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know suffix array, but the application here isn't obvious to me. I have all rotation's last character, which is a permutation of the original string, so computing this string's suffix arrays shouldn't be useful, right? So what do I build the suffix array of?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can just build the suffix array of the original string. Then replace every character of the original string with the one before (so this is the last character of the string starting at this position), and sort this new string based on the suffix array.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But I do not have the original string? For example in the sample I am given "cb#ab" the final string, I have to restore the original string myself. Or by original string are you referring to the input string?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh sorry I was wrong. I didn't understand the text.

          → Reply