ParkingSequences
2021 Regional 2 · 2021-04-13 · by misof
Problem Statement
There is a long circular one-way road. Along the road there are N parking spots, numbered from 0 to N-1 in order. As you drive along the road, parking spot numbers increase (and after N-1 you get back to 0).
Initially, all parking spots are empty. N cars arrive to the circular road and park there. The cars arrive one at a time: the next car always arrives only after the previous one has parked.
The cars are numbered from 0 to N-1 in the order in which they arrive. The numbering of cars is unrelated to the numbering of parking spots.
Different cars may enter the circular road at different locations. For each car i, let P[i] be the first parking spot it will encounter. The sequence P will be called a parking sequence.
There are N^N different parking sequences.
Each car drives along the road until it finds an empty parking spot. Once it finds an empty parking spot, it parks there.
For example, if we have N = 4 and the parking sequence {3, 2, 2, 3}, car 0 will park at spot 3, car 1 will park at spot 2, car 2 will drive past occupied spots 2 and 3 and park at spot 0, and finally car 3 will drive past occupied spots 3 and 0 and park at the final free spot 1.
Each time a car encounters an occupied parking spot, a collision occurs. We don't like collisions, as they cause delays. The badness of a parking sequence is the number of collisions it causes.
For example, the above parking sequence {3, 2, 2, 3} has badness 4.
Let C(X,Y) be the number of parking sequences for X cars and X parking spots such that during the parking there are exactly Y collisions.
You are given N and B. Calculate and return C(N,B) mod 1,000,000,007.
Constraints
- N will be between 1 and 50, inclusive.
- B will be between 0 and N*(N-1)/2, inclusive.
- B will not exceed 200.
4 6 Returns: 4
In order to have the maximum number of collisions, all cars have to arrive at the same place. Each car will then drive along all previously-parked cars until it reaches an empty parking spot. Thus, the parking sequences we seek are the sequences {0,0,0,0}, {1,1,1,1}, {2,2,2,2}, and {3,3,3,3}.
13 0 Returns: 227020758
In order to have no collisions at all, each car must arrive at a different parking spot. Thus, the parking sequences we are counting in this example are permutations of order N. The return value equals 13! modulo (10^9 + 7).
4 1 Returns: 48
Two of these parking sequences: {0,0,2,3}: the collision is car 1 passing by car 0 parked on the spot 0 {1,2,2,0}: car 0 parks on the spot 1, car 1 parks on the spot 2, car 2 arrives at spot 2 (collision), continues to the empty spot 3 and parks there. Then, the final car arrives at spot 0 and parks there.
5 9 Returns: 25
In order to have exactly one fewer collisions than the theoretical maximum, each car must start at the same spot, except for one car that will start one spot further along the road. For example, {4, 4, 4, 0, 4} is one of these parking sequences.
1 0 Returns: 1
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 ParkingSequences with a public method int count(int N, int B) · 100 test cases · 2 s / 256 MB per case