Problem Link - Triathlon
Problem Statement
The Republic of Tutaria is celebrating its 37th year of independence. To mark the occasion, the nation is organising a contest where all its N citizens take part. The event has three tracks, a COBOL programming competition, pole vault, and a doughnut-eating competition. Each citizen takes part in these three tracks in the same order—a citizen starts with the programming competition, continues with the pole vault as soon as his or her COBOL masterpiece is ready, and then starts gorging on doughnuts as soon as the pole vault is done.
The Supreme Leader of Tutaria closely monitors all citizens and knows the exact amount of time each citizen will take in each of the three tracks. She wants to schedule the event so that it will finish as early as possible. However, the Republic of Tutaria has only one computer, and, as a result, only one person can participate in the COBOL programming event at a time. However, any number of people may simultaneously participate in the pole vault and doughnut-eating competitions.
The event works as follows. The Supreme Leader fixes the order in which contestants get access to the computer. At time 0, the first citizen in the list starts writing his or her COBOL program, while the remaining citizens wait for the computer to be free. As soon as the first citizen is done, he or she proceeds to the pole vault, and the second citizen gets the computer for the programming round. In general whenever the computer becomes free, the next citizen gets to use it. Whenever a citizen is done using the computer, he or she proceeds to the pole vault immediately, regardless of what the other citizens are doing. Similarly, whenever a citizen is done with the pole vault, he or she proceeds to the doughnut-eating track immediately, independently of the others. The event ends as soon as all the citizens have finished all the three tracks of the event.
Approach
We want to minimize the total time of the event. Since only one person can use the computer at a time for the COBOL track
, we need to consider the time each person spends on the three tracks. The time a person spends in total is the sum of their times in COBOL
, pole vault, and doughnut-eating
. We start by adding up the times of all citizens. Then, for each citizen, we calculate how long they will take, factoring in that while they are doing the pole vault or eating doughnuts, others can continue those activities concurrently. To find the minimum time to complete all the activities, we track the maximum time either taken by a citizen’s total time or the time required by the current citizen once they finish COBOL
and the others have completed their tasks. At the end, we return the maximum of these values, which ensures we finish as early as possible while considering the constraints of the event.
Editorialist's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n;cin>>n;
ll idx = -1;
ll totalc = 0;
vector<ll> cobol;
vector<ll> times;
ll maximize = 0;
for(size_t i = 0;i<n;i++)
{
ll c,p,d;cin>>c>>p>>d;
totalc += c;
ll total = c+p+d;
maximize = max(maximize, total);
times.push_back(total);
cobol.push_back(c);
}
ll mint = INT_MAX;
for(size_t i = 0;i<n;i++)
{
ll timeif = times[i]+totalc-cobol[i];
mint = min(mint, timeif);
}
cout<<max(mint,maximize)<<endl;
return 0;
}
Time Complexity
The time complexity is O(n) because we go through each citizen once to compute their total times.
Space Complexity
The space complexity is O(n) due to the storage of the citizen’s times and other variables.