This year's Code Jam to I/O for Women came later in the year than its recent predecessors, but it was hopefully worth the wait!

The round started with *Impartial Offerings*, helping the budget-conscietious
Aroha stay generous with her beloved pet friends. One small insight allowed contestants
to get some points, and a second one was enough to solve the full problem greedily.
*Inconstant Ordering* followed with a more abstract scenario, and this time the greedy
strategy was less apparent, but more straightforward to code. There was larger leap in
difficulty landing into the third problem, *Introductions Organization*, in which some
clever graph modeling was needed. Finally, *Irrefutable Outcome* had three test sets:
some careful brute force would get you a few points and applying some dynamic programming
to it would get you some extra, but a thorough analysis of the game was needed to
obtain the full score.

**IloveShokupanman** was the first one to a perfect score (something that hasn't been achieved
since 2017), and landed at the top of the scoreboard once the round concluded. **ITO444** came in
with a super close second place finishing only 10 penalty seconds behind, and
**giada** rounded out the top 3. In total, 10 people managed a perfect score. More than 5000
people scored some points out of the more than 6600 that submitted a solution.

Unfortunately, there was an incorrect limit in the Hidden test set of Introductions Organization, which we discovered only after the Hidden results were already revealed. The test data was corrected to match the statement that was displayed during the round. All affected solutions have been re-judged and points have been updated accordingly. As a result, ranks may change slightly from what was previously displayed. We apologize for the confusion.

We hope that Code Jam to I/O for Women 2021 was fun and challenging, and that everyone finished having learned something new. Congratulations to those in the top 150: you earned special tickets to virtual Google I/O 2021! You will be contacted by the team soon to claim your prize.

We look forward to having everyone back again in 2022. Until then, the current Code Jam season is in full swing, and you can also train and compete year round with Kick Start.

**Cast**

Impartial Offerings: Written by Frances Cooper. Prepared by Vivian Tsai.

Inconstant Ordering: Written by Daria Tupikina. Prepared by Sadia Atique.

Introductions Optimization: Written by Pablo Heiber. Prepared by Jonathan Irvin Gunawan.

Irrefutable Outcome: Written and prepared by Sherry Wu.

Solutions and other problem preparation and review by Anushi Maheshwari, Balganym Tulebayeva, Bianca Shimizu Oe, Bohdan Pryshchenko, Cindy Le, Daria Tupikina, Deepika Naryani, Diana Tanase, Hsin-Yi Wang, Ian Tullis, Jasmine Yan, Jonathan Irvin Gunawan, Liang Bai, Marina Vasilenko, Max Ward, Md Mahbubul Hasan, Pablo Heiber, Pi-Hsun Shih, Sadia Atique, Samiksha Gupta, Sherry Wu, Shuhan Fan, Swetha Srinivasan, Teja Vardhan Reddy Dasannagari, Timothy Buzzelli, and Vivian Tsai.

Analysis authors:

- Impartial Offerings: Sadia Atique.
- Inconstant Ordering: Samiksha Gupta.
- Introductions Optimization: Balganym Tulebayeva, Ian Tullis, Jonathan Irvin Gunawan, and Pablo Heiber.
- Irrefutable Outcome: Vivian Tsai.

Aroha is a big animal lover, so she spends some free time taking care of many of her loved ones' pets. She likes to offer them treats, but wants to do that in an impartial way.

Aroha decided that it was logical for pets of the same size to get the same amount of treats and for larger pets to get strictly more treats than smaller ones. For example, if she has $$$4$$$ pets with her of sizes $$$10, 20, 10$$$, and $$$25$$$, she could offer $$$2$$$ treats to each pet of size $$$10$$$, $$$3$$$ treats to the pet of size $$$20$$$, and $$$5$$$ treats to the pet of size $$$25$$$. This requires her to buy a total of $$$2+3+2+5=12$$$ treats. However, she can offer treats to all $$$4$$$ pets and comply with her own rules with a total of just $$$7$$$ treats by offering $$$1$$$ each to the pets of size $$$10$$$, $$$2$$$ to the pet of size $$$20$$$, and $$$3$$$ to the pet of size $$$25$$$.

