Fractal Expansion#13044

Fractal Expansion (Editorial)

Solution

Every string that can appear during the process is a prefix of $t$ .

Let $d p [x]$ be the minimum cost needed to obtain the prefix of $t$ of length $x$ .

Initially,

d p [0] = 0.

dp[0]=0.

There are two possible transitions.

Appending one character

Suppose the current prefix has length $x$ .

Appending the next character makes its length equal to $x + 1$ x+1, and the cost of this operation is $x + 1$ x+1.

Therefore,

d p [x + 1] = min (d p [x + 1], d p [x] + x + 1) .

dp[x+1] = \min(dp[x+1],dp[x]+x+1).

Applying the transformation

Suppose the current string is

s = t_{1} t_{2} \dots t_{x} .

s=t_1t_2\dots t_x.

Let

L_{x} = ∣ f (s) ∣.

L_x=|f(s)|.

Every character A produces two characters, while every character B produces one character.

Therefore,

L_{x} = x + # A (t_{1} t_{2} \dots t_{x}) .

L_x=x+\#A(t_1t_2\dots t_x).

After applying the operation, the new string becomes

s + f (s),

s+f(s),

so its length becomes

x + L_{x} .

x+L_x.

The operation is valid exactly when

t_{x + 1} t_{x + 2} \dots t_{x + L_{x}} = f (t_{1} t_{2} \dots t_{x}) .

t_{x+1}t_{x+2}\dots t_{x+L_x} = f(t_1t_2\dots t_x).

Now construct

U = f (t) .

U=f(t).

Since the transformation is applied independently to every character,

f (t_{1} t_{2} \dots t_{x})

f(t_1t_2\dots t_x)

is exactly the prefix of $U$ of length $L_{x}$ L_x.

Thus, we only need to check whether

t_{x + 1} t_{x + 2} \dots t_{x + L_{x}} = U_{1} U_{2} \dots U_{L_{x}} .

t_{x+1}t_{x+2}\dots t_{x+L_x} = U_1U_2\dots U_{L_x}.

This is a longest common prefix query between $U$ and the suffix of $t$ starting from position $x + 1$ x+1.

Construct the string

U + # + t,

U+\#+t,

where # is a character different from A and B, and calculate its Z-function.

The Z-value corresponding to position $x + 1$ x+1 in $t$ gives the length of the common prefix between $U$ and

t_{x + 1} t_{x + 2} \dots .

t_{x+1}t_{x+2}\dots.

Therefore, the transformation is possible exactly when

x + L_{x} \leq n

x+L_x\le n

and the corresponding Z-value is at least $L_{x}$ L_x.

Then we can perform the transition

d p [x + L_{x}] = min (d p [x + L_{x}], d p [x] + c) .

dp[x+L_x] = \min(dp[x+L_x],dp[x]+c).

The answer is $d p [n]$ .

Correctness

Every reachable string is a prefix of $t$ , so it is enough to store only its length.

From a prefix of length $x$ , there are exactly two possible operations: append one character or apply the transformation.

The first DP transition handles the append operation.

For the second operation, the Z-function checks exactly whether $f (t_{1} t_{2} \dots t_{x})$ f(t_1t_2\dots t_x) appears immediately after the current prefix.

Therefore, every valid transition is considered and no invalid transition is added.

Hence, $d p [x]$ is the minimum possible cost of obtaining the prefix of length $x$ , and $d p [n]$ is the required answer.

Complexity

The string $U$ has length at most $2 n$ .

Building $U$ , calculating prefix counts, and calculating the Z-function all take $O (n)$ time.

Every DP state has at most two transitions.

Therefore, the total complexity is

O (n)

time and

O (n)

memory.

d p [0] = 0.

x + 1

x + 1

d p [x + 1] = min (d p [x + 1], d p [x] + x + 1) .

s = t_{1} t_{2} \dots t_{x} .

L_{x} = ∣ f (s) ∣.

L_{x} = x + # A (t_{1} t_{2} \dots t_{x}) .

s + f (s),

x + L_{x} .

t_{x + 1} t_{x + 2} \dots t_{x + L_{x}} = f (t_{1} t_{2} \dots t_{x}) .

U = f (t) .

f (t_{1} t_{2} \dots t_{x})

L_{x}

t_{x + 1} t_{x + 2} \dots t_{x + L_{x}} = U_{1} U_{2} \dots U_{L_{x}} .

x + 1

U + # + t,

x + 1

t_{x + 1} t_{x + 2} \dots .

x + L_{x} \leq n

L_{x}

d p [x + L_{x}] = min (d p [x + L_{x}], d p [x] + c) .

f (t_{1} t_{2} \dots t_{x})