Official

F - ARC Stamp Editorial by evima

Table of contents

Section 1 explains the fundamental viewpoint to deal with the problem: to see it backward.

Section 2 derives the key idea to the problem: decomposition of the string \(T\).

Section 3 presents the solution to the problem with dynamic programming.

Section 4 summarizes the solution, and Section 5 provides a sample implementation (C++). If you are in a hurry, go to Section 4.


1. Introduction: see it backward

Consider the following problem.

We have a string of \(S\) of length \(N\), which is initially \(S\) = ***...**. Determine whether it is possible to repeat the operation below to make \(S\) equal to a string \(T\) (consisting of A, R, C).

Operation: Choose three consecutive characters in \(S\) and replace them with ARC.

(Modification of CPSCO2019 Session3 Problem D - Decode RGB Sequence)

Consider the reverse version of the operation: replace ARC with arbitrary three characters. By representing this arbitrary character by ?, the problem becomes the following.

We have a string of \(S\) of length \(T\). Determine whether it is possible to repeat the operation below to make \(T\) the string ???...??.

Operation: Choose three consecutive characters in \(T\) that are one of the following: ARC, AR?, A?C, ?RC, A??, ?R?, ??C, ???. Then, replace them with ???.

Here, doing an operation does not “make a possible operation impossible”. Instead, it just “unlocks” new operations. Thus, if we repeat the operation as many times as possible and get ???...??, the answer is Yes; if A, R, or C remains somewhere, the answer is No.

We can use this backward approach also to the original problem, where the setting is quite similar.


2-1. From what kind of string \(S\) can we make \(T\)?

First, let us consider a specific case: from what kind of string \(S\) can we make \(T\) = ARARCCC in one, two, or three operations?

As we did in Section 1, we see the process backward.


In one operation

The operation just before getting ARARCCC could only be to change the \(3\)-rd, \(4\)-th, \(5\)-th characters to ARC.

This could be done if the string was AR???CC (? stands for an arbitrary character which is A, R, or C).


In two operations

The operation just before getting AR???CC could be one of the three options below.

  • Change the \(1\)-st, \(2\)-nd, \(3\)-rd characters to ARC, which could be done if the string was ?????CC.
  • Change the \(3\)-rd, \(4\)-th, \(5\)-th characters to ARC, which could be done if the string was AR???CC.
  • Change the \(4\)-th, \(5\)-th, \(6\)-th characters to ARC, which could be done if the string was AR????C.

Thus, we can make the string \(T\) in two operations when \(S\) is ?????CC or AR????C.


In three operations

Similarly to the above, we can make the string \(T\) in three operations when \(S\) is ??????C or AR?????.


The figure below describes this process, where blue segments represent the positions changed to ARC.

Intuitively speaking, we make the string \(S\) by “dominating” the string \(T\) with ?, starting at positions with ARC.

Here are some examples.

  • We need three operations to make ARARCCC from AR?????, because it takes three steps to dominate: ARARCCC → AR???CC → AR????C → AR?????.
  • We need four operations to make AARCRARC from ????????, because it takes four steps to dominate: AARCRARC → A???RARC → A???R??? → ????R??? → ????????.


2-2. How to dominate it with “?”?

Here is what we write above: ‘Intuitively speaking, we make the string \(S\) by “dominating” the string \(T\) with ?, starting at positions with ARC.’ Let us sort out this mechanism of domination.

  • There is only one way to create domination from nothing: ARC → ???.
  • There are two ways to expand a dominated part to the left:
    • A??...?? → ???...?? (dominate the A to the left)
    • AR??...?? → ????...??(dominate the AR to the left)
  • There are two ways to expand a dominated part to the right:
    • A??...?? → ???...?? (dominate the C to the right)
    • AR??...?? → ????...??(dominate the RC to the right)
  • It is also possible to connect two dominated parts:
    • ??...??R??...?? → ??...?????...?? (dominate the C in the middle)

The reason why we have six ways to expand domination is that while there are eight patterns ARC, AR?, A?C, ?RC, A??, ?R?, ??C, ??? that can be changed to ???, ??? → ??? is a meaningless change, and A?C never appears in the string.


2-3. Decomposition of \(T\)

