Connection Status:
Competition Arena > AlternativePiles

AlternativePiles

SRM 615 · 2013-12-22 · by snuke

SRM 615 · 2013-12-22 · by snuke · Dynamic Programming, Greedy, Simple Math
Class Name: AlternativePiles
Return Type: int
Method Name: count
Arg Types: (string, int)
Problem Statement

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.

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
0)
"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}.

1)
"RRGG"
1
Returns: 0

There is no valid way.

2)
"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.

3)
"WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"
50
Returns: 265470435

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

4)
"W"
1
Returns: 1

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

Coding Area

Language: C++17 · define a public class AlternativePiles with a public method int count(string C, int M) · 74 test cases · 2 s / 256 MB per case

Submitting as anonymous