Help Aroha plan her next pet day. Given the sizes of all pets that will accompany her, compute the minimum number of treats she needs to buy to be able to offer at least one treat to all pets while complying with her impartiality rules.

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 a test case contains a single integer $$$\mathbf{N}$$$, the number of pets in Aroha's next pet day. The second line of a test case contains $$$\mathbf{N}$$$ integers $$$\mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N}$$$, representing the sizes of each pet.

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 treats she needs to buy to be able to offer
at least one treat to all pets while complying with her impartiality rules.

Time limit: 10 seconds.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

$$$1 \le \mathbf{S_i} \le 100$$$, for all $$$i$$$.

$$$2 \le \mathbf{N} \le 5$$$.

$$$2 \le \mathbf{N} \le 100$$$.

Sample Input

3 4 10 20 10 25 5 7 7 7 7 7 2 100 1

Sample Output

Case #1: 7 Case #2: 5 Case #3: 3

Sample Case #1 is the case explained above.

In Sample Case #2, all pets are of the same size, so Aroha must offer them all the same amount of treats. The minimum total is attained by offering each pet a single treat.

In Sample Case #3, both pets are of different size so they need a different amount of treats each. Buying less than $$$2$$$ treats is not enough to give treats to both pets. Buying $$$2$$$ treats and making sure both pets get something would force Aroha to give both pets the same amount, despite them having different size. Using $$$3$$$ treats Aroha can give $$$1$$$ to the small pet and $$$2$$$ to the big pet and thus comply with all her rules.

We want to build a string with English alphabet uppercase letters in sorted order. However, we want the order to be sometimes strictly increasing and sometimes strictly decreasing.

The first letter of the string must be `A`

.
After that, the string must contain one or more blocks of letters.
The $$$i$$$-th block must contain exactly $$$\mathbf{L_i}$$$ letters.
Each letter in the $$$i$$$-th block must be later in the
alphabet than its preceding letter in the string if $$$i$$$ is odd and earlier in the alphabet
than its preceding letter if $$$i$$$ is even. Notice that for the first
letter of a block, its preceding letter exists, even though it is not in the block.
Strings that follow all of these rules
are called valid. There can be multiple valid strings, and we want
to find the alphabetically first one.

For example, if there are $$$2$$$ blocks of sizes $$$\mathbf{L_1}=2$$$ and $$$\mathbf{L_2}=3$$$, the
string must have exactly $$$1+\mathbf{L_1}+\mathbf{L_2}=1+2+3=6$$$ letters (the $$$1$$$ is for the
initial `A`

).
The strings `XYZYBA`

, `AZYCBA`

and `AYZYBB`

are not valid
for this case because they violate the required starting letter condition, and the ordering
conditions in the first
and second block, respectively. The string `AYZYBA`

is valid.
The string `ABDCBA`

is also valid and, moreover, it is the alphabetically first valid
string.

Given the sizes of the blocks, output the valid string that comes first in alphabetical order in the list of all valid strings. It can be shown that, for all inputs within the given limits, at least one valid string exists.

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case is described with two lines. The first line of a test case contains a single integer $$$\mathbf{N}$$$, the number of blocks. The second line contains $$$\mathbf{N}$$$ integers $$$\mathbf{L_1}, \mathbf{L_2}, \dots, \mathbf{L_N}$$$, the number of letters each block must have, in order.

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 valid string
that comes first in alphabetical order. It is guaranteed that at least one
valid string exists.

Time limit: 10 seconds.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

$$$1 \le \mathbf{L_i} \le 25$$$, for all $$$i$$$.

$$$1 \le \mathbf{N} \le 2$$$.

$$$1 \le \mathbf{N} \le 100$$$.

Sample Input

3 2 2 3 2 5 1 1 2

Sample Output

Case #1: ABDCBA Case #2: ABCDEFA Case #3: ABC

After Apricot Rules LLC went through a reorganization, a new large team was formed containing $$$\mathbf{M}$$$ managers and $$$\mathbf{N}$$$ non-managers. Since many people within the team do not know each other, a number of introduction sessions are to be scheduled. We know exactly which pairs of members already know each other.

