Simultaneous Lap Crossings
Autumn Tournament (2010)
Submission name: competition.cpp
Problem summary
K runners start together and each completes N laps. Runner i needs ms[i] milliseconds for a fresh lap; each consecutive lap takes one millisecond longer until chocolate after every p[i] laps resets that runner. Find the largest number of runners crossing the start line in the same millisecond. Count finish crossings, but not the initial start.
Input
K N, followed by K pairs ms[i] p[i].
Output
The maximum simultaneous crossing count.
Constraints
2 ≤ K ≤ 10000; 1 ≤ N ≤ 1000; 1 ≤ ms[i] ≤ 1000000; 1 ≤ p[i] ≤ N. The original memory limit is 1 MB.
Worked example
Original statement sample.
Input
4 3 26 2 39 3 45 1 56 2
Output
2
Solution analysis
- For one runner, crossing times form a strictly increasing stream. Start its next crossing at ms[i], with one lap completed. After a crossing with c completed laps, the next lap costs ms[i]+c%p[i]. The remainder is zero immediately after a chocolate reset.
- Keep only the next crossing of each runner in a min-heap. Remove every event at the smallest time, count them, and insert each runner’s following event if that runner has not finished. Since lap durations are positive, a newly inserted event cannot belong to the same time group.
- The first runner crosses at 26,53,79; the second at 39,79,120. Their shared time 79 gives count 2. Storing all K·N crossings would violate the small memory limit; the heap contains at most K events. Three 32-bit fields per event and two runner arrays use roughly 20K bytes of application data.
- Each crossing time is at most N·1000000+N(N−1)/2≤1000499500, so int is sufficient. Heap ordering depends only on time; equal-time runner order is irrelevant because the entire time group is counted together.
Why it works
The heap initially contains the earliest crossing of every runner. Removing one event and replacing it by that runner’s next crossing preserves this invariant. Therefore its minimum is always the earliest unprocessed crossing globally. Grouping all equal minima counts exactly the runners crossing at each time, and taking the maximum gives the answer.
Watch out. Do not count time zero. Reset fatigue after p laps, not before the p-th lap. Do not store or sort all KN timestamps. Include the final crossing even though no following event is inserted.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
struct Event{
int time;
int runner;
int laps;
};
struct Later{
bool operator()(const Event&a,const Event&b)const{
return a.time>b.time;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int runners,totalLaps;
cin>>runners>>totalLaps;
vector<int>fresh(runners),period(runners);
vector<Event>initial;
initial.reserve(runners);
for(int i=0;i<runners;i++){
cin>>fresh[i]>>period[i];
initial.push_back({fresh[i],i,1});
}
priority_queue<Event,vector<Event>,Later>pending(Later{},move(initial));
int answer=0;
while(!pending.empty()){
int time=pending.top().time;
int crossings=0;
while(!pending.empty()&&pending.top().time==time){
Event event=pending.top();
pending.pop();
crossings++;
if(event.laps<totalLaps){
// The completed-lap remainder gives next lap's fatigue.
event.time+=fresh[event.runner]+event.laps%period[event.runner];
event.laps++;
pending.push(event);
}
}
if(crossings>answer){
answer=crossings;
}
}
cout<<answer<<'\n';
}