Floccinaucinihilipilification

Which pairs contribute to the answer?

Call the initially present viruses original viruses and those inserted during changes new viruses. Pairs of original viruses contribute equally to both extinction risks. The answer is therefore the sum of similarities over unordered pairs containing at least one new virus. All terms are nonnegative, so subtracting the original-only risk from the full risk gives the required absolute difference.

Store the strings in a trie. Each non-root node represents a nonempty prefix. The number of nodes on the common prefix of two strings equals their similarity. If a node's subtree contains $o$ original viruses and $a$ new viruses, its contribution is

$$F(o,a)=oa+\binom{a}{2}=oa+\cfrac{a(a-1)}{2}.$$

Summing $F$ over all non-root nodes gives the answer. A pair of new viruses must be counted only once. Distinct virus types with identical structures still count separately.

Subtask 1: direct simulation

After each change, explicitly modify every string and append the new viruses. Compute the longest common prefix for every pair containing a new virus. With $B=\sum x_i$ and $H=\max |V_i|+M$, the time complexity is and the memory complexity is . This subtask has and .

Subtask 2: one change

Let the only change be $cx$. If $k$ original structures start with $c$ after the mutation, the answer is $kx+\binom{x}{2}$. An original string qualifies exactly when it did not initially start with , or when its first two characters were both . A one-character string becomes empty. Writing , the solution takes time.

Subtask 3: only the letter A

Every new virus always has an empty or one-character structure. If there are $o$ nonempty original structures and $a$ nonempty new structures, the answer is $F(o,a)$.

An original string of length $\ell$ first becomes empty after $\ell$ changes. It then alternates between empty and length one. Count initial lengths and maintain, separately for both parities, the number of originals that have already reached zero. At time $i$, an original structure is empty exactly when its initial length is at most $i$ and has the same parity as $i$.

A virus inserted at time $t$ has length one at time $i$ exactly when $i-t$ is even. Maintain insertion totals by time parity as well. The total time complexity is $O(L+M)$, with $O$ memory.

Moving the root of the trie

Let $r$ be the current root and $c$ the mutation letter. Let $s$ be the $c$ child of $r$, creating an empty node if that child does not exist.

Moving the root from $r$ to $s$ removes the leading $c$ from strings that previously started with $c$. Every other string gains a leading $c$, represented by an edge from the new root to the old root. The old root's former $c$ child link must be removed.

Inserting $x$ new viruses after the mutation is equivalent to inserting $x$ empty strings at the old root before moving it. These strings become exactly the one-character string $c$ after the move. Inserting empty strings at the root does not immediately change the answer because no nonempty prefix is added.

After adding these $x$ new viruses to the old root's count, let $(o_s,a_s)$ be the counts at $s$ before the move. Subtract because becomes the root. Subtract the counts of from those of , and add the contribution of the resulting to the answer. Set the counts of to the total counts. The move itself leaves all other subtree counts unchanged.

Merging subtrees with equal edge labels

If $s$ already had a $c$ child $u$, it conflicts with $r$, which is also becoming a $c$ child. The node $u$ represents strings that originally started with $cc$. The two subtrees now represent the same prefix and must be merged.

When merging nodes $v,w$, subtract their previous contributions, combine their counts, and add the contribution of the combined node. A child present on only one side can be transferred unchanged. Children present on both sides under the same letter must also be merged.

The reference solution uses an explicit work stack, avoiding recursive calls even for very long strings. Each merge makes one node unreachable. Thus, the total number of node merges is bounded by the number of nodes ever created.

The initial trie has at most $L+1$ nodes, and each change creates at most one node. For alphabet size $K$, the total time and memory complexities are both $O(K(L+M))$. The full task has $K=26$, giving linear complexity in .

Subtasks 4, 5, and 6

For subtasks 4 and 5, specialize the same algorithm to child arrays of sizes $2$ and $6$. Their time and memory complexities are $O(2(L+M))$ and $O(6(L+M))$, respectively.

In subtask 6, exactly one new virus is inserted throughout the entire process. Thus $a \leq 1$ always holds and $\binom{a}{2}=0$. A trie implementation using only the contribution $oa$ solves this subtask in time and memory. The full solution must retain the term for pairs of new viruses.

Integer bounds

At most $B=9M \leq 2\,700\,000$ new viruses are inserted. A virus inserted at step $i$ has final length at most $M-i+1$. Original-new pairs contribute at most . New-new pairs are maximized by inserting viruses at every step and increasing the length of every existing new structure at each later step. Their maximum contribution is .

The exact maximum answer is therefore $9M(M+1)(N+3M+1)/2$, which is $486\,002\,025\,001\,350\,000$ at the full bounds. This is attained by using identical initial strings of one letter and alternating mutations of two other letters while inserting viruses each time. The intermediate product before division is also at most , within signed -bit range.

There are at most $3\,000\,000$ viruses, and a single-node contribution is at most $4\,454\,998\,650\,000$. The original-only risk is at most $((N-1)L+MN(N-1))/2$. Even if both risks are computed separately, the full risk is at most , safely within signed -bit range. The reference solution directly accumulates prefix contributions and does not evaluate these large polynomial formulas.

At most $2\,300\,002$ nodes are allocated, including the dummy node. The reference solution maintains a bitmask of existing child letters and visits only those children while merging. Each full-task node uses $116$ bytes, so the node array occupies about $255$ MiB. Reserving the maximum capacity in advance avoids holding both old and new arrays during reallocation. The merge work stack and input buffers also fit within the $1\,024$ MiB limit.

The validator checks bounds before accumulating an integer. Intermediate seed-hash values are below $2.82\cdot 10^{11}$, random-state multiplication is below $1.04\cdot 10^{14}$, and the generator's product $N(N+1)$ is at most . No judging component requires an integer type wider than bits.

Solution written by GPT6