The introduction sessions are organized into time slots that take $$$1$$$ minute. The first time slot starts at 8:00 AM and ends at 8:01 AM. The $$$i$$$-th time slot starts $$$i-1$$$ minutes after 8:00 AM and ends $$$i$$$ minutes after 8:00 AM. During each time slot, there can be one or more introduction sessions. A team member can be assigned to at most one introduction session per time slot. Each introduction session must have exactly three members: an assigned manager $$$a$$$ who must be a manager and two others $$$b$$$ and $$$c$$$ who can be managers or non-managers. The assigned manager $$$a$$$ must already know $$$b$$$ and $$$c$$$ for the session to be scheduled. After the introduction session, $$$b$$$ and $$$c$$$ are considered to know each other too. If $$$b$$$ and/or $$$c$$$ are managers, either of them can be the assigned manager of a future introduction session that includes both.

For some pairs of people in the team, we want to know the shortest time that is needed for them to finally know each other, or whether it is impossible for that to happen through the described process. If two people know each other before any introduction sessions happen, we define that shortest time to be $$$0$$$ minutes.

Even though we are interested in multiple pairs of people, we are considering the situations independently. That is, the minimum time for each pair can depend on a specific organization of the introduction that is particular to that pair only.

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$.
$$$\mathbf{T}$$$ test cases follow. Each test case begins with a line containing
three integers $$$\mathbf{M}$$$, $$$\mathbf{N}$$$, and $$$\mathbf{P}$$$: the number of managers on the new team, the
number of non-managers on the new team, and the number of pairs of team members we are
going to ask about, respectively. Managers are numbered from 1 through $$$\mathbf{M}$$$ and
non-managers are numbered from $$$\mathbf{M} + 1$$$ through $$$\mathbf{M} + \mathbf{N}$$$. Then,
$$$\mathbf{M} + \mathbf{N}$$$ lines follow with $$$\mathbf{M} + \mathbf{N}$$$ characters each.
The j-th character on the i-th of these lines $$$\mathbf{C_{i,j}}$$$ is
`Y`

if team members $$$i$$$ and $$$j$$$ know each other before the introduction
process starts, and `N`

otherwise. Then, there are $$$\mathbf{P}$$$ more lines; the $$$k$$$-th
of which contains a pair of integers $$$\mathbf{A_k}$$$ and
$$$\mathbf{B_k}$$$ each, representing the team member numbers of the $$$k$$$-th pair we
are interested in.

For each test case, output one line containing
`Case #$$$x$$$: $$$y_1\ y_2\ y_3 \cdots y_\mathbf{P}$$$`

,
where $$$x$$$ is the test case number (starting from 1) and
$$$y_i$$$ is $$$-1$$$ if team members $$$\mathbf{A_k}$$$
and $$$\mathbf{B_k}$$$ cannot get to know each other, or the shortest amount
of time (in minutes) since the process starts until they do.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

$$$\mathbf{C_{i,j}}$$$ is either uppercase `Y`

or uppercase
`N`

, for all $$$i, j$$$.

$$$\mathbf{C_{i,j}}$$$ = $$$\mathbf{C_{j,i}}$$$, for all $$$i, j$$$.

$$$\mathbf{C_{i,i}}$$$ = `Y`

, for all $$$i$$$.
(Team members know themselves.)

$$$1 \le \mathbf{A_k} \lt \mathbf{B_k} \le \mathbf{M} + \mathbf{N}$$$, for all $$$k$$$.

$$$(\mathbf{A_k}, \mathbf{B_k}) \neq (\mathbf{A_\ell}, \mathbf{B_\ell})$$$, for all $$$k ≠ \ell$$$.
(No pair of team members is asked about twice.)

Time limit: 20 seconds.

$$$1 \le \mathbf{M} \le 3$$$.

$$$1 \le \mathbf{N} \le 2$$$.

$$$1 \le \mathbf{P} \le 3$$$.

Time limit: 40 seconds.

$$$1 \le \mathbf{M} \le 50$$$.

$$$1 \le \mathbf{N} \le 50$$$.

$$$1 \le \mathbf{P} \le 100$$$.

Sample Input

3 2 2 3 YYYY YYNN YNYN YNNY 2 3 2 4 1 4 3 2 2 YYYNN YYNYN YNYNY NYNYN NNYNY 2 5 4 5 1 1 1 YN NY 1 2

Sample Output

Case #1: 1 1 0 Case #2: 2 3 Case #3: -1

