Connection Status:
Competition Arena > StringSequences

StringSequences

TCO12 Wildcard Round · 2012-03-27 · by rng_58

TCO12 Wildcard Round · 2012-03-27 · by rng_58 · Dynamic Programming, Math
Class Name: StringSequences
Return Type: int
Method Name: countSequences
Arg Types: (string, string)
Problem Statement

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Farmer John and Eel Brus are studying string theory at the university. One day John found a very interesting sequence of strings s1, s2, ..., sK and told Brus about it. Brus only remembers the following information:
  • Each string in the sequence consists of lowercase letters only.
  • The sequence starts with A. In other words, s1 = A.
  • The sequence ends with B. In other words, sK = B.
  • For each i between 1 and K-1, inclusive, si+1 can be obtained by inserting one lowercase letter to si. For example, if s1 is "tco", valid options for s2 include "qtco", "trco", "tcso", and "tcot", but not "xco", "txoc", or "srm".
Return the number of sequences that match Brus's information, modulo 1,000,000,007. Brus's memory is always correct, so it is guaranteed that at least one such sequence exists.

Constraints

  • A will contain between 1 and 49 characters, inclusive.
  • Each character in A will be a lowercase letter ('a'-'z').
  • B will contain between N+1 and 50 characters, inclusive, where N is the number of characters in A.
  • Each character in B will be a lowercase letter ('a'-'z').
  • There will be at least one sequence that matches Brus's information in the problem statement.
Examples
0)
"oxoxox"
"foxfoxfox"
Returns: 6

The following six sequences match Brus's information: "oxoxox", "foxoxox", "foxfoxox", "foxfoxfox" "oxoxox", "foxoxox", "foxoxfox", "foxfoxfox" "oxoxox", "oxfoxox", "foxfoxox", "foxfoxfox" "oxoxox", "oxfoxox", "oxfoxfox", "foxfoxfox" "oxoxox", "oxoxfox", "foxoxfox", "foxfoxfox" "oxoxox", "oxoxfox", "oxfoxfox", "foxfoxfox"

1)
"aaaaa"
"aaaaaaaa"
Returns: 1

Only the sequence "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa" matches Brus's information.

2)
"tco"
"tcotco"
Returns: 18
3)
"a"
"alnfrlrealjnsliejsraijneroav"
Returns: 135925750
4)
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
Returns: 1

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StringSequences with a public method int countSequences(string A, string B) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous