Gangsters
TCO18 Wildcard Fun Round · 2018-04-20 · by monsoon
Problem Statement
There are people gangsters in Gangsterville, and that small town definitely isn't big enough for all of them. Therefore they decided to organize a shootout. May only the best survive!
The gangsters arranged themselves in a circle. For simplicity we'll number them from 1 to people along the circle. Each gangster is pointing his gun at the next gangster in the circle. (I.e., for each valid i gangster number i is aiming at gangster number i+1, and the last gangster is aiming at gangster 1.)
In order to make the gunfight more spectator-friendly, the gangsters have decided that they will shoot sequentially. Before the gunfight they will choose one of the people! possible orders uniformly at random. Then, they will shoot their guns in the chosen order. (Obviously, gangsters who have already been shot do nothing when it's their turn.) Each gangster always hits their target.
Calculate the number of orderings for which the number of gangsters who will survive is exactly alive. Return the answer modulo 10^9+7.
Constraints
- people will be between 3 and 150, inclusive.
- alive will be between 0 and people, inclusive.
4 2 Returns: 12
We have four gangsters numbered 1, 2, 3, and 4 along the circle. There are 4! = 24 possible orders in which they will shoot. First consider the six permutations in which gangster 1 shoots first: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 In each of these six settings gangster 1 will shoot gangster 2. As gangster 2 will not shoot, gangster 3 is guaranteed to survive. In three of these six setting gangster 3 will shoot before gangster 4. In these three scenarios the survivors will be gangsters 1 and 3. In the other three scenarios gangster 3 will be the only survivor. We can then make similar reasoning for the remaining cases. In total there are 12 orderings with exactly two survivors (and another 12 with just one survivor).
3 1 Returns: 6
There are six possible shooting orders for three gangsters. For all of them only one gangster will remain alive.
3 0 Returns: 0
It is not possible that no one survives.
9 3 Returns: 203616
3 2 Returns: 0
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Gangsters with a public method int countOrderings(int people, int alive) · 100 test cases · 2 s / 256 MB per case