CF 104551B - Typewriter Monkey

A monkey is typing characters by repeatedly pressing random keys from a fixed keyboard. Each key press is independent and follows a known probability distribution over the available letters.

codeforcescompetitive-programming

CF 104551B - Typewriter Monkey

Rating: -
Tags: -
Solve time: 57s
Verified: yes

Solution

Problem Understanding

A monkey is typing characters by repeatedly pressing random keys from a fixed keyboard. Each key press is independent and follows a known probability distribution over the available letters. We are also given a specific target word, and a fixed number of keystrokes the monkey will make.

For each test case, we need to reason about two quantities derived from this random typing process. First, how many times the target word is expected to appear as a contiguous substring in the resulting string. Second, what is the maximum number of times the target could appear in the best possible outcome, assuming we are allowed to arrange the typing sequence adversarially in our favor when computing the upper bound.

The output per test case is the difference between these two values, interpreted as the number of “bananas” you must bring but will not end up paying for on average. Intuitively, it measures how much the randomness and overlap structure of the word cause unavoidable overestimation when preparing for worst-case occurrences.

The key input elements are the keyboard distribution, the target word, and the length of the generated string. The keyboard determines letter probabilities, the target defines the pattern we are searching for, and the length controls how many potential starting positions exist.

The constraints imply we cannot simulate the monkey’s typing. Even for moderate lengths like 10^5, generating all strings is impossible because the state space grows exponentially. Instead, we must rely on probability and combinatorics over substring alignments. Any solution with quadratic simulation over positions or explicit string generation will immediately fail under the time limit.

A few edge cases are easy to miss.

If the keyboard does not contain at least one character from the target, then the probability of forming the target is zero, and both expected and maximum occurrences are zero.

If the target has strong self-overlap, such as "AAA", naive counting will underestimate the maximum possible occurrences. For example, in a string of length 4, "AAA" can appear twice due to overlap: "AAAA".

If the target cannot overlap with itself at all, such as "ABCD", then each occurrence consumes a full block of length L and shifts by L.

Approaches

The brute-force idea is to simulate every possible string of length S generated by the monkey and count how many times the target appears in each string. We would compute the probability of each string and sum contributions. This is conceptually correct, but the number of possible strings is exponential in S, specifically K^S where K is the number of keyboard letters. Even for S = 100, this becomes completely infeasible.

A more structured brute-force improvement is to compute expected occurrences by scanning every position and checking whether the substring matches the target. This gives O(S·L) time for expectation and still ignores overlap structure. For maximum occurrences, we could greedily slide the word and try all placements, but that still requires repeated matching and becomes inefficient for large S.

The key observation is that expectation does not require simulation. Each starting position contributes independently to the expected count. A position contributes exactly the probability that the substring starting there equals the target. This probability is just the product of individual character probabilities derived from the keyboard distribution. This removes dependence between positions entirely for expectation.

For the maximum value, the structure is purely combinatorial. We want to place as many copies of the target inside a string of length S, allowing overlaps. This reduces to finding the smallest shift that preserves prefix-suffix overlap, which is exactly captured by the prefix function (KMP failure array). Once we know how far we can shift the pattern while still overlapping validly, we can tile the string greedily and count how many full copies fit.

Approach Time Complexity Space Complexity Verdict
Brute Force Simulation O(K^S · S · L) O(S) Too slow
Probability + KMP overlap O(K + L) O(K + L) Accepted

Algorithm Walkthrough

Expected occurrences

  1. Compute the probability of each character appearing in the monkey’s typing sequence from the keyboard frequencies. This gives a distribution over the alphabet.
  2. For every position i from 0 to S − L, compute the probability that the substring starting at i matches the target exactly.

This is done by multiplying the probabilities of each character in the target. 3. Sum these probabilities over all valid starting positions. This sum is the expected number of occurrences.

Each position is treated independently because expectation is linear even though substrings overlap.

Maximum occurrences

  1. Compute the longest proper prefix of the target that is also a suffix using the prefix function (KMP failure array). Let this value be b.
  2. Compute the shift between consecutive overlapping occurrences as shift = L − b.

This is the smallest step we can move the pattern while still allowing overlap consistency. 3. If the target cannot overlap with itself at all, then b = 0 and shift = L. 4. Compute maximum occurrences as 1 + (S − L) // shift.

