Timofey and Docker

The whole problem is secretly not about Docker. Thank god, no YAML involved.

We only care about the final number of occurrences of docker. If exactly $x$ occurrences appear, then the number of happy attendees is fixed. So the plan is:

1. Find which values of $x$ make the maximum number of attendees happy.
2. Among those values, find the cheapest one to force.

The crucial string fact

The word docker has no non-empty border:

• prefix length $1$: d, suffix length $1$: r
• prefix length $2$: do, suffix length $2$: er
• and so on; none match.

So two occurrences of docker cannot overlap. If two starts were less than $6$ apart, the overlap would force a prefix of docker to equal a suffix of docker, which never happens.

Therefore the maximum possible number of occurrences is

$M = \left\lfloor \frac{|s|}{6} \right\rfloor.$

Every occurrence is basically a length-$6$ block.

Which occurrence counts are worth targeting?

For every attendee range $[l_i, r_i]$, clip it to $[l_i, \min(r_i, M)]$. If it becomes empty, that attendee can never be satisfied.

Use a difference array over counts $0,1,\dots,M$ to compute happy[x], the number of attendees satisfied by exactly $x$ occurrences. Let

$best = \max_x happy[x].$

Only counts with happy[x] = best matter.

If best = 0, that is fine: every count is equally good, so doing nothing is optimal. The general logic below naturally handles this.

Current occurrences and decreasing the count

Let cur be the number of existing occurrences in the original string. Since occurrences do not overlap, they are disjoint blocks.

For any target $x \le cur$, the answer is exactly

$cur - x.$

Lower bound: one character change can destroy at most one existing occurrence, because existing occurrences are disjoint.

Upper bound: change one carefully chosen character inside each occurrence you want to destroy. With 26 letters, you can avoid accidentally creating a new docker nearby. So yes, one change per killed occurrence is enough.

So for all optimal target counts $x \le cur$, we can just try cur - x.

Increasing the count

Now suppose we need $k > cur$ occurrences.

For every possible start position $i$, define

$cost_i = \#\{j : s_{i+j} \ne docker_j\}, \quad 0 \le j < 6.$

This is the number of edits needed to make the block starting at $i$ become docker.

Now the problem becomes:

Choose exactly $k$ non-overlapping length-$6$ blocks with minimum total cost.

This is a weighted interval DP. The dumb DP with dimension chosen blocks is too slow, because $|s|$ is up to $5 \cdot 10^5$.

So we use the classic penalty trick.

Penalty DP

Pretend every chosen block has an extra penalty $p$. Usually $p \le 0$, so this is more like a discount. For a fixed $p$, compute the minimum value of

$real\_cost + p \cdot blocks.$

At the same time, store how many blocks were chosen. If two states have equal modified cost, prefer the one with more blocks.

The DP over prefixes is simple:

• skip current character: move from $i$ to $i+1$
• take a docker block starting at $i$: move from $i$ to $i+6$, paying $cost_i + p$

So:

$dp[i+1] = \min(dp[i+1], dp[i])$

$dp[i+6] = \min(dp[i+6], dp[i] + cost_i + p).$

Store a pair (modified_cost, -block_count), so normal lexicographic minimum automatically prefers lower cost, then more blocks.

As $p$ increases, blocks become less attractive, so the chosen block count never increases. That lets us binary search the largest $p$ such that the DP still chooses at least $k$ blocks.

Once we have such a penalty, if the DP result is

$value = real\_cost + p \cdot chosen,$

then the minimum real cost for exactly $k$ blocks is

$value - p \cdot k.$

This is the Aliens trick. It looks suspicious the first time, but it is just pricing one block until the optimal solution sits at the count we want. Competitive programming: where coupons become geometry, because apparently we enjoy pain.

Why only the smallest optimal target above cur?

For $k > cur$, the minimum cost to create exactly $k$ occurrences is nondecreasing in $k$: from any valid set of $k+1$ blocks, removing one block leaves a valid set of $k$ blocks with no larger cost.

So among all optimal target counts greater than cur, the smallest one is cheapest. We scan target counts in increasing order; the first optimal count above cur is the only one we need to run the penalty DP for.

Algorithm

For each test case:

1. Let $M = \lfloor |s|/6 \rfloor$.
2. Build happy[0..M] with a difference array over attendee ranges.
3. Compute diff[i], the mismatch cost to make s[i..i+5] equal docker.
4. Count current occurrences cur, where diff[i] = 0.
5. Let mxHappy be the maximum value in happy.
6. Scan all counts $x = 0 \ldots M$ with happy[x] = mxHappy:
   • if $x \le cur$, candidate answer is cur - x
   • otherwise, remember the first such $x$ as k and stop scanning upward
7. If such k exists, compute the minimum cost for exactly k blocks using penalty DP + binary search.
8. Output the minimum candidate answer.

Complexity

For each penalty value, the DP is $O(|s|)$. The binary search uses about 27 iterations, because the penalty range is just a large integer range.

Total complexity:

$O((|s| + n) + |s| \log C)$

per test case, with $C \approx 10^8$.

Across all tests, this is easily fine for $5 \cdot 10^5$ total string length. No Docker daemon required.