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

×

MINSHIFT - Editorial

PROBLEM LINK:

Contest
Practice

Author: Sergey Kulik
Testers: Vasya Antoniuk and Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Medium

PREREQUISITES:

Segment tree

PROBLEM:

Given a string $s$ of length $N \le 10^5$ generated uniformly randomly and independently, support $Q \le 10^5$ operations of two kinds:

  • Given a position $j$ and a character $c$, replace the $j$th character of $s$ by $c$. $c$ is generated uniformly randomly and independently.
  • Given $i$, $j$, and $p$, Find the $p$th character in the minimal cyclic shift of $s[i\ldots j]$.

QUICK EXPLANATION:

Let $C$ be the length of the longest repeated substring at any point during the operations. Then with very very high probability, $C$ is very small, say, $C \le 24$. So we assume we can compare two suffixes by only comparing their first $C$ characters. Similarly, we can compare cyclic shifts by comparing the first $C$ characters, assuming the cutoff point of the cyclic shift isn't within the last $C$ positions. Finally, there are only $C$ cyclic shifts where the cutoff point is within the last $C$ positions.

This means that we can set up a segment tree to compute range minimum queries. Specifically, to find the index of the minimal cyclic shift in the range $[i,j]$, find the minimum suffix in the range $[i,j-C]$, and then manually compare this minimum with the last $C$ cyclic shifts. This runs in $O(C^2 + C \log N)$. Finally, during updates where we replace the $j$th character, we simply update the suffixes in the index range $[j-C,j]$ in the segment tree. This runs in $O(C^2 \log N)$.

EXPLANATION:

Randomness

The fact that the string and the updates are generated uniformly randomly and independently is important: It means we can expect not to see any "non-random" structures in the input, like long runs of a single letter ...aaaaaaaaaaa... and other simple patterns ...aabaabaabaa.... There are still some nonzero probability that these appear, but this probability is vanishingly small for really long patterns.

Given this, let's see how a naïve algorithm will fare. Note that in the naïve algorithm, modifications are trivial. The only slow part is finding the minimal cyclic shift, which takes $O(N^2)$ in the worst case.

In this pseudocode, we let $s[i]$ be the $i$th character of $s$. Note that in the substring $s[i\ldots j]$, the $p$th character in the cyclic shift that starts at $k$ ($i \le k \le j$) is $s[i + (k - i + p - 1) \bmod (j - i + 1)]$. Also, be careful: this code uses one-indexing.

def s_cycle(i, j, k, p):
    // the p'th character in the cyclic shift of s[i..j] starting at k
    return s[i + (k - i + p - 1) % (j - i + 1)]

def s_cycle_compare(i, j, k1, k2):
    // compare the cyclic shifts starting at k1 and k2
    if k1 == k2:
        // if k1 == k2, then we already know they're equal
        return 0
    for p=1..j-i+1:
        c1 = s_cycle(i, j, k1, p)
        c2 = s_cycle(i, j, k2, p)
        if c1 < c2: return -1
        if c1 > c2: return +1

    // all characters are equal
    return 0

def find_minimal_cyclic_shift(i, j, p):
    k_min = i
    for k=i..j:
        if s_cycle_compare(i, j, k_min, k) > 0:
            k_min = k

    return s_cycle(i, j, k_min, p)

Since $s$ is generated uniformly randomly and independently, it means the comparison s_cycle_compare will most likely halt within just a couple of comparisons. Specifically, if k1 and k2 are different, then the probability of c1 being equal to c2 (and thus continuing the loop) is equal to $1/26$. So the probability that the loop runs $C$ times is $1/26^C$, which is a rapidly-decaying function! For $C = 24$, this probability is already $< 1.1\times 10^{-34}$. This is a very low number. To illustrate, notice that in a query, the most number of times s_cycle_compare will be called is $10^5$. There are at most $10^5$ queries, so there are at most $10^{10}$ calls all in all in a single test case. Thus, the probability that the loop inside s_cycle_compare runs at least $24$ times is approximately $1.1\times 10^{-34}\times 10^{10} = 1.1\times 10^{-24}$, which is still very small. Even if we run this solution against one billion test cases, the probability of it exceeding $24$ comparisons is still approximately $1.1\times 10^{-24}\times 10^9 = 1.1\times 10^{-15}$ which is still very small! (These calculations are not 100% accurate, but that's okay; they only serve to give some intuition to the smallness of $1.1\times 10^{-34}$. If for some weird reason this isn't small enough for you, you can always replace $24$ with something higher, say $30$ or $40$.)

Thus we can expect the loop in s_cycle_compare to run at most $24$ times. In fact, we can even safely modify the s_cycle_compare implementation code above to the following:

def s_cycle_compare(i, j, k1, k2):
    ...
    for p=1..min(24,j-i+1):
        ...
    ...

