RainbowConnection
SRM 827 · 2022-04-04 · by misof
Problem Statement
A rainbow has seven colored arcs: red, orange, yellow, green, blue, indigo, and violet. We will denote the colors by their first letters: ROYGBIV.
N children are sitting around a circle painting rainbows. The children are numbered 0 to N-1 around the circle.
Each child always paints the rainbow by drawing arcs in the above order. Thus, each non-empty rainbow picture can uniquely be represented by a single letter: for example, 'Y' represents a picture with red, orange and yellow arc already painted.
You are given the
Children paint their rainbows in steps. At the beginning of each step, each child x takes a look at their left neighbor (child (x-1) modulo N) and notes the number of arcs that child currently has on its picture. Then, each child adds the remembered number of arcs to its own picture.
Whenever a child wants to add an eighth arc to an already completed rainbow, instead the child gives the finished picture to their teacher, takes a new clean sheet of paper, and draws the first arc of a new neighbor.
Determine aggregate information about the situation after S steps. For each picture type, in ROYGBIV order, determine the number of kids that will currently have in front of them a picture of that type.
Return these counts, still in ROYGBIV order, as a
Notes
- Do not count the pictures given to the teacher during the process, only the pictures the kids have at the end.
Constraints
- C will have between 2 and 5,000 characters, inclusive.
- Each character in C will be one of "ROYGBIV".
- S will be between 1 and 10^18, inclusive.
"RRRRR"
2
Returns: {0, 0, 0, 5, 0, 0, 0 }
Five kids. Initially, each has a single arc (the red arc) painted. In the first step each kids looks at their left neighbor, notices one arcs, looks back at their own picture, and paints one arc. Thus, after the first step each kid has two arcs painted (red+orange). In the second step each kid will see two arcs and then paint two extra arcs. Thus, in the end we have five 'G' pictures and no other pictures.
"RRRRR"
3
Returns: {5, 0, 0, 0, 0, 0, 0 }
Continuing Example 0, in the third step each kid will paint four more arcs. I.e., each kid will finish their first rainbow picture, hand it to the teacher, and then paint the first arc of a new picture. Recall that the pictures given to the teacher are not counted.
"VO"
1
Returns: {0, 2, 0, 0, 0, 0, 0 }
Kid 0 sees two arcs on its neighbor's picture, so it hands off the completed picture and paints two arcs onto a new one. Kid 1 sees seven arcs on its neighbor's picture, so it paints a total of seven new arcs. (After five arcs it has a finished rainbow. That one gets handed off to the teacher. The next two arcs go on the next picture.)
"ROYGBIVROYGBBB"
47
Returns: {0, 2, 2, 6, 2, 0, 2 }
Final state: "BGVGOYGBGVGOYG".
"ROYGBIVROYROYGBIROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBROYGBIVROYROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBBVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBROYGBIVROYGIVROYGBBBGIVROYGBBB"
987654321987654321
Returns: {707, 719, 751, 693, 715, 677, 738 }
Submissions are judged against all 33 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RainbowConnection with a public method vector<int> paint(string C, long long S) · 33 test cases · 2 s / 256 MB per case