CCC '19 J5 - Rule of Three

View as PDF

Submit solution

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

Problem types
Canadian Computing Competition: 2019 Stage 1, Junior #5

A substitution rule describes how to take a sequence of symbols and convert it into a different sequence of symbols. For example, ABA \to 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 \to AB
  2. AB \to BB
  3. B \to AA

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

\displaystyle \textbf{AB} \to \textbf{B}B \to AA\textbf{B} \to AA\textbf{AA} \to 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, followed by another sequence of A's and B's. Both sequences will have between one and five symbols.

The next line will contain 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.

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

\displaystyle \textbf{AB} \to B\textbf{B} \to B\textbf{AA} \to \textbf{B}AB \to AAAB.


  • 0
    leoliu93233  commented on Nov. 5, 2023, 3:30 a.m.

    this question is so hard that i did the funny

  • 1
    jo3_l  commented on Sept. 19, 2021, 6:18 a.m.

    Could an editorial be opened for this problem?

    • 2
      Marshmellon  commented on Sept. 20, 2021, 12:40 a.m.

      The chances of that are pretty small, since only 3 people have AC'd the problem with the strong data. However, you already have a 15/30 submission which would get you AC on the original cemc data.

  • 1
    danielwilson682  commented on Feb. 16, 2021, 7:42 p.m.


    I'm new to this site, I use Python 3, and I'm trying to solve this problem, which has been getting on my case for a while now. XD. Is there anybody who could share their code so that I can understand how you solved it?


    P.S. I'm not trying to cheat here. I only want to know how you guys solved this problem.

    • 3
      Subway_Man  commented on April 6, 2021, 1:50 a.m. edited

      I would recommend trying to get 15/30 - that would allow you to pass this problem on the contest it was given. DMOJ has modified the test cases, so this problem is a lot harder. Only 3 people on the entire website have gotten 30/30. The general solution most people seem to use is a brute force with some optimisations.

      • 1
        Badmode  commented on June 15, 2021, 5:14 p.m. edited

        It's actually 5 people, go to all submissions and change the filter submissions status to "Accepted." There seems to be a glitch where best submissions only shows 3 AC.

        Edit: Look at comments below.

        • 7
          Plasmatic  commented on June 16, 2021, 5:32 a.m.

          This is not a bug. Users who attempt to plagiarize or otherwise cheat the points system will be unlisted from most of the ranking boards on DMOJ.

        • 2
          thomas__li  commented on June 15, 2021, 5:28 p.m. edited

          It's because the other 2 users are unlisted.

  • 2
    kevinlu1248  commented on Feb. 11, 2020, 4:02 p.m. edited

    If you brute force isn't it still \mathcal{O}(3^S) \sim 10^7?

    • 4
      j9292002  commented on Feb. 12, 2020, 12:29 a.m. edit 2

      hello kevin! it is more than that I think example: bbbbbbbbbbb. more that one way to do b->aa

  • 22
    Neon  commented on Feb. 2, 2020, 9:35 p.m.

    Why is the time limit so low? Isn't it supposed to be at least 2.0s?

  • 43
    const  commented on Dec. 17, 2019, 10:11 p.m.

    This question really should be worth much more points.

  • 16
    yeerk16  commented on Dec. 16, 2019, 6:16 p.m.

    I should stop working on this one (it's putting me behind in other tasks, oops!), but I can't get in under the 1 second time limit. My solutions all use recursion-based DFS. I started with Python3, converted to C, added memoization (hashing based on number of steps and the current string), added bidirectional/meet-in-the-middle search... each of these steps has helped, but not sufficiently. Now I'm stuck. Can anyone help? I've learned a lot with this problem, and I'm grateful for that, but it would be nice to see how to solve this more quickly so that I can fully move on.

    • 0
      DynamicSquid  commented on Jan. 17, 2021, 3:55 a.m.

      Could you please clarify what you mean by "hashing based on number of steps and the current string"? I'm also trying to speed up my solution with memoization, but I can't get it to work

      • 0
        Badmode  commented on June 5, 2021, 6:07 p.m.

        What I did to memoize was based on the hash of the current string and the number of steps it took to get there.

    • 14
      souradeepsahaf9466880b1d54979  commented on Dec. 17, 2019, 5:40 a.m.

      I'm trying this problem for around 6 months now, and did all the things you've done but still can't pass the last test case. One other thing I did is calculating the number of times you can apply a rule by creating systems of equations and solving them. You might try that out as well, but I don't think it'll be very useful.

  • 14
    YidiChen  commented on Nov. 5, 2019, 10:13 p.m. edit 3

    Just 8 score...

    • 4
      Neon  commented on Feb. 2, 2020, 9:33 p.m.

      use memoization, you shud be able to get 15/30

  • 28
    pblpbl  commented on Oct. 4, 2019, 9:15 p.m.

    How does one not TLE?