This is of course incorrect in some cases, but there is a very, very low probability that it will fail, so we're still good!

But notice that if we're only comparing the first $24$ characters, then for most pairs of cyclic shifts in $[i,j]$, their comparison is actually the same as the comparison between the suffixes that start in the same location! Specifically, for cyclic shifts that start in the indices $[i,j-24]$, we can expect that comparing them will finish before the indices start to wrap around the substring $s[i\ldots j]$.

To explain further, we also modify the remaining parts of the pseudocode above:

def s_cycle(i, j, k, p):
    // the p'th character in the cyclic shift of s[i..j] starting at k
    return s[i + (k - i + p - 1) % (j - i + 1)]

def s_suffix_compare(k1, k2):
    // compare the suffixes starting at k1 and k2
    // assume the string 's' is padded with a null character
    // (or some unique dummy character) at the end
    // so the loop below doesn't go out of bounds.
    if k1 == k2:
        return 0
    for p=1..24:
        c1 = s[k1+p-1]
        c2 = s[k2+p-1]
        if c1 < c2: return -1
        if c1 > c2: return +1
    return 0

def s_cycle_compare(i, j, k1, k2):
    // compare the cyclic shifts starting at k1 and k2
    if k1 == k2:
        return 0
    for p=1..min(24,j-i+1):
        c1 = s_cycle(i, j, k1, p)
        c2 = s_cycle(i, j, k2, p)
        if c1 < c2: return -1
        if c1 > c2: return +1
    return 0

def find_minimal_cyclic_shift(i, j, p):
    k_min = i
    cutoff = max(i,j-24)
    for k=i..cutoff:
        if s_suffix_compare(k_min, k) > 0:
            k_min = k
    for k=cutoff+1..j:
        if s_cycle_compare(i, j, k_min, k) > 0:
            k_min = k
    return s_cycle(i, j, k_min, p)

Notice that in the range $[i,j-24]$, we're using the s_suffix_compare function instead of s_cycle_compare. Again, this fails with very very low probability.

Faster range minimum

Unfortunately, the code above is still very slow, because the range $[i,j]$ can be large and there are a lot of queries. Specifically, it runs in $O(QNC)$ time in the worst case, where $C$ is the constant we chose. ($24$ in the code above.) To improve it, notice that the first loop in find_minimal_cyclic_shift above is actually a range minimum query. We're finding the "minimum" suffix in the range $[i,\max(i,j-C)]$, where comparison is string comparison. But range minimum queries are standard operations which can be solved in a variety of ways!

In this case, we can use segment trees because there are also updates. Specifically, we set up a segment tree over the suffixes of the string, but we only store the indices, and for comparison we use s_suffix_compare. Then when we update some character, say $s[j]$, notice that only the suffixes with indices $[j-C+1,j]$ will be affected, because of our assumption. This means we only need to update up to $C$ elements of the segment tree!

Let's analyze the running time. Segment tree point updates and range queries need $O(\log N)$ comparisons, but each operation takes $O(C)$ time, so a segment tree operation runs in $O(C \log N)$ time. The worst queries are updates, where we perform $C$ segment tree updates, so it takes $O(C^2 \log N)$ time. This means that overall, the running time is $O(QC^2 \log N)$! There's also an $O(NC)$-time construction of the segment tree.

The overall running time is $O(NC + QC^2 \log N)$ which is fast enough, but if $O(QC^2 \log N)$ looks a bit slow and bothers you, then you can consider replacing the $C$ updates with a single range update, but this time it's okay to do it without lazy propagation. At the very least it will save you some number of comparisons, particularly near the root.

Time Complexity:

$O(C (N + Q C \log N))$ where $C$ is an upper bound to the longest length of any repeated substring

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 13 Jun '16, 23:28

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 15 Jun '16, 14:22

admin's gravatar image

0★admin ♦♦
19.8k350498541


One thing I couldn't understand : The indices in the update query are not chosen randomly (only the character is selected randomly). So it is very well possible to transform the string such that the number of comparisons exceed the assumption of (24/30/40) chars in s_cycle_compare().

Please correct me if I am wrong. Thanks!

link

answered 23 Jun '16, 16:25

noob333's gravatar image

5★noob333
10414
accept rate: 0%

we can also find the lexicographically smallest character within the range [l,r] ,and then concatenate the left part at the end to find the minimal cyclic shift. Then, we will have to deal with characters instead.

will this result into a W.A.?

link

answered 26 Jan '17, 10:40

karbish98's gravatar image

2★karbish98
191
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:

×15,639
×2,585
×1,755
×70
×9

question asked: 13 Jun '16, 23:28

question was seen: 2,397 times

last updated: 26 Jan '17, 10:40