CircularParking
SRM 811 · 2021-08-19 · by misof
Problem Statement
This problem is about simulating how N cars park along a circular street.
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. (As the road is circular, 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.
For each i from 0 to N-1, inclusive: Car i will arrive to the circular road in such a place that the first parking spot it encounters is the parking spot P[i] = (A*i*i + B*i + C) modulo N.
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, suppose we have N = 4 and (A,B,C)=(1,2,3). Car 0 will park at spot P[0] = 3, car 1 will park at spot P[1] = 2, car 2 will appear next to the occupied parking spot P[2] = 3, drive past it and park at spot 0, and finally car 3 will appear at P[3] = 2, drive past occupied spots 2, 3, and 0, and park at the final free spot 1.
Each time a car encounters an occupied parking spot, a collision occurs. For example, in the scenario described above the cars produce a total of 0 + 0 + 1 + 3 = 4 collisions. We don't like collisions, as they cause delays.
Calculate and return the total number of collisions that will happen while our N cars park.
Notes
- It should be obvious that the correct answer always fits into a signed 64-bit integer.
- Watch out for integer overflows when computing the value "(A*i*i + B*i + C) modulo N".
Constraints
- N will be between 3 and 250,000, inclusive.
- A will be between 0 and N-1, inclusive.
- B will be between 0 and N-1, inclusive.
- C will be between 0 and N-1, inclusive.
47 0 1 0 Returns: 0
For each i, car i arrives at the parking spot i, and as it is empty, it parks there. No collisions.
47 0 0 42 Returns: 1081
Each car arrives at the parking spot 42. Car i will have i collisions before it parks on the spot (42+i) modulo 47.
30 1 1 1 Returns: 175
Car i starts looking for an empty parking spot at the parking spot (i*i + i + 1) modulo 30. There will be some collisions. E.g., eight of the 30 cars will start at the parking spot number 13.
250000 2352 32652 199975 Returns: 93375000
250000 0 0 248987 Returns: 31249875000
4 1 2 3 Returns: 4
The example from the problem statement.
Submissions are judged against all 82 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CircularParking with a public method long long park(int N, int A, int B, int C) · 82 test cases · 2 s / 256 MB per case