Let us revisit the case \(T\) = ARARCCC again. There are many orders we can dominate \(T\) with ?, such as:

  • ARARCCC → AR???CC → ?????CC → ??????C → ???????
  • ARARCCC → AR???CC → AR????C → AR????? → ???????

However, in one step, only the fixed segments on \(T\) ― between [ and ] in [AR][ARC][C][C] ― can be dominated. The cases above can be seen as:

  • [AR][ARC][C][C] → [AR][???][C][C] → [??][???][C][C] → [??][???][?][C] → [??][???][?][?]
  • [AR][ARC][C][C] → [AR][???][C][C] → [AR][???][?][C] → [AR][???][?][?] → [??][???][?][?]

Let us see some other examples.

  • \(T\) = ARCRCCRARC: can be decomposed into [ARC][RC][C][R][ARC].
  • \(T\) = RARCCRRARC: can be decomposed into [R][ARC][C][RR][ARC]. (Since the leftmost R and the middle RR cannot be dominated, let us represent it as [X][ARC][C][X][ARC].)
  • \(T\) = AARARCRARRAC: can be decomposed into [A][AR][ARC][RARRAC] = [A][AR][ARC][X].
  • \(T\) = ARCARCARC: can be decomposed into [ARC][ARC][ARC]. (However, since the dominations of [ARC]s do not interfere with each other, let us put [X]s in between to represent it as [ARC][X][ARC][X][ARC] for easier implementation.)
  • \(T\) = CARCCAARCA: can be decomposed into [C][ARC][C][A][ARC][A] = [X][ARC][C][X][A][ARC][X].

Actually, for a general string \(T\), there is a unique decomposition representing segments that can be dominated in one step. This decomposition can be found in \(O(|T|)\) time as the process of dominating the \(T\) as much as possible.

Then, we can simplify the domination in a step to the following.

  • Dominate [ARC].
  • Dominate [A] or [AR] to the left of a dominated part.
  • Dominate [C] or [RC] to the right of a dominated part.
  • Dominate [R] between dominated parts.
  • [X] cannot be dominated.

Therefore, the following important property holds, where a clause is [ARC], [A], [AR], [C], [RC] or [X] in the decomposition.

Property: the number of minimum operations needed to perform the domination equals the number of clauses to dominate.

Thus, counting the strings \(S\) that can be made in \(K\) or fewer operations can be done by counting the strings that can be made by dominating \(K\) or fewer clauses. This idea leads to the solution with dynamic programming stated in Section 3.


3. Solution with dynamic programming (DP)

Based on the idea of decomposing the string \(T\) we obtained in Step 2, let us design a solution to the problem with DP.

Let \(v_1, v_2, \dots, v_M\) be the decomposition of \(T\) from left to right, where \(M\) is the number of clauses. Here, each \(v_i\) is [ARC], [A], [AR], [C], [RC], or [X].

Now, consider deciding, for each clause, whether to dominate it with ? and what the original string (in \(S\)) will be if we dominate it, one by one from left to right. Then, we need the following three values \((pos, conq, flag)\) as the state of the DP.

  • \(pos\): the clause up to which we have processed (representing that \(v_1, v_2, \dots, v_{pos}\) are already processed)
  • \(conq\): the number of clauses already dominated
  • \(flag\): a boolean value representing whether both Clauses \(pos\) and \(pos+1\) are to be dominated (\(1\) if dominating both, \(0\) if not dominating either)

The setting of the third variable \(flag\) depends on implementation. In this editorial, we record whether we dominate both \(v_{pos}\) and \(v_{pos+1}\) to simply the implementation.

