TopCoder Statistics - Problem Statement

Problem Statement

The unicorn is an exotic chess piece similar to the knight. The difference is that while the knight moves two cells in one direction and one in the other direction, the unicorn moves more than two cells in one direction and more than one in the other direction.

More precisely, each unicorn move looks as follows:

pick up the unicorn;
pick one of the four basic directions, and move the unicorn more than two cells in that direction;
pick one of the two basic directions that are orthogonal to the previous one, and move the unicorn more than one cell in that direction;
put down the unicorn.

We have a chessboard that has R rows times C columns. Each cell of the chessboard contains one of the first L letters of the alphabet. To keep the input small, the content of the cells is randomly generated using the method described below.

You are given the ints R, C, and L described above, an int seed used to generate the letters in the cells, and a String word. You want to trace the String word by taking a unicorn, placing it onto a cell containing the first letter of word, making a valid move that takes it onto a cell that contains the second letter, from there making another move to the third letter, and so on. Return the number of ways in which this can be done, modulo 1,000,000,007.

The content of the cells is generated using the following pseudocode:

x = seed;
d = (65535 div L)+1;
for (int r=0; r&lt;R; r++)
  for (int c=0; c&lt;C; c++) {
    x = (x * 25173 + 13849) modulo 65536;
    chessboard[r][c] = character with ASCII code (65+(x div d));
  }

Definition

Class:: Unicorn
Method:: countWays
Parameters:: int, int, int, int, String
Returns:: int
Method signature:: int countWays(int R, int C, int L, int seed, String word)
(be sure your method is public)

Notes

The path of the unicorn can contain the same cell multiple times.
In the pseudocode, "A div B" represents the integer part of A/B. For example, 14 div 5 = 2 and 20 div 4 = 5.
The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.

Constraints

R will be between 1 and 300, inclusive.
C will be between 1 and 300, inclusive.
L will be between 1 and 26, inclusive.
seed will be between 0 and 65,535, inclusive.
word will contain between 1 and 50 characters, inclusive.
Each character in word will be an uppercase letter ('A'-'Z').

Examples

3

4

2

47

"AB"

Returns: 2

When generating the input we will compute d=32768, and then generate the content of the cells. The variable x will have the following values, in order: 17332, 39133, 37242, 14235, 656, 12265, 20598, 6471, 51372, 44853, 44210, and 45363. The generated chessboard looks as follows: ABBA AAAA BBBB There are only two ways a unicorn can trace the word "AB" on this chessboard. It has to start in one of the two top corners, and then jump into the opposite corner.
5

5

2

47

"CD"

Returns: 0

No letter C on this board.
4

4

1

42

"AA"

Returns: 20

The unicorn can start in one of the four corner cells (and then has three possible jumps), or at one of the 8 cells that share a side with a corner cell (and then only have one possible jump). This gives us 4*3 + 8*1 = 20 ways to trace the word.
4

4

1

42

"AAAAA"

Returns: 172
1

1

5

54321

"ABCDE"

Returns: 0

The board is too small. No word longer than one character can be traced as there is no way to make a valid move.
8

8

26

226

"TOPCODER"

Returns: 1

The board looks as follows: AILFPSPF DZIOMYCE QOODZARU YVOTLTRX LSRIGANL LCIUUSNF IWVXKTDE OVPPNXRD If we number the rows and columns starting from 0, with (0,0) being the upper left corner cell, the only valid path of the unicorn is (6,5)-(2,1)-(7,3)-(1,6)-(7,0)-(2,3)-(6,7)-(4,2).
300

300

26

47

"QWERTYUIOPLKJHGFDSAZXCVBNMQWERTYUIOPLKJHGFDSAZXXVB"

Returns: 814990822
3

3

3

214

"B"

Returns: 4
20

20

2

47

"AAAAA"

Returns: 373977054

Do not forget about the modulo; the actual number of paths can be huge.
300

300

26

4747

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 488664626
300

300

1

35612

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

1

10

2434

"ABCCBC"

Returns: 0
1

300

10

21414

"BAACACDFG"

Returns: 0
3

4

2

47

"ABABABABABABABABABABABABABABABABABABABABABABABABAB"

Returns: 2
297

294

3

152

"AABACABACAACACABACACABACBACBACBABCABCBABAACA"

Returns: 500171210
125

14

23

28045

"WMLWJUKDORUVOTUFOWKUUSTT"

Returns: 640540645
9

84

8

38564

"AFF"

Returns: 413060
210

150

3

9689

"BAACCACCABAAAAAABBBACBCCBC"

Returns: 680124160
35

55

23

22805

