Connection Status:
Competition Arena > CharacterBoard2

CharacterBoard2

SRM 576 · 2012-12-13 · by gojira_tc

SRM 576 · 2012-12-13 · by gojira_tc · Brute Force, Simple Search, Iteration, String Manipulation
Class Name: CharacterBoard2
Return Type: int
Method Name: countGenerators
Arg Types: (vector<string>, int, int, int)
Problem Statement

Problem Statement

Manao has a matrix X with 10,000 rows and W columns. He likes to fill it with characters; he even has developed an algorithm for this task. First, he chooses a string S consisting of at most W lowercase letters. The string S is called the generator. Then, he applies the algorithm described by the following pseudocode: 
cur := 0
for i := 0 to 9999
  for j := 0 to W - 1
    X[i][j] := S.charAt(cur)
    cur := (cur + 1) mod length(S)

Manao has recently found a matrix X in his notepad. He wonders whether it was generated using the above algorithm. You are given:
  • a String[] fragment that contains a rectangular submatrix of X,
  • the int W: the width of X,
  • and two ints i0 and j0: the coordinates of the upper left corner of your submatrix within X.
In other words, for all valid i, j we have fragment[i][j] = X[i + i0][j + j0]. Count how many different generators Manao could have used to create a matrix X that contains the fragment you were given. Return this number modulo 1,000,000,009.

Constraints

  • fragment will contain N elements, where N is between 1 and 10, inclusive.
  • Each element of fragment will be M characters long, where M is between 1 and 10, inclusive.
  • Each element of fragment will consist of lowercase letters ('a'-'z') only.
  • W will be between M and 10,000, inclusive.
  • i0 will be between 0 and 10,000 - N, inclusive.
  • j0 will be between 0 and W - M, inclusive.
Examples
0)
{"dea",
 "abc"}
7
1
1
Returns: 1

Manao has a matrix with 10000 rows and 7 columns. We know that it looks as follows: ??????? ?dea??? ?abc??? ??????? ... The only string of length at most 7 which could generate such matrix is "abcde".

1)
{"xyxxy"}
6
1
0
Returns: 28

The given information is: ?????? xyxxy? ?????? ... The corresponding generator could be "xyx", "yxyxx", or a string of form "xyxxy?", where '?' stands for any lowercase letter.

2)
{"gogogo",
 "jijiji",
 "rarara"}
6
0
0
Returns: 0

No generator could create this matrix using the given algorithm.

3)
{"abababacac",
 "aaacacacbb",
 "ccabababab"}
882
10
62
Returns: 361706985
4)
{"asjkffqw",
 "basjkffq",
 "qbasjkff",
 "qqbasjkf"}
9031
9024
1959
Returns: 173947456

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

Coding Area

Language: C++17 · define a public class CharacterBoard2 with a public method int countGenerators(vector<string> fragment, int W, int i0, int j0) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous