Resistance
TCO18 Fun 1A · 2018-04-20 · by Nickolas
Problem Statement
The Resistance is a multiplayer board game. During the game each player belongs into one of two groups: some are resistance members, others are spies. In this problem there are P players, and exactly S of them are spies. The players are numbered 0 through P-1.
The game is played in rounds. In each round of the game a subset of all players goes on a mission. Each player who goes on the mission casts a secret vote on whether they want it to succeed or to fail. Resistance members always vote for the mission to succeed, and spies may cast either vote. (Sometimes a spy will vote for a mission to succeed in order to gain trust of the other players.) If at least one player on a mission voted for it to fail, the mission fails. If everybody voted for the mission to succeed, it succeeds.
You are given the
Verify whether the mission history is valid.
If there is no assignment of roles (spies / resistance members) to players that would be consistent with the given mission history, return an empty
If the mission history is valid, assume that each of the matching assignments of roles to players is equally likely.
Return a
Notes
- Each element of your return value must have an absolute or a relative error smaller than 1e-9.
Constraints
- P will be between 3 and 10, inclusive.
- S will be between 1 and P, inclusive.
- missions will contain between 1 and 50 elements, inclusive.
- Each element of missions will contain exactly P+1 characters.
- For each element of missions, its first character will be 'S' or 'F', and the rest of the characters will be '0' or '1'.
- Each element of missions will contain at least one '1' character.
4
1
{"S0110",
"F1100",
"S0011"}
Returns: {0.5, 0.5, 0.0, 0.0 }
There is only one spy. Players 2 and 3 cannot be the spy because neither of them went on the failed mission. Players 0 and 1 can be spies. As both scenarios are valid, each of these two players is a spy with probability 50%.
4
2
{"F0100",
"S0101",
"F1010",
"S1011"}
Returns: {0.5, 1.0, 0.5, 0.0 }
Now we have two spies. Only one player went to the first failed mission, so we can be certain that player 1 is a spy. Based on the second failed mission, one of players 0 and 2 must be a spy. Both possibilities match the rest of the input, so we assign each of them probability 50% of being a spy. Note that player 1 (a known spy) once voted for a success of a mission.
3
1
{"F110",
"F101",
"F011"}
Returns: { }
There is supposed to be only one spy, but no player went on all three failed missions, so the mission history is invalid.
5
2
{"F11000",
"S00011",
"F10100",
"S01111"}
Returns: {0.8, 0.4, 0.4, 0.2, 0.2 }
One possibility is that the spies are players 1 and 2. Another possibility is that one of the spies is player 0 and the other spy can be any of the other four players.
9
3
{"S100001100",
"F011110000",
"F001000010",
"F100010101",
"S010010001",
"F100001010",
"F000100100"}
Returns: {0.3, 0.1, 0.4, 0.5, 0.2, 0.1, 0.6, 0.7, 0.1 }
3
1
{"F100", "F010", "S001"}
Returns: { }
Min test with -1 answer
3
1
{"S110", "S011", "F101"}
Returns: {0.5, 0.0, 0.5 }
Min test with possible assignments
10
1
{"F1111111111", "S1111111111"}
Returns: {0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1 }
Everybody has equal probability of being a spy (+ identical missions can have different outcomes)
10
1
{"S1111100000", "S0000011111"}
Returns: {0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1 }
No failed missions but somebody has to be a spy
10
10
{"S1111100000", "F0000011111"}
Returns: {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 }
Everybody is a spy!
10
5
{"F1111100111",
"S1001110100",
"S0101001100",
"F1101110110",
"S1101111111",
"S1011111111",
"F1011100101",
"F0010101010",
"F1110001101",
"F0010000101",
"F1111001000",
"S0010111011",
"F0100000101",
"F1001100110",
"S0011110000",
"F0000010110",
"F1111110100",
"F1011001101",
"S0001010011",
"F1010010010",
"F0110000110",
"S1101100001",
"F0101010010",
"S0110100001",
"S0010111001",
"F0001001011",
"S0010010100",
"F1111011111",
"S1111010110",
"S0111111011",
"S0011101010",
"S0011010100",
"F0111110000",
"F1111010110",
"S0011000100",
"F0111110111",
"F0110101011",
"F0101111101",
"F1111100001",
"S1111010111",
"F1011101100",
"F1111010111",
"F0101110001",
"F1000110010",
"S0111100100",
"F0110100101",
"S0111010000",
"S0010001101",
"F1101110100",
"F1000001101"}
Returns: {0.4339622641509434, 0.4716981132075472, 0.49056603773584906, 0.44025157232704404, 0.4276729559748428, 0.5157232704402516, 0.44654088050314467, 0.6226415094339622, 0.5974842767295597, 0.5534591194968553 }
Max missions count
10
5
{"S1111010111",
"S0010000001",
"S0111010100",
"S1101100101",
"S1000100100",
"S0010101111",
"S0110000010",
"S1011001111",
"S1001011110",
"S1110110111",
"S0101001010",
"S1101001100",
"S1111100110",
"S0110011110",
"S0110011101",
"S1000110100",
"S1010100011",
"S0100011100",
"S0000011101",
"S1010000000",
"S0110111000",
"S0000001110",
"S0000100111",
"S1101110111",
"S1011001011",
"S0010000001",
"S1101000110",
"S0001101001",
"S1011011111",
"S0111011100",
"S1001011110",
"S0101010100",
"S1010111000",
"S0100001001",
"S0000001011",
"S0001011001",
"S0010111011",
"S1111011101",
"S1011000100",
"S0011001100",
"S0000101111",
"S0001101011",
"S0111101010",
"S0000010100",
"S1001001100",
"S1010000100",
"S1101101011",
"S0000100010",
"S0010110101",
"S1001111011"}
Returns: {0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5 }
Max number of missions + max number of valid assignments
Submissions are judged against all 58 archived test cases, of which 12 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Resistance with a public method vector<double> spyProbability(int P, int S, vector<string> missions) · 58 test cases · 2 s / 256 MB per case