"HPIHGAUSRIDKJIAGTGDIFRGRQSOVENVRAVL"

Returns: 351146909
69

208

15

48892

"FOKAOOGIMDCEGNDFILAIBKLKNBBFIFKOOIKBJFH"

Returns: 118183924
206

289

18

19554

"PCJKHDHKNHQODECKDEJADLQIPNNNLBNJLMDNQGECECEDH"

Returns: 222491368
224

229

18

63837

"PPMKEAGRINQLCERNFERAGBRGEMNADIFD"

Returns: 332027111
63

2

7

6668

"FEFEBGDBAEAGCDCBBFGGCFGEBCFFEAEG"

Returns: 0
15

6

21

10236

"AKUGBFROGFGDKFALLUSEJIKASM"

Returns: 0
103

199

19

8066

"DODHJGFQSQPLILGKKMOSDLLEOHLMHRJBR"

Returns: 534125035
23

217

26

37289

"MVJCOINKPQRTRUZZPZTUXKAPYYZGXZAJIXEUMGQTHWLIROLWQ"

Returns: 301664651
223

191

8

4211

"HFBFBGBDDCCADGECBEEGCBBDEDHGFBGHGCHHAHFDEDCHCHCH"

Returns: 164842583
268

220

21

47045

"JGFLTNGAFEBROEAKCBARFAOKLHEJLOJHHIKRMGUHA"

Returns: 487076206
47

73

19

17724

"NCQNGQKOMOFHFNOPLFFFFPBHQGL"

Returns: 293810085
114

18

19

57015

"DOSOCOQIPJAOQMIDOOELQOBANNNEDDBDEPQAPAFOAHE"

Returns: 881377220
53

284

25

8332

"TJQBELUDBJPTVTGIGJQPIPHNVIVWJEPKEFSCCWYBQQFBLK"

Returns: 354594720
224

300

14

30946

"IFINFICNCKMCEDICGLKFNDHNFEGIJFAHGKGHGBC"

Returns: 251962695
95

17

1

21328

"V"

Returns: 0
241

242

23

8331

"AFOITCTWRKWCBVOAVFCBVFCDHVEUWCDPQI"

Returns: 690558827
3

176

19

4897

"KMOKGRCCMPHANINPGKHPNPARPCCPAOCFNKDFJOCNDJQSHCCFH"

Returns: 861718693
106

155

24

42503

"XXQFURTBDARAAKUXEIQJLDVFESAK"

Returns: 178609739
235

160

14

7409

"KKAIJNNGJDCCJLDJDMNEKLNILHJJ"

Returns: 522110740
127

134

23

25083

"EFSPJSFKEOTWDRBHSNLSBILLKEVPACDGEAFKBG"

Returns: 539739581
193

212

1

30848

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 958555856
211

228

12

21336

"DGCHCGIDKCBJAILDKABEEIHHLCEEJLACAJDDKD"

Returns: 695484280
51

210

17

14192

"BOPHFLIJLAKPAFNQJBLMDCQDJHKFI"

Returns: 12086742
22

296

8

33030

"ABCCHCGBGACDBFHHDBBHFGBACC"

Returns: 59910238
87

22

10

7076

"DJDJIGHHBFFJJIFHHDIAIAHHFGEHCEDJIFCJH"

Returns: 166324138
111

4

15

55125

"CBMCKLHAIBJHLBBAJGOIIHLHFAMLLOAGHFHKMDOAIFFMBBD"

Returns: 377276319
61

29

17

24206

"IAJAHFMNIGPGLPOMCNCQMFAENIMNHCPGBEINJDLAHDDFLPHIMB"

Returns: 557997309
11

129

1

59954

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 150370884
33

44

21

27368

"FNGCBJKPKGMHKTELHUUUMPNAUNIOUOBSQO"

Returns: 214460220
119

210

3

43424

"CACCBACBACBBCBACABBABABBBBCA"

Returns: 366456386
214

44

11

34739

"HIHBAHCFIHBAIHIGEIFHAEGKG"

Returns: 969342859
212

180

9

3324

"EFGBDAHGBBBIICGDBCFFICABDIGFBABFEB"

Returns: 280169015
188

36

23

63370

"BJEFSGBGNHPSSNHKGWKBTLORSASJWWTSINOVDHUB"

Returns: 485241611
152

73

20

53139

"FANAPIANFHNIFAMSFIRDALMD"

Returns: 48919101
178

207

14

18038

"FHGHBJDKICBBCFELFBCCCMNNNNLLLIJCDIA"

Returns: 712446435
157

168

16

26276

"L"

Returns: 1630
95

275

17

4776

"BBIALFOODIEJGAHEGCEDLGPGLDGGGBKBGOQKJM"

Returns: 877946352
222

35

6

21920

"CBDFEBFBDFCEAFDCEEBEFDDABCCADDDCB"

Returns: 766550773
275

87

2

2951

"BABAABABBABABABBABABBBBBBBA"

Returns: 963575496
171

231

10

5428

"XSSTPACKJKCMOIPABHYIACIAOYCJLAFOCEQUJSZGPJAZZPJ"

Returns: 0
6

152

10

33218

"ACDFIGGBCGBJCJEHAADBGGBAEDABFEBAABBGHJGADJJFDJIJ"

Returns: 691737914
84

2

18

3516

"GPCJLJDJOJLLRPNQCINQGGLRMEAAEOMNKBRACD"

Returns: 0
99

40

3

19082

"BBCACCCBBAABBCAAABCACBCCAACBCBCAA"

Returns: 569637787
213

151

15

48449

"IOCDIDMENNAMBHOIGODDDCIMLMCDNFJLJDEBGD"

Returns: 490095859
65

52

17

53871

"ABHOKDKAKIAGDCFNDDPHGLJBFCIJNOPIFEQBIBCDDLLKJE"

Returns: 348468764
246

4

16

43323

"WHSWYBJSWOSOYVCZGYLDGRVACCARVKOKYZCJDWUWLJVGXE"

Returns: 0
219

191

2

38892

"B"

Returns: 21012
114

5

7

32821

"FDEADDACAGEEGFDCCDFFEFGGCACGCECFBBGGBCBGFA"

Returns: 638835127
2

266

1

20379

"AAA"

Returns: 0
40

223

16

49282

"MFALOEPPDONEHFIGOKIKNLHNLLJ"

Returns: 428058376
255

234

25

31763

"SEFRBXLPLHTXFASWSHIJEVMSA"

Returns: 952894581
233

156

21

15939

"CCTUNNECCBRRGRCKAIPUBTTJOOIGMCQEJGGRKPEN"

Returns: 215287459
105

217

22

19211

"STEAATCFMJFQGGGMPNFAOGLRSUVIVNTDVEGVQJRJTMBI"

Returns: 739434495
144

123

6

3749

"CAECEDFBCBCCEAFEFABFBFEFABFAFCDECBDADBEFDCAEDEA"

Returns: 971517439
9

82

13

49525

"GFCHFHMIFLIHFGLDGKBDFGJDBLG"

Returns: 401188863
197

131

15

30519

"WQDOUPAIXOQRPOWSYFSJJQZESKQPPYSIKLXZ"

Returns: 0
222

218

12

17076

"EIFHKDIAKDFLHELEJFAECHELDLCBKHBGFBD"

Returns: 393840750
172

86

15

63667

"EMBNDBLNDLNNEKAABNMENLAAAHBBCBD"

Returns: 356437033
148

210

1

33688

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 12274854
81

130

23

25588

"SJIGLMMTJDLFOGRDVGAWMISENJCVHEGDDAFGSTM"

Returns: 664386174
216

156

11

26448

"JFJJFAAJFGJKCBCDFKGJBEIHKFCED"

Returns: 525116527
183

145

22

39905

"HGV"

Returns: 537638338
156

4

8

44652

"HFEFGFHHCCGBECHCBFBAEDABFGCABFHAADGGC"

Returns: 649522516
278

111

6

10938

"BFCFEBEBACACEECCEBFEDECCBBABDBFCCFCBEAABABACCAAEC"

Returns: 50731872
26

271

10

41614

"CCDAGEJIFGHECABEECJHECJGDHBBJHAAEEBDEJHJJABIF"

Returns: 3864239
245

167

1

50896

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 953990655
144

121

3

29064

"BBCACBABCACCBAABCCACAACABCBBCBCABABBBCBBABB"

Returns: 182028855
300

300

3

12345

"ABABAAABABAABCABCAAABCCACABACCAABACBABACACABACAAB"

Returns: 786883102
20

20

2

49

"AAAAA"

Returns: 837978474
300

300

26

234

"ABCPDSOWEOSOCXODSOEWPSDOASDOSDOZXCOWAEOSDAODSAO"

Returns: 719500530
300

300

2

2342

"ABABAAABABBAABBBBABABABBABBBABBABABBABABBABABBBABA"

Returns: 283522936
300

300

1

47

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

2

47

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 445391449
300

300

3

2134

"ABCBAABBCAABCBAABBCAABCBAABBCAABCBAABBCAABCBAABBCA"

