RPSRobots | Topcoder Archive

Problem Statement

This task references the traditional game Rock-Paper-Scissors. In this game each of the two players simultaneously chooses one of those three objects. Rock beats Scissors, Scissors beat Paper, and Paper beats Rock. If both players choose the same object, the game is a tie.

We have n Rock-Paper-Scissors robots. Each robot has a fixed string called strategy and a nonnegative integer called state. Each character in the robot's strategy is one of 'R', 'P', and 'S', denoting Rock, Paper, and Scissors, respectively. The strategies of all robots have the same length: k.

Whenever a robot plays one round of Rock-Paper-Scissors, he performs the following steps:

Use strategy[state modulo k] as his choice in the round of the game.
Increment state by 1.

For example, if strategy = "RRS" and state = 10, then the next few moves will be: Rock, Scissors, Rock, Rock, Scissors, Rock, Rock, Scissors ... A match between two robots consists of exactly k consecutive rounds. The result of the match is the pair (number of rounds won by the first robot, number of rounds won by the second robot). Sometimes the result will depend on the initial states of both robots, and in other cases the result will be same regardless of their states. A pair of robots is called attuned if the result of their match is independent from their states.

For example, if two robots have strategies "RPS" and "RSP", the result of their match will be (1,1), regardless of their states at the beginning of the match. Hence, this pair of robots is attuned. On the other hand, consider two robots with strategies "RPS" and "RPS". The result of this match can be (0,0), (3,0), or (0,3) based on the robots' initial states. Hence, this second pair of robots is not attuned.

You are given a set of robots in a format that is described below. A non-empty subset of these robots is called attuned if all pairs of robots in the subset are attuned. (Note that trivially all subsets of size 1 are attuned as well.) Please compute and return the number of attuned subsets of robots, modulo 10^9 + 7.

You are given the following data:

The int n: the number of robots.
The String[] r: the strategies of the first few robots. The value k can be determined as the length of any of these strategies.
The ints seed, pR, pP, and pS: parameters for a pseudorandom generator used to produce the rest of the input.

Use the pseudocode below to generate the strategies of all robots.

        long now = seed;
        long a = 22222223;
        long b = 12345678;
        long mod = 1000000000 + 7;
        String[] input = new String[n];
        for(int i = 0; i &lt; r.length; i++)
            input[i] = r[i];
        for(int i = r.length; i &lt; n; i++)
        {
            String s = "";
            for(int j = 0; j &lt; r[0].length(); j++)
            {
                if((now % (pR + pP + pS)) &lt; pR)
                    s += "R";
                else if((now % (pR + pP + pS)) &lt; pR + pP)
                    s += "P";
                else
                    s += "S";
                now = (now * a + b) % mod;
            }
            input[i] = s;
        }

Definition

Class:: RPSRobots
Method:: countGoodSet
Parameters:: int, String[], int, int, int, int
Returns:: int
Method signature:: int countGoodSet(int n, String[] r, int seed, int pR, int pP, int pS)
(be sure your method is public)

Notes

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

n will be between 1 and 100,000, inclusive.
k will be between 1 and 18, inclusive.
r will contain between 1 and min(n, 1000) elements, inclusive.
Each element of r will contain exactly k elements.
Each character in r will be one of 'R', 'P', 'S'.
seed will be between 0 and 1,000,000,006, inclusive.
pR, pP, pS will be between 0 and 1,000, inclusive.
pR + pP + pS > 0.

Examples

```
3
```
```
{"RRR", "RPS", "RPS"}
```
```
0
```
```
1
```
```
1
```
```
1
```
```
Returns: 5
```
We have 5 attuned sets: {0}, {1}, {2}, {0,1}, {0,2}.
```
3
```
```
{"RRR", "RPS", "RSP"}
```
```
0
```
```
1
```
```
1
```
```
1
```
```
Returns: 7
```
This time we have 2 more since ("RPS", "RSP") are attuned: {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}.
```
6
```
```
{"RRRR", "RRPP", "PSPS"}
```
```
123456789
```
```
1
```
```
1
```
```
1
```
```
Returns: 13
```
Input = {"RRRR", "RRPP", "PSPS", "RSRR", "PSSR", "PSRR"}.
```
50
```
```
{"PPPPPPPPP"}
```
```
22222223
```
```
0
```
```
100
```
```
0
```
```
Returns: 898961330
```
All 2^50-1 non-empty subsets are good, so the answer is (2^50-1) % (10^9+7).

{"SSSSSSSSSSSS"}

Returns: 230852587

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.