AlternativePiles | Topcoder Archive

Problem Statement

Slow loris Guts is playing with N cards, numbered 0 through N-1. Each card has one of four colors: red, green, blue, or white. You are given the card colors as the String C. For each i, character i of C is one of 'R' (red), 'G' (green), 'B' (blue), and 'W' (white).

You are also given an int M.

Guts wants to color each white card red, green, or blue in such a way that the number of cards not colored blue is exactly 2*D*M for some non-negative integer D. Additionally, there must be exactly M sequences of integers S_0 through S_{M-1} with the following properties:

For each i, the sequence S_i contains exactly 2*D integers, each of them between 0 and N-1, inclusive.
For each i, the sequence S_i is strictly increasing. That is, S_i[0] < S_i[1] < ... < S_i[2*D-1].
For each i and each even j, the card S_i[j] is red.
For each i and each odd j, the card S_i[j] is green.
No two sequences share a common element. Hence, for each index x of a non-blue card there is precisely one pair (i,j) such that S_i[j]=x.

Return the number of valid ways to color all white cards, modulo 1,000,000,007.

Definition

Class:: AlternativePiles
Method:: count
Parameters:: String, int
Returns:: int
Method signature:: int count(String C, int M)
(be sure your method is public)

Constraints

C will contain between 1 and 5,000 characters, inclusive.
Each character of C will be 'R', 'G', 'B' or 'W'.
M will be between 1 and 50, inclusive.

Examples

```
"WRGWWRGW"
```
```
2
```
```
Returns: 3
```
There are three valid colorings: "RRGRGRGG", "RRGGRRGG", and "BRGBBRGB". For "RRGRGRGG", we have D=2 and one possibility is to select S_0 = {0,2,3,7} and S_1 = {1,4,5,6}. For "BRGBBRGB", we have D=1 and to show that this is a valid coloring we let S_0 = {5,6} and S_1 = {1,2}.
```
"RRGG"
```
```
1
```
```
Returns: 0
```
There is no valid way.
```
"BBBB"
```
```
5
```
```
Returns: 1
```
Note that D can be zero. Also, note that even though there are no white cards in this test case, there is a valid way to color all white cards: we do nothing and keep the colors we currently have.

"WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

Returns: 265470435

Do not forget to calculate the answer modulo 10^9 + 7.

"WRWRGWWGWWWRWBWRWGWWRWBWWRGWBWGRGWWGWGRWGRWBRWBW"

Returns: 7400348

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.