Returns: 537697376
300

300

1

1

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

2

42

"ABABABABABAABABBABABABABABABABAABABBABABAABABBABAB"

Returns: 768820158
300

300

2

123

"ABABABABABABABABABABABABABABABABABABABABABABABABAB"

Returns: 326008507
300

300

1

0

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

26

100

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 401636837
232

123

26

226

"TOPCODER"

Returns: 935748138
299

299

26

9999

"DAREMY"

Returns: 826948420
300

300

2

0

"ABABABABABABABABABABABABABABABABABABABABABABABABAB"

Returns: 281249122
300

300

26

7

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 446215026
300

300

26

65000

"AMBLGNVJSRTIJGRDGVCSHGEBKDTIDKTJFNYJFLGKKGIWU"

Returns: 220623087
300

300

3

1015

"ABCACBBACBCACABCBAAABCACBBACBCACABCBABBBABABBAAACC"

Returns: 427757232
300

300

26

523

"ABFDSFASDFADFSDFASDFASF"

Returns: 559051743
300

300

2

10

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 659948255
300

300

1

12345

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

34234

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

22

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

2

23

"ABAAABBABAABAAABBABAABAAABBABAABAAABBABAABAAABBABA"

Returns: 578796717
300

300

2

47

"AAABBBBAABBBAAAABABABABBBBAAABBBBAABBBAAAABABABABB"

Returns: 185328352
300

300

26

234

"FIWORIGFNGTPNOKSXNBZUFEWOGTOYITNJKVNDCQPEOJNMSAJ"

Returns: 808425795
300

300

26

10007

"ABCHIJKLMNOPQRSTUVWXYZOPQRSTUVDEFGHIJKLMNABCDEFGWX"

Returns: 222392399
300

300

26

226

"ABCDEFGHIJKLMNOPQRSTUVWXYABCDEFGHIJKLMNOPQRSTUVWXY"

Returns: 721662974
300

300

1

5

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

2

47

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 421440691
300

300

2

23

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 609554907
300

300

26

65535

"AAAAABBBBBCCCCCZZZZZXXXXXCCCCCFFFFFRRRRRTTTTTGGGGG"

Returns: 925047332
300

300

1

300

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 797806534
300

300

2

1235

"ABABABABABABABABABABABABABABABABABABABABABABABABAB"

Returns: 532222533
300

300

26

47

"ABCDEFGHIJKLMMMMMMMMMOUTRFDGHJIUYTREDFGHJKIOMNBVCX"

Returns: 591856012
300

300

2

47

"AAAAABBBBBBBBBBAAAAAAA"

Returns: 320012450
300

300

1

10

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

653

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

2

1

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 698080016
300

300

2

47

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"

Returns: 317211214
300

300

2

222

"ABABABABABABABABABABABABABABABABABABABABABABABABAB"

Returns: 16339227
300

300

26

2

"FDSAAAAAKFDHSAKLDFHDSAKGNFHKLGASDGFDAGAQWFGUHAAAAA"

Returns: 702126508
300

300

2

27

"AAAAAAAAAAAAAAA"

Returns: 567543686
300

300

2

47

"AAAAABBBBB"

Returns: 16682137
300

300

3

7648

"AAAAAABAAAC"

Returns: 302768154
300

300

2

47

"AAAAA"

Returns: 450003361
300

300

1

1312

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

26

12345

"KAKAASDFQWERZXCVPOIUAAAAKKKKYUIOTHMKQEPOIUYTREWQ"

Returns: 662701903
300

300

26

325

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 682929454
300

300

1

26

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

2

1231

"AAABBBAAABAAABBBAAABAAABBBAAABAAABBBAAABAAABBBAAAB"

Returns: 523210126
300

300

26

43896

"TOPCODERFOREVER"

Returns: 714484037
300

300

10

2

"ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ"

Returns: 480525478
300

300

1

438

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

5

37617

"ABAADEADABCDABECCCEBABEBCABBABAECBCBCAAABBBBBBBBBB"

Returns: 305920360
300

300

5

47

"ABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDEABCDE"

Returns: 301936484
300

300

1

226

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

43

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

42

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

4

27

"ABCD"

Returns: 575191091
300

299

2

47

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 393610615
300

300

1

8191

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

57

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

7667

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

26

65535

"AJSDFJAFDJASFJGJASGDJGJGDFASKDGASKGDKAJSHDKJHASDJK"

Returns: 69017844
300

300

1

31000

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945
300

300

1

32516

"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

Returns: 861343945

Statistics

Problem Statement for "Unicorn"

Problem Statement

Definition

Notes

Constraints

Examples