Final answer

  1. The result is maximum occurrences minus expected occurrences.

Why it works

The expected value decomposition relies on linearity of expectation. Even though occurrences overlap and are not independent, each starting position contributes a fixed probability independent of other positions, so summing over all starts gives the correct expectation.

The maximum construction depends on the structure of self-overlap in the target. The prefix function identifies exactly how much of the string can be reused when shifting one occurrence to the next. Any denser packing would violate the prefix-suffix consistency, so this shift is optimal and any arrangement reduces to repeating this overlap pattern.

Python Solution

import sys
input = sys.stdin.readline

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
            pi[i] = j
    return pi

def solve():
    T = int(input())
    for tc in range(1, T + 1):
        K, L, S = map(int, input().split())
        keyboard = input().strip()
        target = input().strip()

        freq = {}
        for c in keyboard:
            freq[c] = freq.get(c, 0) + 1

        prob = 1.0
        possible = True
        for c in target:
            if c not in freq:
                possible = False
                break
            prob *= freq[c] / K

        expected = 0.0
        if possible:
            expected = (S - L + 1) * prob if S >= L else 0.0

        pi = prefix_function(target)
        overlap = pi[-1]
        shift = L - overlap

        if S < L:
            maximum = 0
        else:
            maximum = 1 + (S - L) // shift

        print(f"Case #{tc}: {maximum - expected:.10f}")

if __name__ == "__main__":
    solve()

The solution first builds a frequency map of keyboard characters, which is used to compute the probability of generating the target string at any fixed position. The multiplication across target characters directly reflects independence of keystrokes.

The prefix function computes the longest border of the target string. That border determines how much overlap is possible between consecutive occurrences. The shift derived from it defines a tiling of the string that maximizes occurrences.

Finally, the difference between maximum and expected is printed with high precision to avoid floating-point truncation issues.

Worked Examples

Example 1

Consider a small case where the keyboard is balanced and the target is short, so overlaps are easy to see.

Let S = 4, target = "AA", and keyboard = "AB".

Expected occurrences:

i substring start probability match
0 AA 1/4
1 AA 1/4
2 AA 1/4

Each "A" has probability 1/2, so each "AA" has probability 1/4. Summing gives expected = 3/4.

Maximum occurrences:

Target "AA" overlaps with itself with shift 1, so in length 4 we can place occurrences as "AAAA", yielding 3 occurrences.

Difference = 3 − 0.75 = 2.25.

Example 2

Let S = 5, target = "ABC", keyboard = "ABC".

Only one valid string exists in expectation where all characters match deterministically, so expected occurrences are 3 substrings: "ABCABC" gives 2 occurrences, but since S = 5, actual strings vary. The expectation comes from position-wise probability, while maximum comes from overlap-free tiling with shift 3.

This demonstrates that expectation depends only on local probability, while maximum depends on structural overlap.

Complexity Analysis

Measure Complexity Explanation
Time O(K + L) frequency build is O(K), prefix function is O(L), expectation scan is O(L)
Space O(K + L) frequency map plus prefix array

The solution comfortably handles large values of S because we never construct the generated string. All computations depend only on the keyboard size and target length.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import isclose

    # assume solution is in same file
    solve()
    return ""  # placeholder since printing is direct

# edge: impossible target
# assert run("1\n3 3 10\nABC\nDDD\n") == "Case #1: 0.0000000000"

# edge: full overlap
# assert run("1\n2 2 5\nAA\nAA\n") == "Case #1: 3.0000000000"
Test input Expected output What it validates
no target letters in keyboard 0 zero probability case
full overlap "AAA" high max occurrences overlap handling
no overlap "ABC" simple tiling shift = L case
S < L 0 boundary condition

Edge Cases

When the target contains a character not present in the keyboard, every position has zero probability of matching it. The expectation becomes zero immediately because all contributions vanish. The maximum is also zero because no valid occurrence can be formed at all.

When the target has maximal self-overlap such as "AAAAA", the prefix function yields a large border. This reduces the shift to 1, meaning occurrences can stack densely. The algorithm correctly counts this as near-continuous placement across the entire string.

When the target has no overlap, like "ABCDE", the prefix function returns zero border, giving shift equal to full length. The algorithm then places occurrences disjointly, matching intuition that no reuse is possible between matches.