In Sample Case #1, manager $$$1$$$ knows everybody else at the start, and there are no other pairs of people that know each other. Therefore, any pair that includes manager $$$1$$$ has $$$0$$$ as a result, since they know each other from the start. On the other hand, for any pair that does not include manager $$$1$$$, the two people do not know each other from the start, but can be introduced during the first time slot by manager $$$1$$$. Notice that the scenarios for the first two pairs considered independently.

In Sample Case #2, manager $$$2$$$ and non-manager $$$5$$$ do not know each other, nor do they know anyone who knows both of them, so the minimum time for them to be introduced is at least $$$2$$$ minutes. One way for them to be introduced after exactly 2 minutes is for manager $$$3$$$ to introduce manager $$$1$$$ and non-manager $$$5$$$ during the first time slot, after which manager $$$1$$$ can introduce manager $$$2$$$ and non-manager $$$5$$$ in the second time slot. For the second pair, we can start the same way to introduce manager $$$2$$$ and non-manager $$$5$$$ in 2 minutes and then, manager $$$2$$$ can introduce non-managers $$$4$$$ and $$$5$$$ in the third time slot, so $$$3$$$ minutes is an upper bound for introducing the pair of $$$4$$$ and $$$5$$$. It is impossible to do this quicker.

In Sample Case #3, neither person in the new team knows the other, so no introductions are possible.

Sample Input

1 5 1 1 YYNNNN YYYNNN NYYYNN NNYYYN NNNYYY NNNNYY 1 6

Sample Output

Case #1: 3

In this additional Sample Case, manager $$$2$$$ can introduce managers $$$1$$$ and $$$3$$$ in the first time slot, while at the same time manager $$$5$$$ can introduce manager $$$4$$$ and non-manager $$$6$$$. Then, manager $$$3$$$ can introduce managers $$$1$$$ and $$$4$$$ in the second time slot, and finally manager $$$4$$$ can introduce manager $$$1$$$ and non-manager $$$6$$$ in the third time slot.

Izabella and Olga are playing a game alternating turns. Izabella plays first. The game starts with all game pieces arranged in a single row. The pieces come in two colors: indigo and orange. During Izabella's turns, she must choose and remove an indigo piece that is either the leftmost or rightmost piece remaining. During Olga's turns, she must choose and remove an orange piece that is either the leftmost or rightmost piece remaining. If at any point one of the players does not have a legal move (possibly because there are no pieces remaining), that player loses the game, and the other player is awarded $$$1$$$ point plus $$$1$$$ additional point for each piece that remains on the board.

We use an uppercase letter `I`

to represent indigo pieces and
an uppercase letter `O`

to represent orange pieces. Suppose, for example, that they play with the following
starting board: `IOIOOOII`

.

On her first turn, Izabella can choose to remove either the leftmost or rightmost
pieces, as both are indigo. Suppose she chooses the leftmost. Then, the board
would become `OIOOOII`

. Then, Olga would have no choice but
to remove the new leftmost piece, as the rightmost piece is not orange, leaving
`IOOOII`

. Izabella can choose again, and this time she chooses the
rightmost piece, leaving `IOOOI`

for Olga's turn. At this point,
Olga has no valid move, so Izabella won. Since there are $$$5$$$ pieces remaining,
Izabella wins $$$1+5=6$$$ points in total.

Each player plays optimally trying to win and to maximize their own score. A player that cannot guarantee a win plays to minimize the opponent's score.

Given the starting board, can you find out who wins and what is their score?

The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ lines follow.
Each line represents a test case and contains a string $$$\mathbf{B}$$$ representing the status of the
board. The $$$i$$$-th character in $$$\mathbf{B}$$$ is `I`

if the $$$i$$$-th piece from
the left is indigo and `O`

if it is orange.

For each test case, output one line containing `Case #$$$x$$$: $$$y$$$ $$$z$$$`

,
where $$$x$$$ is the test case number (starting from 1), $$$y$$$ is the initial of
the winner (`I`

for Izabella or `O`

for Olga), and $$$z$$$ is
the score the winner gets.

Time limit: 20 seconds.

Memory limit: 1 GB.

$$$1 \le \mathbf{T} \le 100$$$.

Each character of $$$\mathbf{B}$$$ is either an uppercase letter `I`

or an uppercase letter
`O`

.

$$$2 \le$$$ the length of $$$\mathbf{B} \le 10$$$.

$$$2 \le$$$ the length of $$$\mathbf{B} \le 100$$$.

$$$2 \le$$$ the length of $$$\mathbf{B} \le 10^5$$$.

Sample Input

5 IOIOOOII OIIIIO IO IOIOIOI IOIOIOOIO

Sample Output

Case #1: I 8 Case #2: O 7 Case #3: O 1 Case #4: I 1 Case #5: O 6

In Sample Case #1, Izabella can do better than the example in the statement. If she starts by removing the rightmost piece, Olga has no possible moves and Izabella wins with $$$7$$$ pieces remaining. Izabella wins $$$1+7=8$$$ points in total.

In Sample Case #2, Izabella cannot even make her first move, so Olga wins!

In Sample Case #3, neither player has a choice on what to play, and Olga wins after all pieces are exhausted, so she gets only $$$1$$$ point.

In Sample Case #4, all pieces are exhausted at the end of the game too, but it is Izabella who comes out with the win.

One observation that helps us find a solution is: we will never need to give any pet more than $$$\mathbf{N}$$$ treats. So for each pet, we need to consider at most $$$\mathbf{N}$$$ options for treats, $$$1, 2, \dots, \mathbf{N}$$$. We can quickly verify that this observation is true with a simple argument. If there is a positive integer $$$X$$$ such that no pet receives $$$X$$$ and some pets receive $$$X+1$$$, then we can give all those pets $$$X$$$ instead, keep everything valid and reduce the total amount of treats.

For Test Set 1, limits are small enough for a brute force solution. For each pet, we can try all the numbers ($$$1, 2, \dots, \mathbf{N}$$$) of treats, and check if that assignment fulfills our criteria. Then we output the minimum total from among the valid assignments. There are $$$\mathbf{N}^\mathbf{N}$$$ possible assignments. For each assignment, we can check the validity criteria by checking that all pairs of pets satisfy the impartiality rule in $$$O(\mathbf{N}^2)$$$ time. This makes the overall time complexity $$$O(\mathbf{N}^{\mathbf{N}+2})$$$, which is sufficient for Test Set 1.

For Test Set 2, we need to find the solution faster.

All pets of the same size must get the same amount of treats, and any pet must get strictly more treats than all pets strictly smaller than it. That means that if we sort the pets by size (in non-decreasing order), the number of treats each pet must get is also sorted. Since we need to minimize the number of treats, we can start by giving $$$1$$$ treat to the smallest animal. Then, for every animal in the sorted list, we can give it:

- the same number of treats as the previous one, if it is the same size as the previous one.
- $$$1$$$ more treat than the previous one, if it is bigger.

By distributing treats like this, we are keeping the invariant that the assignment is optimal for the set of pets that have already received treats. When considering the next pet, we are giving the minimum amount possible. Therefore, we are giving the minimum number of treats whilst also fulfilling the condition.

The sorting of the pets takes $$$O(\mathbf{N} \log \mathbf{N})$$$ time, and the assigning of the treats can be done in $$$O(\mathbf{N})$$$ time. This makes the overall time complexity $$$O(\mathbf{N} \log \mathbf{N})$$$, which is sufficient to pass Test Set 2.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

It is given that a valid string must start with A.

For $$$\mathbf{N} = 1$$$, the only block $$$B_1$$$
should therefore start with a character greater than `A`

. To keep building
the alphabetically first valid string, we start $$$B_1$$$ with `B`

which is
just greater than `A`

. We keep on incrementing the character as we move
right to ensure that $$$B_1$$$ is strictly increasing. Notice that we will eventually end up
with a prefix of `BCDE..XYZ`

as $$$B_1$$$. As $$$\mathbf{L_i} \le 25$$$, we will never
run out of characters for this.

For $$$\mathbf{N} = 2$$$, we construct the first block $$$B_1$$$ using the process described for
$$$\mathbf{N} = 1$$$.
We now evaluate the possible ways to fill the strictly decreasing second block $$$B_2$$$.
We try to start $$$B_2$$$ with the smallest possible character to get the alphabetically
first string. This implies that $$$B_2$$$ will end with the smallest character in the alphabet
which is `A`

. So, we start filling $$$B_2$$$ from the end with `A`

and
move to the left, incrementing the character.

Let $$$b_1$$$ be the last character in $$$B_1$$$ and $$$b_2$$$ be the first character in
$$$B_2$$$.
If $$$b_1 \gt b_2$$$, then we will always get a valid string as it ensures that
$$$B_2$$$ is strictly decreasing. On the other hand if $$$b_1 \le b_2$$$, then the final
string is invalid. For example, if $$$\mathbf{L_1}=2$$$ and $$$\mathbf{L_2}=4$$$, the resulting string
from the above process will be `ABCDCBA`

which is invalid.

To ensure that $$$B_2$$$ is always strictly decreasing, we update $$$b_1$$$ with the
character just greater than $$$b_2$$$. This will guarantee that the string is valid and
alphabetically the first one. Again as $$$\mathbf{L_i} \le 25$$$, we will never run out of
characters while filling $$$B_2$$$. In the above example, `ABCDCBA`

now transforms
to a valid string `ABEDCBA`

.

We generalize the above solution for $$$\mathbf{N} \gt 2$$$.

If $$$\mathbf{N}$$$ is even, we can divide the blocks into $$$\mathbf{N}/2$$$ pairs as
|$$$\mathbf{L_1}$$$,$$$\mathbf{L_2}$$$|$$$\mathbf{L_3}$$$,$$$\mathbf{L_4}$$$|...|$$$\mathbf{L_{N-1}}$$$,$$$\mathbf{L_N}$$$| and solve the $$$\mathbf{N}/2$$$ pairs
independently using the same approach as for $$$\mathbf{N}=2$$$. We can do this as every such pair
of blocks will end with `A`

.

If $$$\mathbf{N}$$$ is odd, we solve for $$$\mathbf{N}-1$$$ blocks using the above approach and for the last block $$$\mathbf{L_N}$$$, we treat it as the case when $$$\mathbf{N}=1$$$.

The time complexity is $$$O(\mathbf{L_1} + \mathbf{L_2} + \cdots + \mathbf{L_N})$$$ for each test case.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

In the first Test Set, the number of people in a new team is so small that we can use brute force. Even in the worst case, we only have five people: three managers and two non-managers. Since an introduction ties up three people, at most one introduction can take place in each minute. Moreover, there are only $$$\binom{3}{1}\times\binom{4}{2}=18$$$ possible groups of an introducing manager plus two other people, and only some of these will meet the conditions needed for an introduction: the introducing manager must know the other two people, and the other two people must not know each other (or else there would be no point in introducing them).

We can use an exhaustive search to explore all ways of performing an introduction each minute until our target people are acquainted, or until we run out of valid introductions to make, and then return the smallest number of introductions we saw in a valid answer (or $$$-1$$$ if there is no answer). The bounds on the number of possible introductions and on the size of the answer (it cannot exceed $$$3$$$ in this test set) ensure that the space to explore is small, and so our solution will run very quickly.

To solve Test Set 2 we can model the problem as a graph. Every person in the team is a node, and we connect two different nodes with an edge if the represented people know each other when the team was formed. The key insight to solve this test set is to realize that an introduction changes the state from graph $$$G$$$ to a graph $$$H$$$ that is $$$G$$$ with one extra edge, and the extra edge directly connects two nodes that are connected in $$$G$$$ by a path of length $$$2$$$ with an intermediate node that is a manager. Let $$$D_G(v,w)$$$ be the distance in $$$G$$$ between nodes $$$v$$$ and $$$w$$$ considering just paths that only use managers as intermediate nodes. In what follows, when we say path or distance, we refer to those terms with the restriction of only using managers as intermediate nodes.

Following the reasoning in the previous paragraph,
$$$D_{G}(v,w)-1 \ge D_{H}(v,w)$$$ — that is, after an introduction,
the distance between two nodes decreases by at most $$$1$$$. Moreover, if
$$$D_{G}(v,w) \gt 1$$$ — that is, $$$v$$$ and $$$w$$$ do not know each other —
and there is a path of managers between them, there is always a way to make an introduction such
that the resulting $$$H$$$ has $$$D_{H}(v,w)=D_{G}(v,w)-1$$$. Let
`$$$[v = x_0, x_1, x_2, \dots, x_{D_{G}(v,w)-1}, x_{D_{G}(v,w)} = w]$$$`

be a minimum path that between $$$v$$$ and $$$w$$$ in $$$G$$$. Since $$$v$$$ and $$$w$$$ do not
know each other, $$$x_1$$$ is neither of them, and therefore
an intermediate step in the path, so $$$x_1$$$ is a manager.
If $$$x_1$$$ introduces $$$v = x_0$$$ and $$$x_2$$$, the
path `$$$[v = x_0, x_2, \dots, x_{D_{G}(v,w)-1}, x_{D_{G}(v,w)} = w]$$$`

of length $$$D_{G}(v,w)-1$$$ is formed in the resulting $$$H$$$, so
$$$D_{H}(v,w) = D_{G}(v,w)-1$$$.

The goal of the problem is to use introductions to reduce the distance between a given pair of nodes $$$v$$$ and $$$w$$$ to $$$1$$$ (the minimum possible distance). So, if we could only do one introduction at a time, the answer would be exactly $$$D_{G_0}(v,w)$$$ in the initial graph $$$G_0$$$. Since time considerations don't change whether it is possible for $$$v$$$ and $$$w$$$ to meet, we can already say that $$$v$$$ and $$$w$$$ can meet if and only if there is a path connecting them in the initial graph.

Let us now consider simultaneous introductions.
Let $$$G_0, G_1, \dots, G_k$$$ be a
list of graphs where $$$G_i$$$ models the state of the team at time $$$i$$$
in an optimal way to make $$$v$$$ and $$$w$$$ meet (meaning $$$k$$$ is the answer for this pair).
$$$G_0$$$ is the original team and $$$v$$$ and $$$w$$$ are connected directly by an
edge only in $$$G_k$$$. For convenience, let $$$D_i = D_{G_i}(v, w)$$$.
We can bound $$$D_{i + 1}$$$ in terms of $$$D_i$$$ as follows:
each edge $$$(x, y)$$$ on $$$G_{i + 1}$$$ either exists in $$$G_i$$$ or
comes from an introduction that happens between minutes $$$i$$$ and $$$i + 1$$$, meaning
there is a path of length $$$2$$$ $$$[x, m, y]$$$ in $$$G_i$$$ where $$$m$$$ is a manager.
Now fix $$$i$$$ and consider the path ```
$$$[v = x_0, x_1, \dots, x_{D_{i+1} - 1}, x_{D_{i+1}}
= w]$$$
```

between $$$v$$$ and $$$w$$$ in $$$G_{i + 1}$$$. Consecutive edges share
a person, so at most one of each pair can come from an introduction
and the other one must exist in $$$G_i$$$. This gives us a
bound $$$D_i \le D_{i+1} + \lceil(D_{i+1} / 2)\rceil$$$.
Let us show that this bound is tight and always reachable:
if we are at state $$$G_i$$$, and $$$D_i \gt 1$$$,
we can take a minimum path ```
$$$[v = y_0, y_1, \dots,
y_{D_{i} - 1}, y_{D_i} = w]$$$
```

between $$$v$$$ and $$$w$$$ in $$$G_i$$$ and have $$$y_{3j + 1}$$$
to introduce $$$y_{3j}$$$ and $$$y_{3j + 2}$$$ for each $$$j$$$ between
$$$0$$$ and $$$\lceil((D_i - 2) / 3)\rceil$$$. Those introductions at minute $$$i$$$
yield $$$D_{i + 1} = D_i - \lceil((D_i - 2) / 3)\rceil$$$ and
make exactly $$$\lceil(D_{i + 1})\rceil$$$ edges in $$$G_{i+1}$$$ come from an
introduction.

