The problem is as follows:

Given $k$ strings of size $n$, propose a data structure to support the following operations:

  1. Return the maximum of a string.
  2. Given an index $i$, and $2$ strings $a$ and $b$, create 2 strings to replace them: One of them is compised of the $i$ first elements of $a$ and $n-i$ of the last elements of $b$, and the other string is the $i$ first elements of $b$ followed by the $n-i$ last elements of $a$.

I suppose we need to do a preperation for the structure, and answer the queries as fast as possible.

One solution I thought of is as follows:

For each string, memoize the maximum in all prefixes and suffixes.

  1. Returning the maximum is trivial.
  2. Given the index $i$, the prefixes of the first half are still correct, and only the prefixes of the second half need to be recomputed, and only the first half's suffixes need to be recomputed.

But this results in $O(kn)$ preperation, $O(1)$ maximum, and $O(n)$ splits.

I also thought of using some sort of a Cartesian Tree or RMQ for this.

How can this be done more efficiently, possibly $O(1)$ in both queries?

  • 2
    $\begingroup$ What do you mean by 'maximum of a string' ? $\endgroup$ – preetsaimutneja May 17 '14 at 12:37
  • $\begingroup$ I myself struggled to understand what it says. I assume that by string it means a sequence of something comperable, for example numbers. $\endgroup$ – NightRa May 17 '14 at 12:38
  • $\begingroup$ Turns out just as a regular string with characters, and lexicographical/ascii order. $\endgroup$ – NightRa May 18 '14 at 9:43
  • $\begingroup$ I got to a solution. Coming soon. $\endgroup$ – NightRa May 19 '14 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.