Thank you for participating in Kick Start 2021 Round H!
Cast
Transform the String: Written by Bartosz Kostka and prepared by Chu-ling Ko.
Painter: Written by Bartosz Kostka and prepared by Jared Gillespie.
Silly Substitutions: Written by Kevin Tran and prepared by Nikolai Artemiev.
Dependent Events: Written by Siddharth Nayyar and prepared by Lucas Maciel.
Solutions, other problem preparation, reviews and contest monitoring by Alan Lou, Anson Ho, Anurag Singh, Anushi Maheshwari, Bartosz Kostka, Bianca Shimizu Oe, Bohdan Pryshchenko, Brijesh Panara, Chu-ling Ko, Chun-nien Chan, Cristhian Bonilha, Deeksha Kaurav, Duong Hoang, Federico Brubacher, Guilherme Rodrigues Nogueira de Souza, Hsin-Yi Wang, Jakub Kuczkowiak, Jared Gillespie, Kashish Bansal, Kevin Tran, Laksh Nachiappan, Lizzie Sapiro Santor, Lucas Maciel, Maneeshita Sharma, Michał Łowicki, Mohamed Yosri Ahmed, Motty Porat, Nikolai Artemiev, Phil Sun, Rahul Goswami, Rishabh Agarwal, Robert O'Connor, Ruoyu Zhang, Samiksha Gupta, Sarah Young, Shahed Shahriar, Shubham Garg, Shweta Karwa, Siddharth Nayyar, Subhasmita Sahoo, Surya Upadrasta, Swapnil Gupta, Swapnil Mahajan, Swetank Modi, Tarun Khullar, Teja Vardhan Reddy Dasannagari, Umang Goel, Vijay Krishan Pandey, Wendi Wang, Yulian Yarema, Zhitao Li.
Analysis authors:
You are given a string $$$\mathbf{S}$$$ which denotes a padlock consisting of lower case English letters. You
are also given a string
$$$\mathbf{F}$$$ consisting of set of favorite lower case English letters.
You are allowed to perform several operations on the padlock. In each operation, you can change one
letter of the string to the one following it or preceding it in the alphabetical order. For example: for
the letter c, you are allowed to change it to either b or d in an operation.
The letters can be considered in a cyclic order, i.e., the preceding letter for letter a
would be letter z. Similarly, the following letter for letter z would be letter a.
Your aim is to find the minimum number of operations that are required such that each letter in string $$$\mathbf{S}$$$ after applying the operations, is present in string $$$\mathbf{F}$$$.
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow.
Each test case consists of two lines.
The first line of each test case contains the string $$$\mathbf{S}$$$.
The second line of each test case contains the string $$$\mathbf{F}$$$.
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1)
and $$$y$$$ is the minimum number of operations that are required such that each letter in string $$$\mathbf{S}$$$
after applying the operations, is one of the characters in string $$$\mathbf{F}$$$.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le$$$ the length of $$$\mathbf{S} \le 10^5$$$.
$$$\mathbf{S}$$$ only consists of lower case English letters.
$$$\mathbf{F}$$$ only consists of distinct lower case English letters.
The letters in string $$$\mathbf{F}$$$ are lexicographically sorted.
Time limit: 20 seconds.
The length of $$$\mathbf{F} = 1$$$.
Time limit: 40 seconds.
$$$1 \le $$$ the length of $$$\mathbf{F} \le 26$$$.
2 abcd a pppp p
Case #1: 6 Case #2: 0
In Sample Case #1, all the letters in string $$$\mathbf{S}$$$ should be converted to letter a.
We can keep on changing the letters to its preceding letter till we reach the letter a.
We do not need to change the first letter as it is already a. The second letter needs
$$$1$$$ operation to change it to a. The third letter needs
$$$2$$$ operations to change it to a. The fourth letter needs
$$$3$$$ operation to change it to a. Hence, we need a total of $$$6$$$ operations to
change string $$$\mathbf{S}$$$ such that all letters are changed to a.
In Sample Case #2, string $$$\mathbf{S}$$$ already contains only the favorite letter from string $$$\mathbf{F}$$$. Hence, we do not require any more operations.
3 pqrst ou abd abd aaaaaaaaaaaaaaab aceg
Case #1: 9 Case #2: 0 Case #3: 1
In Sample Case #1, all the letters in string $$$\mathbf{S}$$$ should be converted to either the letter
o or the letter u.
For the first and second letters it is optimal to change them to preceding letters till they are changed
to letter o. The first letter would take $$$1$$$ operation to change to letter o.
The second letter would take $$$2$$$ operations to change to letter o.
For fourth and fifth letters it is optimal to change them to following letters till they are changed
to letter u. The fourth letter would take $$$2$$$ operations to change to letter u.
The fifth letter would take $$$1$$$ operation to change to letter u.
We can change the third letter to either o or u as both of them would require
$$$3$$$ operations.
Hence, we need a total of $$$9$$$ operations to
change string $$$\mathbf{S}$$$ such that all letters are changed to either o or u.
In Sample Case #2, string $$$\mathbf{S}$$$ already contains only the favorite letters from string $$$\mathbf{F}$$$. Hence, we do not require any more operations.
In Sample Case #3, we only need to change the last letter b to either a or c.
Thus, we only need $$$1$$$ operation.
You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: Red, Yellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following:
You still do not understand shades of colors, therefore the proportion and order of each color in the combination does not matter. For example, combining Red and Yellow produces the same result as combining Yellow and Red, as well as the same result as combining Red, Yellow, and Red again.
To practice your skills, you want to paint a 1-dimensional painting $$$\mathbf{P}$$$ of length $$$\mathbf{N}$$$. Your painting consists of $$$\mathbf{N}$$$ squares. From left to right, $$$\mathbf{P_i}$$$ represents the color of the i-th square. Initially all squares are Uncolored, that is, $$$\mathbf{P_i}$$$ = Uncolored for every $$$1 \le i \le \mathbf{N}$$$.
In a single stroke, you can choose one of the three primary colors and apply it to a sequence of consecutive squares. In other words, you can choose a color $$$c$$$ and two integers $$$l$$$ and $$$r$$$, such that $$$1 \le l \le r \le \mathbf{N}$$$, and apply color $$$c$$$ to all squares $$$\mathbf{P_j}$$$ such that $$$l \le j \le r$$$. If the square being painted is currently Uncolored, then its color will become $$$c$$$. Otherwise, the color will be a combination of all the colors applied on this square so far and the new color $$$c$$$, as described in the list above.
In order to save time, you want to use as few strokes as possible. Given the description of the painting that you want to paint, figure out what is the minimum number of strokes required to paint it.
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow.
Each test case starts with a line containing an integer $$$\mathbf{N}$$$, representing the length of the painting. Then on the next line, there will be a string $$$\mathbf{P}$$$ of length $$$\mathbf{N}$$$, representing the painting. The $$$i$$$-th character represents the color of square $$$\mathbf{P_i}$$$, according to the following list:
U = UncoloredR = RedY = YellowB = BlueO = OrangeP = PurpleG = GreenA = Gray
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is
the minimum number of strokes required to paint the painting.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{N} \le 10^5$$$.
Time limit: 20 seconds.
$$$\mathbf{P_i}$$$ will be one of {Y, B, G}.
Time limit: 40 seconds.
$$$\mathbf{P_i}$$$ will be one of {U, R, Y, B, O, P, G, A}.
2 9 YYYBBBYYY 6 YYGGBB
Case #1: 3 Case #2: 2
In Sample Case #1, the solution is to make $$$3$$$ strokes: the first one using color Yellow from square $$$1$$$ through $$$3$$$, the second one using color Blue from square $$$4$$$ through $$$6$$$, and the third one using color Yellow from square $$$7$$$ through $$$9$$$. Notice that this particular painting required only primary colors.
In Sample Case #2, the solution is to make $$$2$$$ strokes: the first one using color Yellow from square $$$1$$$ through $$$4$$$, and the second one using color Blue from square $$$3$$$ through $$$6$$$. Notice that squares $$$3$$$ and $$$4$$$ will be painted with both colors Yellow and Blue, which will result on it being Green.
1 5 ROAOR
Case #1: 3
In Sample Case #3, the solution is to make $$$3$$$ strokes: the first one using color Red from square $$$1$$$ through $$$5$$$, the second one using color Yellow from square $$$2$$$ through $$$4$$$, and the third one using color Blue on square $$$3$$$. Notice that square $$$3$$$ is painted with all three primary colors, which will result in it being Gray.
You are given a string $$$\mathbf{S}$$$ of length $$$\mathbf{N}$$$ which consists of digits 0-9. You do the
following operations on the string in the order given.
01 and replace each of them with 2.12 and replace each of them with 3.23 and replace each of them with 4.34 and replace each of them with 5.89 and replace each of them with 0.90 and replace each of them with 1.
You repeat this process in the same given order until none of the above operations change
the string. For example, if $$$\mathbf{S}$$$ is 12 then we do not stop at operation $$$1$$$
since it does not affect the string but perform operation $$$2$$$ and change the string to
3. We can see that the string does not change further no matter how many times
we repeat the above process.
Your task is to find how the final string will look like for the given $$$\mathbf{S}$$$.
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case consists of two lines.
The first line of each test case contains an integer $$$\mathbf{N}$$$, denoting the length of the string $$$\mathbf{S}$$$.
The second line of each test case contains a string $$$\mathbf{S}$$$ of length $$$\mathbf{N}$$$.
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is the final string obtained.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
The input string only consists of digits 0-9.
Time limit: 20 seconds.
$$$1 \le \mathbf{N} \le 100$$$.
Time limit: 60 seconds.
For at most 10 cases:
$$$1 \le \mathbf{N} \le 5 \times 10^5$$$.
For the remaining cases:
$$$1 \le \mathbf{N} \le 100$$$.
4 3 012 4 0145 5 00000 11 98765432101
Case #1: 22 Case #2: 26 Case #3: 00000 Case #4: 1
In Sample Case #1, substring 01 is replaced with 2 and the resulting
string is 22 which is not affected further by any of the operations.
Therefore final string is 22.
In Sample Case #2, substring 01 is replaced with 2 and the resulting
string is 245. The substring 45 is replaced with 6 and the
resulting string is 26 which is not further affected by any of the operations.
Therefore final string is 26.
In Sample Case #3, since the operations cannot be performed on the given string, the string does not change.
In Sample Case #4, all the operations can be performed sequentially on the string and the final
string is 1.
There are $$$\mathbf{N}$$$ events, numbered $$$1$$$ through $$$\mathbf{N}$$$. The probability of occurrence of each event depends upon the occurrence of exactly one other event called the parent event, except event $$$1$$$, which is an independent event. In other words, for each event from $$$2$$$ to $$$\mathbf{N}$$$, $$$3$$$ values are given: $$$\mathbf{P_{i}}$$$ denoting the parent event of event $$$i$$$, $$$\mathbf{A_{i}}$$$ denoting the probability of occurrence of event $$$i$$$ if its parent event occurs, and $$$\mathbf{B_{i}}$$$ denoting the probability of occurrence of event $$$i$$$ if its parent event does not occur. For event $$$1$$$, its probability of occurrence $$$\mathbf{K}$$$ is given. There are $$$\mathbf{Q}$$$ queries that we want to answer. Each query consists of $$$2$$$ distinct events, $$$\mathbf{u_{j}}$$$ and $$$\mathbf{v_{j}}$$$, and you need to find the probability that both events $$$\mathbf{u_{j}}$$$ and $$$\mathbf{v_{j}}$$$ have occurred.
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow.
The first line of each test case contains two integers $$$\mathbf{N}$$$ and $$$\mathbf{Q}$$$ denoting the number of events and number of queries, respectively. $$$\mathbf{N}$$$ lines follow. The $$$i$$$-th line describes event $$$i$$$. The first line contains a single integer $$$\mathbf{K}$$$ denoting the probability of occurrence of event $$$1$$$ multiplied by $$$10^6$$$. Each of the next $$$\mathbf{N}-1$$$ lines consists of three integers $$$\mathbf{P_{i}}$$$, $$$\mathbf{A_{i}}$$$ and $$$\mathbf{B_{i}}$$$ denoting the parent event of event $$$i$$$, the probability of occurrence of event $$$i$$$ if its parent event occurs multiplied by $$$10^6$$$, and the probability of occurrence of event $$$i$$$ if its parent event does not occur multiplied by $$$10^6$$$, respectively. Then, $$$\mathbf{Q}$$$ lines follow, describing the queries. Each of these lines contains two distinct integers $$$\mathbf{u_{j}}$$$ and $$$\mathbf{v_{j}}$$$. For each query, find the probability that both events $$$\mathbf{u_{j}}$$$ and $$$\mathbf{v_{j}}$$$ occurred.
For each test case, output one line containing Case #$$$x$$$: $$$R_{1} \ R_{2} \ R_{3} \ \dots \ R_{Q}$$$, where $$$x$$$ is the
test case number (starting from 1) and $$$R_{j}$$$ is the sought probability computed for $$$j$$$-th query
modulo $$$10^9+7$$$, which is defined precisely as follows.
Represent the answer of $$$j$$$-th query as an irreducible fraction
$$$\frac{p}{q}$$$. The number $$$R_{j}$$$ then must satisfy the modular equation
$$$R_{j} \times q \equiv p \pmod{(10^{9} + 7)}$$$, and be between $$$0$$$ and
$$$10^9+6$$$, inclusive. It can be shown that under the constraints of this problem such a
number $$$R_{j}$$$ always exists and is uniquely determined.
Time limit: 60 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{P_{i}} \lt \mathbf{i}$$$, for each $$$i$$$ from $$$2$$$ to $$$\mathbf{N}$$$.
$$$1 \le \mathbf{u_{j}}, \mathbf{v_{j}} \le \mathbf{N}$$$ and $$$ \mathbf{u_{j}} \neq \mathbf{v_{j}} $$$, for all $$$j$$$.
$$$0 \le \mathbf{A_{i}} \le 10^6$$$, for each $$$i$$$ from $$$2$$$ to $$$\mathbf{N}$$$.
$$$0 \le \mathbf{B_{i}} \le 10^6$$$, for each $$$i$$$ from $$$2$$$ to $$$\mathbf{N}$$$.
$$$0 \le \mathbf{K} \le 10^6$$$.
$$$2 \le \mathbf{N} \le 1000$$$.
$$$1 \le \mathbf{Q} \le 1000$$$.
For at most 5 cases:
$$$2 \le \mathbf{N} \le 2 \times 10^{5}$$$.
$$$1 \le \mathbf{Q} \le 2 \times 10^{5}$$$.
For the remaining cases:
$$$2 \le \mathbf{N} \le 1000$$$.
$$$1 \le \mathbf{Q} \le 1000$$$.
2 5 2 200000 1 400000 300000 2 500000 200000 1 800000 100000 4 200000 400000 1 5 3 5 4 2 300000 1 100000 100000 2 300000 400000 3 500000 600000 1 2 2 4
Case #1: 136000001 556640004 Case #2: 710000005 849000006
For Sample Case #1, for the first query, the probability that both events $$$1$$$ and $$$5$$$ occurred is given by (the probability that event $$$1$$$ occurred) $$$\times$$$ (probability that event $$$5$$$ occurs given event $$$1$$$ occurred). Event $$$1$$$ would occur with probability $$$0.2$$$. Given that event $$$1$$$ occurred, the probability that event $$$4$$$ occurs is $$$0.8$$$. Therefore, the probability of occurrence of event $$$5$$$ given that event $$$1$$$ occurred is $$$0.2 \times 0.8 + 0.4 \times 0.2 = 0.24$$$ (probability of event $$$5$$$ occurring given than event $$$4$$$ occurred $$$+$$$ probability of event $$$5$$$ occurring given that event $$$4$$$ did not occur). The probability that both events $$$1$$$ and $$$5$$$ occurred is $$$0.2 \times 0.24 = 0.048$$$. The answer $$$0.048$$$ can be converted into fraction of $$$\frac{6}{125}$$$, and one can confirm that the $$$136000001$$$ satisfies the conditions mentioned in the output section as $$$136000001 \times 125 \equiv 6 \pmod{ (10^{9} + 7)}$$$ and is uniquely determined. For the second query, the probability that both events $$$5$$$ and $$$3$$$ occurred is $$$0.10352$$$.
For Sample Case #2, for the first query, the probability that both events $$$1$$$ and $$$2$$$ occurred is given by (the probability that event $$$1$$$ occurred) $$$\times$$$ (probability that event $$$2$$$ occurs given event $$$1$$$ occurred). As $$$1$$$ is the parent event of event $$$2$$$, the probability of event $$$2$$$ occurring given event $$$1$$$ occurred is $$$\mathbf{A_{2}}$$$ which is $$$0.1$$$. Hence, the probability that both events $$$1$$$ and $$$2$$$ occurred is $$$0.3 \times 0.1$$$. Hence, the output will be $$$ 3 \times 10^{-2} \bmod (10^9+7) = 710000005$$$. For the second query, the probability of occurrence of both events $$$2$$$ and $$$4$$$ is $$$0.057$$$.
Let us first define the two operations that we can perform.
c to d.a to z.Let us denote the ASCII value of a character $$$c_x$$$ by $$$ASCII(c_x)$$$. If we move the padlock from a character $$$c_a$$$ to another character $$$c_b$$$ such that $$$ASCII(c_a) < ASCII(c_b)$$$, the number of operations required in clockwise direction = $$$ASCII(c_b) - ASCII(c_a)$$$ and the number of operations required in counter-clockwise direction = $$$26 - (ASCII(c_b) - ASCII(c_a))$$$.
For example, if we move the padlock from c to e:
Similarly, if we move the padlock from a character $$$c_a$$$ to another character $$$c_b$$$ such that $$$ASCII(c_a) > ASCII(c_b)$$$, the number of operations required in clockwise direction = $$$26 - (ASCII(c_a) - ASCII(c_b))$$$ and the number of operations required in counter-clockwise direction = $$$ASCII(c_a) - ASCII(c_b))$$$.
For example, if we move the padlock from g to b:
Thus minimum number of operations required to change a character in the padlock from $$$c_a$$$ to $$$c_b$$$ = $$$min(abs(ASCII(c_a) - ASCII(c_b)), 26 - abs(ASCII(c_a) - ASCII(c_b)))$$$.
Let us call the above expression $$$f(c_a, c_b)$$$.
When length of $$$\mathbf{F}$$$ = $$$1$$$ we need to change every character in $$$\mathbf{S}$$$ to that in $$$\mathbf{F}$$$. Therefore, the answer is the sum of $$$f(c_s, c_f)$$$ for every character $$$c_s$$$ in $$$\mathbf{S}$$$ and $$$c_f$$$ in $$$\mathbf{F}$$$.
For this case, $$$\mathbf{F}$$$ can have multiple characters.
For each character in $$$\mathbf{S}$$$ we need to find a character in $$$\mathbf{F}$$$ such that $$$f(c_s, c_f)$$$ is minimized. Therefore, for every character $$$c_s$$$ in $$$\mathbf{S}$$$, we iterate over all possible characters $$$c_f$$$ in $$$\mathbf{F}$$$ and find minimum of $$$f(c_s, c_f)$$$ and add the minimum value to the final answer.
For each character in $$$\mathbf{S}$$$, move the padlock in the clockwise direction and count the number of operations until we reach a character that belongs to $$$\mathbf{F}$$$. Similarly, for the same character in $$$\mathbf{S}$$$, move the padlock in the counter-clockwise direction and count the number of operations until we reach a character that belongs to $$$\mathbf{F}$$$. Compare the number of operations in both directions and add minimum of the two to the final answer.
Given the three primary colors: Red, Yellow, and Blue, we need to determine the minimum number of strokes required to paint a 1-dimensional painting $$$\mathbf{P}$$$ of length $$$\mathbf{N}$$$. In $$$1$$$ stroke, you can choose a color either Red, Yellow, or Blue, and two integers $$$l$$$ and $$$r$$$, such that $$$1 \le l \le r \le \mathbf{N}$$$, and apply the chosen color to all squares $$$\mathbf{P_j}$$$ such that $$$l \le j \le r$$$.
Note as the colors: Red, Yellow, and Blue are independent of each other and the proportion and order of each color in the combination does not matter, the minimum number of strokes to complete the paining will be the minimum number of Red strokes $$$+$$$ minimum number of Blue strokes $$$+$$$ minimum number of Yellow strokes.
Let $$$F(x)$$$ be the minimum number of strokes needed of primary color $$$x$$$. Notice minimum number of strokes of $$$x$$$ is same as number of continuous blocks of squares that will need the primary color $$$x$$$ to form the required color. To find $$$F(x)$$$ we will start from the leftmost end of the squares. Whenever we encounter a square either with the color $$$x$$$ or with some color $$$y$$$ which is a combination of $$$x$$$ and other primary colors, we paint the squares with the color $$$x$$$ in $$$1$$$ stroke until we reach the rightmost end, or some color $$$y$$$ which is neither $$$x$$$ nor a combination of $$$x$$$ and any other primary color. We continue this until we have encountered all the squares. The number of strokes used is equal to $$$F(x)$$$.
We are given that $$$\mathbf{P_i}$$$ will be one of {$$$Y, B, G$$$}. The final answer will be $$$F(Yellow) + F(Blue)$$$.
Complexity : $$$O(\mathbf{N})$$$ per test case
We are given that $$$\mathbf{P_i}$$$ will be one of {$$$U, R, Y, B, O, P, G, A$$$}. The final answer will be $$$F(Red) + F(Yellow) + F(Blue)$$$.
Complexity : $$$O(\mathbf{N})$$$ per test case
int minimum_number_of_strokes_for_primary_color_x(string S, int N, char x, map<char, string> color_to_primary_colors_mapping) {
int min_strokes = 0;
int last_stroke_position = INT_MIN;
for(int i = 0; i < N; i++) {
if (S[i] == 'U') {
continue;
}
if(S[i] == x || color_to_primary_colors[S[i]].find(x) != string::npos) {
if (last_stroke_position != i - 1) {
min_strokes++;
}
last_stroke_position = i;
}
}
return min_strokes;
}
In this problem, each replacement shortens the string by one character, so the number of replacements is no more than $$$\mathbf{N}$$$. It is the complexity of each replacement that may bother us.
The basic step that we are asked to do is the "replace all" operation; that is, to find all the occurrences of a given substring within a given string, and replace them with another string.
Many programming languages have a built-in function that does exactly this; for example, in both
Python and Java it is called replace().
In other languages you may implement the "replace all" operation by using a few basic operations
or completely from scratch. Either way, the typical implementation of "replace all" would take
linear time, because it has to:
And then, we are asked to apply "replace all" until there is nothing to change. This would look like (pseudo-code):
while True:
previous = s
s = s.replace_all('01', '2').replace_all('12', '3')....replace_all('90', '1')
if s == previous:
return s
This loop makes up to $$$\mathbf{N}$$$ iterations, each iteration attempts the "replace all" operation $$$10$$$ times, and, as said, each attempt takes $$$O(\mathbf{N})$$$.
Therefore, complexity: $$$O(\mathbf{N} ^ 2)$$$ per test case.
To reduce the complexity we should implement our own "replace all" and optimize the two things that it does:
01, all
locations of the substring 12, and so on.
How to define a location in a string that keeps changing? The next bullet solves this.
A "replace all" operation might still take linear time in the optimized version. For example, if
$$$\mathbf{S} = $$$010101010101 then the first replacement (of all the 01s to
2s) will have to replace $$$\mathbf{N}/2$$$ occurrences. But then, the next operations will
be either few enough or fast enough to compensate for the long one. This is known as
amortized analysis.
More accurately, whenever a location becomes interesting, one of the future replacement operations
will have to handle it (as said, by $$$O(1)$$$ manipulations of the linked list). How many times
can locations become interesting? In the initial string, maybe all the $$$\mathbf{N}$$$ characters (except the
last one) start as interesting. Later on, whenever we replace a pair of characters with a new one,
that new character may turn one or both its neighbors to be interesting. For example, when
changing 1013 to 123 it creates two interesting substrings:
12 and 23. Finer analysis can show that we only need to mark the
12 as interesting, but it does not really matter for our conclusion.
So, since we replace characters at most $$$\mathbf{N}$$$ times, the event of a location becoming interesting can happen at most $$$3\mathbf{N}$$$ times (or $$$2\mathbf{N}$$$ with finer analysis).
Therefore, complexity: $$$O(\mathbf{N})$$$ per test case
Notes:
01). Of course, our "replace all" operation
will need to check if each "interesting location" should indeed be replaced, but this is a good
practice anyway. The best part is that our analysis with the $$$3\mathbf{N}$$$ bound will still be
valid.For this problem, we are given a graphical model in the form of a directed, rooted tree, where each vertex is an event. For any vertex $$$v$$$ on this tree, let $$$v=0$$$ and $$$v=1$$$ denote the non-occurrence and occurrence of event $$$v$$$, respectively. Let $$$l_j$$$ be the lowest common ancestor (LCA) of $$$\mathbf{u_j}$$$ and $$$\mathbf{v_j}$$$. By the total probability rule, $$$P[\mathbf{u_j}=1, \mathbf{v_j}=1]=\sum_{i=0}^1 P[\mathbf{u_j}=1, \mathbf{v_j}=1, l_j=i]$$$. We know $$$\mathbf{u_j}$$$ and $$$\mathbf{v_j}$$$ are conditionally independent given $$$l_j$$$, because the paths $$$l_j\rightarrow \mathbf{u_j}$$$ and $$$l_j\rightarrow \mathbf{v_j}$$$ are edge-disjoint due to the definition of LCA. This allows us to simplify the earlier sum into $$$\sum_{i=0}^1 P[\mathbf{u_j}=1 | l_j=i]P[\mathbf{v_j}=1 | l_j = i]P[l_j=i]$$$. This formula forms the basis of our solution, and the approaches for the two test sets differ only in how to compute the required probabilities efficiently.
To deal with the output format of this problem, we store all results as fractions and take the numerator and denominator modulo $$$10^9+7$$$ after each operation to avoid overflow. If our final result is $$$\frac{p}{q}$$$, we output $$$pq^{-1}\pmod{10^9+7}$$$. Due to the nature of the problem, $$$q$$$ will always be a power of ten, so the inverse is guaranteed to exist, and can be efficiently computed via extended Euclidean algorithm. Alternatively, due to Fermat's little theorem, we can equivalently raise $$$q$$$ to the $$$(10^9+5)$$$-th power to find its inverse; this can be done efficiently with exponentiation by squaring.
For this test set it suffices to naively compute $$$l_j$$$. We can then compute $$$P[\mathbf{u_j}=1|l_j]$$$ and $$$P[\mathbf{v_j}=1|l_j]$$$ by walking back down the tree from $$$l_j$$$. To do this, we can use the total probability rule similar to before; if $$$p(x)$$$ denotes the parent of $$$x$$$, then $$$P[x=1 | l_j=i] = \sum_{k=0}^1P[x=1,p(x)=k | l_j=i] = \sum_{k=0}^1 P[x=1 | p(x)=k]P[p(x)=k | l_j = i]$$$; note that the first term in this product comes from the input, and the second term comes from the previous step of our walk. We can use the same formula to compute $$$P[l_j=i]$$$, since $$$P[l_j=i]=\sum_{k=0}^1P[l_j=i|r=k]P[r=k]$$$, where $$$r$$$ is the root of the tree.
Each vertex is visited at most $$$O(1)$$$ times per query using this technique, so our overall time complexity is $$$O(\mathbf{NQ})$$$ per test case, which is sufficient.
There are both more queries and a larger tree in this test set, so the naive solution is too slow. This test set requires computing $$$l_j$$$, the LCA of $$$\mathbf{u_j}$$$ and $$$\mathbf{v_j}$$$, in $$$O(\log \mathbf{N})$$$ time anyways, so we can think of ways to augment an LCA algorithm to also keep track of the necessary probabilities for us. For example, the binary lifting LCA algorithm pre-computes $$$p^i(v)$$$ for all vertices $$$v$$$, where $$$p^i(\cdot)$$$ gives the $$$2^i$$$-th parent of a given vertex. We can extend the binary lifting algorithm to not only store the id of this parent, but to also store $$$P[v=1|p^i(v)]$$$. These probabilities can then be multiplied such that only $$$O(\log \mathbf{N})$$$ hops are needed to get from $$$\mathbf{u_j}$$$ or $$$\mathbf{v_j}$$$ up to $$$l_j$$$. The unconditional probability $$$P[l_j]$$$ can simply be pre-computed for the entire tree via DFS in $$$O(\mathbf{N})$$$ time. This allows us to answer each query in $$$O(\log \mathbf{N})$$$ time, so our overall time complexity is $$$O(\mathbf{N}\log \mathbf{N}+\mathbf{Q}\log \mathbf{N})$$$ per test case.