CCC '19 J5 - Rule of Three

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem types

A substitution rule describes how to take a sequence of symbols and convert it into a different sequence of symbols. For example, ABA \rightarrow BBB, is a substitution rule which means that ABA can be replaced with BBB. Using this rule, the sequence A\textbf{ABA}A would be transformed into the sequence ABBBA (the substituted symbols are in bold).

In this task, you will be given three substitution rules, a starting sequence of symbols and a final sequence of symbols. You are to use the substitution rules to convert the starting sequence into the final sequence, using a specified number of substitutions.

For example, if the three substitution rules were:

  1. AA \rightarrow AB
  2. AB \rightarrow BB
  3. B \rightarrow AA

we could convert the sequence AB into AAAB in 4 steps, by the following substitutions:

\textbf{AB} \rightarrow \textbf{B}B \rightarrow AA\textbf{B} \rightarrow AA\textbf{AA} \rightarrow AAAB,

where the symbols to be replaced are shown in bold. More specifically, from the initial sequence AB, substitute rule 2 starting at position 1, to get the result BB. From BB, substitute rule 3, starting at position 1, to get the result AAB. From AAB, substitute rule 3, starting at position 3, to get the result AAAA. From AAAA, substitute rule 1, starting at position 3, to get the result AAAB, which is the final sequence.

Input Specification

The first three lines will contain the substitution rules. Each substitution rule will be a sequence of A's and B's, followed by a space following by another sequence of A's and B's. Both sequences will have between one and five symbols.

The next line contains three space separated values, S, I and F. The value S (1 \le S \le 15) is an integer specifying the number of steps that must be used, and the values I (the initial sequence) and F (the final sequence) are sequences of A's and B's, where there are at least one and at most 5 symbols in I and at least one and at most 50 symbols in F.

For 7 of the 15 marks available, S \le 6.

For an additional 7 of the 15 available marks, S \le 12.

Due to the official test data being weak, an additional subtask worth 15 marks has been added that consists of tests constructed to break solutions that are incorrect but AC on the official test data. Data are provided by d and xiaowuc1.

Output Specification

The output will be S lines long and describes the substitutions in order.

Line i of the output will contain three space-separated values, R_i, P_i, and W_i:

  • R_i is the substitution rule number (either 1, 2 or 3) that will be used.
  • P_i is the starting position index of where the substitution rule will be applied in the sequence. Notice that the string is 1-indexed (i.e., the first character of the string is at index 1).
  • W_i is the sequence that results from this substitution. Specifically, W_i is the sequence of symbols that results by applying substitution rule R_i starting at position P_i from the previous sequence of symbols, W_{i-1}, where we define W_0 to be the initial sequence I. Note that W_S = F, the final sequence.

There will always be at least one sequence of S substitutions that will convert I into F. If there is more than one possible sequence of substitutions, any valid sequence will be accepted.

Sample Input


Possible Output for Sample Input

2 1 BB
3 1 AAB
3 3 AAAA
1 3 AAAB

Explanation of Output for Sample Input

This is the example outlined in the problem description. Note that the following is another possible valid substitution sequence:

2 1 BB
3 2 BAA
1 2 BAB
3 1 AAAB

Specifically, showing the substitutions in bold, we get \textbf{AB} \rightarrow B\textbf{B} \rightarrow B\textbf{AA} \rightarrow \textbf{B}AB \rightarrow AAAB.


  • 1
    souradeepsahaf9466880b1d54979  commented on May 9, 2019, 6:37 p.m.

    Ideas anyone? I'm using recursion and getting TLE. Thanks!

  • -2
    edmondyu01  commented on May 9, 2019, 10:40 a.m.

    Elegant how they changed the point value to 15 from 35.

    • 4
      juho  commented on May 10, 2019, 9:38 p.m. edited

      It used to be 50 points at one point, lol.

  • -4
    TonyXer  commented on March 29, 2019, 10:38 a.m. edited

    Can someone tell me when people can get an AC with an incorrect answer? (i.e. you get AC but you don't get full marks)

    • 2
      Rimuru  commented on March 29, 2019, 5:28 p.m.

      For example, when your code is correct for some answers.

      • 0
        TonyXer  commented on March 30, 2019, 9:28 p.m.

        But wouldn't that be a WA? And why am I getting downvotes...

        • 1
          31501357  commented on April 26, 2019, 4:51 p.m.

          There could be a mistake in your code. However, the original test data would never be able to exploit your mistake, and that's how you could get away with an incorrect answer.