This is an original string manipulation problem that I wrote. It was included on the 2014 Australian Invitational Informatics Olympiad. In my opinion it would be a question of moderate difficulty on an IOI exam.
Before we can track runs of the critical word within the text, we first need the ability to detect the formation of individual instances of the critical word. Intuitively, some update operations make us closer to a critical word; e.g. if the critical word is "badger", then an update operation "booger" $\to$ "bodger" gets us closer to "badger". Inversely, "bodger" $\to$ "booger" gets us further from the formation of the critical word. Specifically, some $C$-length substring of the text gets closer/further if its edit distance to the critical string (the number of characters that differ across both strings) decreases/increases respectively.
The following observation drives our first technique.
Observation 1. Each update operation results in a decrease in edit distance to at most one instance of a $C$-length substring of the text, and an increase in edit distance to most one instance of a $C$-length substring in the text.
This is a result of the character-distinctness property of the critical string. Say we set a character in the text to 'a'. If the critical string does not contain 'a', then no text substring's edit distance could have decreased. If the critical string contains one occurrence of 'a' at position $p_a$, then only the text substring whose $p_a$th character has become $a$ has a reduction in edit distance. The critical string cannot contain more than one occurrence of 'a' so we need not consider more cases.
Similarly, if we are replacing the character 'b' with 'a', then an increase an edit distance occurs only for the substring whose $p_b$th character is replaced, or for no strings if 'b' does not appear in the critical string.
Sub-algorithm 1. By maintaining a map of character to critical string position (i.e. $c \to p_c$) we can find which $C$-length substring gets closer (if any) and which $C$-length substring gets further (if any) in constant time.
If we are updating position $i$ in the text from character $c$ to character $d$, the substring that gets closer begins at position $i - p_c$ in the text and the substring that gets further begins at position $i - p_d$ (all positions are 0-based by the way).
Sub-algorithm 2. Store, for each position $i \in 0..T-C+1$ in the text, the edit distance of the $C$-length substring beginning at position $i$ in the text. After each update operation, make the zero, one, or two necessary modifications to these values (as indicated by sub-algorithm 1). After replacing the character $c$ at position $i$ with $d$, we can determine in constant time if a critical word instance has been formed or un-formed by querying the edit distance at $i-p_c$ and $i-p_d$. This is all constant time.
Sub-algorithm 2 allow us to detect formations and un-formations of the critical word in the text as we go, in $O(1)$ time for each update. The next step is to detect runs of the critical word in the text. To do this, we introduce a complex data structure into the equation.
I'll begin by posing a more straight-forward problem. We have a binary string. We then perform a series of updates on the string. In each update we set or unset a bit in the string. After each update, we need to output the length of the longest run of 1's in the string.
In fact, we can implement a range tree that handles these exact update and query operations. I won't go into the implementation details, but I will mention what each tree node stores:
Sub-algorithm 3. Instantiate $C$ longest-run trees, where each represents a different 'offset' of a critical string run within the text. The first 'offset' has the first letter of the critical string at indices 0, $C, 2C, ...$ within the text, the second 'offset' has the first letter at indices $1, C+1, 2C+1, ...$, etc.
Each time we detect the completion of a critical word within the text (using sub-algorithm 2), let the position of the beginning of the critical word be $p_0$. Take the $(p_0 \bmod C)$'th longest-run tree and "set the bit" in the tree at index $\left\lfloor \frac{p_0}{C} \right\rfloor$. Do the same for any critical words that we unformed -- find their offset's tree, find the position in the tree, and unset the bit.
Now if we query that tree, we discover the longest run of consecutive critical words in that 'offset'. Setting and unsetting bits is $O(\lg T)$ and querying is also $O(\lg T)$.
We are almost done! After making an update, we can query the longest run for a particular offset of the critical word in logarithmic time. But how do we know if this offset contains the maximum-length run?
For this, we introduce yet another data structure (an easier one this time). We use a max-first priority queue.
Sub-algorithm 4. Initialise a priority queue of integer pairs where each pair is of the form (maximum run-length in tree, tree ID), sorted in descending order by the former. Each time we "set a bit" in a tree, query the maximum run-length of that tree. Push onto the priority queue the maximum run-length in that tree as well as the tree ID.
Now when it comes time to output the maximum run-length of the critical string, query the priority queue. This will give you the maximum run-length across all trees, as well as the tree in which that maximum run-length occurs. However, we can't necessarily trust this value! What if we'd pushed it to the queue a long time ago, and subsequent updates have removed that run of the critical word? To cater for this, we must now query the tree with the tree ID that we just popped to ensure its run length is truly the longest. If it's not, we ignore this priority queue element, pop it off and try the next one.
You can also use a set as your priority queue, and erase elements when you unset bits rather than the lazy deletion we're using.
Each time we do an update, we push something to the queue. We might set a bit up to $T$ times, so potentially we could have $T$ elements on the queue (though this is really unlikely). A queue with $T$ elements has $O(\lg T)$-time operations. Each time we do an update, we potentially pop several things off the queue, but since the total number of elements on the queue is bounded, this amortizes to one pop per update. So the time complexity of each update is the time complexity of a constant number of range tree operations followed by an amortized constant number of priority queue operations. $O(\lg T + \lg U) = O(\log TU)$.
Since we do this for each update, we end up with $O(U \log TU)$ as required.
The implementation is not as horrible as it seems! Mine was 110 lines of C++.
You are given a critical string of length $C$ in some arbitrarily large alphabet $\Sigma$ and some text of length $T$ in $\Sigma$ ($C \leq T \leq 10^6$). You are guaranteed that each character in $\Sigma$ appears at most once in the critical string. You are then instructed to perform $U$ update operations; each operation is of the form "set the character at position $i$ in the text to be $x$" ($0 \leq i < T, x \in \Sigma, U \leq 10^6$) . After each update operation, output the maximum number of consecutive occurrences ("runs") of the critical string in the text. The intended time complexity is linearithmic.The difficulty in this question arises from the number of different sub-algorithms/techniques (three or four of them) that need to be applied to construct a complete solution. What follows is my solution.
Before we can track runs of the critical word within the text, we first need the ability to detect the formation of individual instances of the critical word. Intuitively, some update operations make us closer to a critical word; e.g. if the critical word is "badger", then an update operation "booger" $\to$ "bodger" gets us closer to "badger". Inversely, "bodger" $\to$ "booger" gets us further from the formation of the critical word. Specifically, some $C$-length substring of the text gets closer/further if its edit distance to the critical string (the number of characters that differ across both strings) decreases/increases respectively.
The following observation drives our first technique.
Observation 1. Each update operation results in a decrease in edit distance to at most one instance of a $C$-length substring of the text, and an increase in edit distance to most one instance of a $C$-length substring in the text.
This is a result of the character-distinctness property of the critical string. Say we set a character in the text to 'a'. If the critical string does not contain 'a', then no text substring's edit distance could have decreased. If the critical string contains one occurrence of 'a' at position $p_a$, then only the text substring whose $p_a$th character has become $a$ has a reduction in edit distance. The critical string cannot contain more than one occurrence of 'a' so we need not consider more cases.
Similarly, if we are replacing the character 'b' with 'a', then an increase an edit distance occurs only for the substring whose $p_b$th character is replaced, or for no strings if 'b' does not appear in the critical string.
Sub-algorithm 1. By maintaining a map of character to critical string position (i.e. $c \to p_c$) we can find which $C$-length substring gets closer (if any) and which $C$-length substring gets further (if any) in constant time.
If we are updating position $i$ in the text from character $c$ to character $d$, the substring that gets closer begins at position $i - p_c$ in the text and the substring that gets further begins at position $i - p_d$ (all positions are 0-based by the way).
Sub-algorithm 2. Store, for each position $i \in 0..T-C+1$ in the text, the edit distance of the $C$-length substring beginning at position $i$ in the text. After each update operation, make the zero, one, or two necessary modifications to these values (as indicated by sub-algorithm 1). After replacing the character $c$ at position $i$ with $d$, we can determine in constant time if a critical word instance has been formed or un-formed by querying the edit distance at $i-p_c$ and $i-p_d$. This is all constant time.
Sub-algorithm 2 allow us to detect formations and un-formations of the critical word in the text as we go, in $O(1)$ time for each update. The next step is to detect runs of the critical word in the text. To do this, we introduce a complex data structure into the equation.
I'll begin by posing a more straight-forward problem. We have a binary string. We then perform a series of updates on the string. In each update we set or unset a bit in the string. After each update, we need to output the length of the longest run of 1's in the string.
In fact, we can implement a range tree that handles these exact update and query operations. I won't go into the implementation details, but I will mention what each tree node stores:
- The longest run in the interval contained by the node
- The size of the run that is incident to the left side of the node's interval
- The size of the run that is incident to the right side of the node's interval
Sub-algorithm 3. Instantiate $C$ longest-run trees, where each represents a different 'offset' of a critical string run within the text. The first 'offset' has the first letter of the critical string at indices 0, $C, 2C, ...$ within the text, the second 'offset' has the first letter at indices $1, C+1, 2C+1, ...$, etc.
Each time we detect the completion of a critical word within the text (using sub-algorithm 2), let the position of the beginning of the critical word be $p_0$. Take the $(p_0 \bmod C)$'th longest-run tree and "set the bit" in the tree at index $\left\lfloor \frac{p_0}{C} \right\rfloor$. Do the same for any critical words that we unformed -- find their offset's tree, find the position in the tree, and unset the bit.
Now if we query that tree, we discover the longest run of consecutive critical words in that 'offset'. Setting and unsetting bits is $O(\lg T)$ and querying is also $O(\lg T)$.
We are almost done! After making an update, we can query the longest run for a particular offset of the critical word in logarithmic time. But how do we know if this offset contains the maximum-length run?
For this, we introduce yet another data structure (an easier one this time). We use a max-first priority queue.
Sub-algorithm 4. Initialise a priority queue of integer pairs where each pair is of the form (maximum run-length in tree, tree ID), sorted in descending order by the former. Each time we "set a bit" in a tree, query the maximum run-length of that tree. Push onto the priority queue the maximum run-length in that tree as well as the tree ID.
Now when it comes time to output the maximum run-length of the critical string, query the priority queue. This will give you the maximum run-length across all trees, as well as the tree in which that maximum run-length occurs. However, we can't necessarily trust this value! What if we'd pushed it to the queue a long time ago, and subsequent updates have removed that run of the critical word? To cater for this, we must now query the tree with the tree ID that we just popped to ensure its run length is truly the longest. If it's not, we ignore this priority queue element, pop it off and try the next one.
You can also use a set as your priority queue, and erase elements when you unset bits rather than the lazy deletion we're using.
Each time we do an update, we push something to the queue. We might set a bit up to $T$ times, so potentially we could have $T$ elements on the queue (though this is really unlikely). A queue with $T$ elements has $O(\lg T)$-time operations. Each time we do an update, we potentially pop several things off the queue, but since the total number of elements on the queue is bounded, this amortizes to one pop per update. So the time complexity of each update is the time complexity of a constant number of range tree operations followed by an amortized constant number of priority queue operations. $O(\lg T + \lg U) = O(\log TU)$.
Since we do this for each update, we end up with $O(U \log TU)$ as required.
The implementation is not as horrible as it seems! Mine was 110 lines of C++.
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;
#define MAX_N 1000005
#define MAX_W MAX_N
#define ROOT 0
#define LC(n) (2*(n)+1)
#define RC(n) (2*(n)+2)
struct node {
int left, right, mid;
};
node *trees[MAX_N];
map<int, int> subtract;
int counters[MAX_N];
int N, W, Q, word[MAX_W], searchStr[MAX_N];
priority_queue<pair<int, int> > maxConsPQ; // <max cons in tree, tree id>
int LAST;
int total;
void put(node t[], int cur, int u, int ns, int ne, bool v) {
assert(ns <= u && u <= ne);
if (ns == u && u == ne) {
t[cur].left = t[cur].right = t[cur].mid = v;
} else {
if (u <= (ns+ne) / 2) {
put(t, LC(cur), u, ns, (ns+ne)/2, v);
} else {
put(t, RC(cur), u, (ns + ne)/2 + 1, ne, v);
}
int half = (ne - ns + 1) / 2, mid = 0;
mid = max(mid, t[LC(cur)].right + t[RC(cur)].left);
mid = max(mid, max(t[LC(cur)].mid, t[RC(cur)].mid));
mid = max(mid, max(t[LC(cur)].left, t[RC(cur)].right));
t[cur].mid = mid;
t[cur].left = t[LC(cur)].left;
if (t[LC(cur)].left == half) {
t[cur].left += t[RC(cur)].left;
}
t[cur].right = t[RC(cur)].right;
if (t[RC(cur)].right == half) {
t[cur].right += t[LC(cur)].right;
}
}
}
void change(int pos, int nc, bool isInitial) {
int oc = searchStr[pos];
if (!isInitial && subtract.find(oc) != subtract.end() && pos - subtract[oc] >= 0) {
int po = pos - subtract[oc];
if (W == counters[po]) {
total--;
put(trees[po % W], ROOT, po / W, 0, LAST, false);
maxConsPQ.push(make_pair(trees[po%W][ROOT].mid, po % W));
}
counters[po]--;
assert(counters[po] >= 0);
}
searchStr[pos] = nc;
if (subtract.find(nc) != subtract.end() && pos - subtract[nc] >= 0) {
int pn = pos - subtract[nc];
counters[pn] ++;
assert(counters[pn] <= W);
if (W == counters[pn]) {
total++;
put(trees[pn % W], ROOT, pn / W, 0, LAST, true);
maxConsPQ.push(make_pair(trees[pn%W][ROOT].mid, pn % W));
}
}
}
int query() {
while (!maxConsPQ.empty() && trees[maxConsPQ.top().second][ROOT].mid != maxConsPQ.top().first) {
maxConsPQ.pop();
}
return maxConsPQ.empty() ? 0 : maxConsPQ.top().first;
}
int main() {
scanf("%d %d", &W, &N);
int treeSize = 1;
while (treeSize < N/W) treeSize <<= 1;
LAST = treeSize - 1;
for (int w = 0; w < W; w++) {
scanf("%d", &word[w]);
trees[w] = (node*) malloc(sizeof(node) * 2*treeSize);
memset(trees[w], 0, sizeof(node) * 2*treeSize);
subtract[word[w]] = w;
}
for (int n = 0; n < N; n++) {
scanf("%d", &searchStr[n]);
change(n, searchStr[n], true);
}
scanf("%d", &Q);
for (int q = 0; q < Q; q++) {
int i, x;
scanf("%d %d", &i, &x);
change(i-1, x, false);
printf("%d %d\n", total, query());
}
return 0;
}