Given all the theory above, the answer for a given pair $$$v$$$ and $$$w$$$ for which $$$D_{G_0}(v, w)$$$ is undefined (that is, they are not connected) is impossible, and is otherwise $$$f(D_{G_0}(v, w))$$$ where $$$f(x)$$$ is the number of steps it takes for $$$x := x - \lceil((x - 1) / 3)\rceil$$$ to reach $$$x = 1$$$. Notice that it takes a logarithmic number of steps to reach $$$1$$$, so we can just calculate $$$f$$$ on demand, or we can memoize all the needed values (for $$$x$$$ between $$$1$$$ and $$$\mathbf{N}$$$). Most shortest-path algorithms can be modified slightly to calculate the distance $$$D_0$$$ considering only managers as intermediate nodes as above, but the simplest must be Floyd-Warshall. Floyd-Warshall computes the shortest paths between every pair of nodes by considering each possible intermediate node in its outermost loop. So, simply restricting that loop to iterate over managers (up to $$$\mathbf{M}$$$ instead of $$$\mathbf{M}$$$+$$$\mathbf{N}$$$) is enough to calculate, in time $$$O(\mathbf{M} \times (\mathbf{N}+\mathbf{M})^2)$$$, the distance $$$D_{G_0}$$$ for every pair of nodes. After running Floyd-Warshall and memoizing $$$f$$$ once, we can get the answer for every pair in constant time, so the algorithm takes $$$O(\mathbf{M} \times (\mathbf{M}+\mathbf{N})^2 + \mathbf{P})$$$ time overall.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

We can determine the outcome by playing through the game. For each turn: if the current player cannot move, the game is over. If the current player can only move on one side, eliminate the outermost piece from that side. Otherwise, the current player must choose between the leftmost piece and the rightmost piece.

Notice that this choice leads to a subgame where it is the other player's turn.
(E.g., the starting game `IOII`

where Izabella plays first can lead to either
`OII`

or `IOI`

where it is Olga's turn.) If there is only one piece
left in a subgame, the current player wins if they can take the piece and loses if they cannot.

For each turn, eliminate the piece that the current player takes. If the current player can choose between both sides, solve both subgames and choose the option that is more favorable to the current player. Continue until the game has finished.

If $$$N$$$ is the length of the input string $$$\mathbf{B}$$$, there are at most $$$N$$$ moves in the game, and there are at most $$$2$$$ options per-move, so this solution requires at most $$$O(2^N)$$$ time. Moreover, one player having a choice means the pieces at both ends are of their color. Since only one of them is removed, that means the next player cannot have more than one option. This means that at most half of the moves actually have $$$2$$$ options, meaning our algorithm's running time can be bounded more tightly by $$$O(2^{N/2})$$$.

The solution above can be optimized: use memoization/dynamic programming to avoid playing a subgame more than once. For each subgame, save its result and if you were to play it again, simply lookup the result instead of doing the recursion. Since there are less than $$$N^2$$$ subgames, this can yield a time complexity as low as $$$O(N^2)$$$. Implementations that manipulate strings, use them to represent the states or use inefficient ways to do the lookups can have higher time complexities, but the bounds of this test set are small enough that we can get away with doing it.

We can alternatively determine the outcome without subgames. For each turn: if the current player cannot move, the game is over. If the current player can only move on one side, eliminate the outermost piece from that side.

If the current player can move on either side, the end state of the game can be calculated as
follows: if the `I`

and `O`

pieces continue to alternate, the last player to take a piece wins
(with zero pieces left). Otherwise, the game will end once the players reach a pair of consecutive
identical pieces (`II`

or `OO`

).

Suppose the current player (who can move on either side) is Izabella. From each of the sides,
find the nearest pair of consecutive identical pieces (`II`

or `OO`

).
If one of those pairs is `II`

, Izabella can win by choosing the outermost piece
from that side (as Olga will not be able to move after Izabella takes one of the
`I`

s in `II`

). Note that if both sides have a `II`

pair,
choosing the side with the closer pair will maximize Izabella's score —
which can be calculated as the number of pieces between that `II`

and
the outermost piece on the other side, inclusive.

Alternatively, if the nearest pairs on both sides are `OO`

, Izabella will ultimately
lose the game. She can minimize Olga's score by eliminating the alternating
`I`

and `O`

pieces from both sides until reaching the `OO`

(s).
Then the score will be the number of pieces between the two occurrences of `OO`

s,
$$$1$$$ if there is only one `OO`

or $$$2$$$ if there are overlapping
`OO`

s, that is, `OOO`

, inclusive.

This solution takes linear time.

Test Data

We recommend that you practice debugging solutions without looking at the test data.