ColorfulJewelry
TCO10 Final · 2010-04-11 · by lyrically
TCO10 Final · 2010-04-11 · by lyrically · Math
Problem Statement
Problem Statement
Some jewels are placed in a rectangular grid on an infinite plane.
You are given String[] jewels describing the jewels.
If the j-th character of the i-th element of jewels is 'R', 'G' or 'B',
there is a red, green or blue jewel at the center of the j-th cell of the i-th row of the grid, respectively.
Jewels of the same color cannot be distinguished.
Alice draws two squares on this plane. Their sides must be parallel to the axis and have length k. She is allowed to draw squares so that some part of them are on the outside of the grid. Then she will get the jewels which lie in the inside of at least one of the two squares. Note that the inside of a square does not contain its boundary. She wants to make a chain of jewels, using some of the jewels she will get. She does not have to use all of the jewels she will get. A chain is a row of one or more jewels. Chains are non-directional. For example, chains R-G-B and B-G-R are considered equal. How many different chains are possible, considering all the chains from all possible square locations? Return the answer modulo 1,000,000,009.
Alice draws two squares on this plane. Their sides must be parallel to the axis and have length k. She is allowed to draw squares so that some part of them are on the outside of the grid. Then she will get the jewels which lie in the inside of at least one of the two squares. Note that the inside of a square does not contain its boundary. She wants to make a chain of jewels, using some of the jewels she will get. She does not have to use all of the jewels she will get. A chain is a row of one or more jewels. Chains are non-directional. For example, chains R-G-B and B-G-R are considered equal. How many different chains are possible, considering all the chains from all possible square locations? Return the answer modulo 1,000,000,009.
Notes
- For the purposes of this problem, a jewel is considered to be a single point.
Constraints
- jewels will contain between 1 and 44 elements, inclusive.
- Each element of jewels will contain the same number of characters.
- Each element of jewels will contain between 1 and 44 characters, inclusive.
- Each character in jewels will be either 'R', 'G' or 'B'.
- k will be between 1 and 44, inclusive.
Examples
0)
{ "RGB" }
1
Returns: 6
Alice can get at most two jewels. The possible chains are: R, G, B, R-G, R-B, G-B.
1)
{ "RGB" }
2
Returns: 9
Alice can get all the three jewels.
2)
{ "RGB" }
10
Returns: 9
3)
{ "RRRRR",
"RGGRR",
"RGGGG",
"RRRGG" }
2
Returns: 280
4)
{ "RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR",
"RRRRRRRRRR" }
6
Returns: 68
56)
{"BBGRRGR","GRGGBBB","BRRGBGB","GGGGBBG","RGRGGGG","GRGGRGG","BBGRRGR"}
4
Returns: 1000000008
Case with answer MOD-1 (to catch a "return ret-1;" error).
Submissions are judged against all 73 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulJewelry with a public method int getChains(vector<string> jewels, int k) · 73 test cases · 2 s / 256 MB per case