Then, when choosing the “original string” in the clause \(v_{pos+1}\) from the state \((pos, conq, flag)\), the transition happens as follows. (A bit complicated, but you will see it if you sort it out.)

  • When \(v_{pos+1}\) = [ARC]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate)
    • \((pos, conq, 0)\) → \((pos+1, conq+1, 1)\): \(27\) ways (dominate from \(v_{pos+1}\); the original three characters can be freely chosen)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 0)\): \(27\) ways (dominate up to \(v_{pos+1}\); the original three characters can be freely chosen)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 1)\): \(27\) ways (dominate \(v_{pos+1}\); the original three characters can be freely chosen)
    • \((pos, conq, 0)\) → \((pos+1, conq+1, 0)\): \(26\) ways (dominate just \(v_{pos+1}\), do not dominate the clauses around it; the original three characters can be anything other than ARC)
  • When \(v_{pos+1}\) = [A]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate)
    • \((pos, conq, 0)\) → \((pos+1, conq+1, 1)\): \(2\) ways (dominate from this clause; this operation will not be in vain if A is changed to R or C)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 1)\): \(3\) ways (dominate this clause; the original character can be freely chosen)
  • When \(v_{pos+1}\) = [AR]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate)
    • \((pos, conq, 0)\) → \((pos+1, conq+1, 1)\): \(8\) ways (dominate from this clause; this operation will not be in vain if AR is changed to something else)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 1)\): \(9\) ways (dominate this clause; the original two characters can be freely chosen)
  • When \(v_{pos+1}\) = [C]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 0)\): \(2\) ways (dominate up to this clause; this operation will not be in vain if C is changed to A or R)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 1)\): \(3\) ways (dominate this clause; the original character can be freely chosen)
  • When \(v_{pos+1}\) = [RC]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 0)\): \(8\) ways (dominate from this clause; this operation will not be in vain if RC is changed to something else)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 1)\): \(9\) ways (dominate this clause; the original two characters can be freely chosen)
  • When \(v_{pos+1}\) = [R]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate)
    • \((pos, conq, 1)\) → \((pos+1, conq+1, 1)\): \(2\) ways (dominate this clause; this operation will not be in vain if R is changed to A or C)
  • When \(v_{pos+1}\) = [X]
    • \((pos, conq, 0)\) → \((pos+1, conq, 0)\): \(1\) way (do not dominate; there is no other choice)

We store in \(dp[pos][conq][flag]\) the number of strings \(S\) (prefixes of length \(|v_1| + |v_2| + \cdots + |v_{pos}|\), to be exact) that lead to the state \((pos, conq, flag)\).

As the initial state, we set \(dp[0][0][0] = 1\), and follow the transitions above to sequencially find \(dp[pos][conq][flag]\). In the end, \(dp[M][conq][0]\) represents the number of strings \(S\) such that the minimum number of operations needed is \(conq\). (The transitions do not allow futile operations, and each possible string is counted exactly once.) Thus, the answer is \(dp[M][0][0] + dp[M][1][0] + \cdots + dp[M][K][0]\).

Since the number of states is \(O(MK)\), the total complexity of the solution is \(O(MK)\).


4. Summary

In short, we can solve the problem as follows.

  • See the operations backward and rephrase the problem into counting the strings \(S\) that can be obtained from the string \(T\) in \(K\) or fewer operations.
    • For example, when \(T\) = ARARCCC, there are \(27\) strings that can be obtained in one operation (AR???CC), and \(297\) strings that can be obtained in two operations (AR????C or AR????C).
    • As seen here, we see each operation as expanding the region “dominated” by ?.
  • Let us call a string of the form [A or AR]...[A or AR][ARC][C or RC]...[C or RC] a subsection. Then, \(T\) can be uniquely decomposed in the form [unchangable part][subsection][R or unchangable part][subsection][R or unchangable part]...[subsection][unchangable part].
    • Let us call a part between [ and ] a clause.
    • For example, \(T\) = ARARCCC can be decomposed into the clauses [AR][ARC][C][C].
  • Then, one operation corresponds to dominating one clause.
    • That is, the minimum number of operations equals the number of clauses that must be dominated.
  • After decomposing \(T\) into clauses, we sequentially find \(dp[pos][conq][flag]\): the number of possible strings \(S\) when the first \(pos\) clauses have been processed, \(conq\) clauses are dominated so far, and the boolean value representing whether both Clauses \(pos\) and \(pos+1\) are to be dominated is \(flag\).
  • This DP takes \(O(|T| \cdot K)\) time.

Therefore, the problem can be solved in the total complexity \(O(|T| \cdot K)\), or \(O(|T| \cdot \min(|T|, K))\) because when \(K \geq |T|\), we can regard it as \(K = |T|\) without changing the result.


5. Sample Implementation (C++)

https://atcoder.jp/contests/arc131/submissions/27711292

posted:
last update: