TRIATHLON - Editorial

PROBLEM LINKS:
Practice Contest

Editorialist: hackxsaras

DIFFICULTY:
Sorting, STL, Dynamic Programming

PROBLEM (in short):

There are N citizens participating in an event. The event has 3 tracks (say A,B,C in order). Each participant has to do all the three tracks in the same order. More than one participants can do B and C simultaneously whereas A has to be done separately. We can alter the order in which participants appear in the event ( order of tracks remaining same ).

Given, the time required by each of the participants for each track. Calculate the minimum time in which the whole event could be completed.

For example, suppose N = 3, and the time they need for the three tracks are as follows:

tc
If the citizens start at time 0 and proceed in the order 1,2,3, then citizen 1 will finish at time 18+7+6 = 31, citizen 2 will finish at time 18 + (23+10+27) = 78, and citizen 3 will finish at time 18+23 + (20+9+14) = 84. The event ends at time max(31,78,84)=84. (this is not the optimal solution)

EXPLANATION:

Now with keen observation, we could establish a fact that if we arrange the citizens according to the sum of time of the tracks B and C in reverse order, the time is minimised. In the above example the order would be 2, 3,1 because (10+27) > (9+14) > (7+6) and Time to complete event = 74.

So, We have to use a comparator which will sort the citizens according to the sum of B and C in decreasing order [ O(N log N) ] and then just calculate the time required to complete the event [O(N)].

TIME COMPLEXITY:

O(N log N) (as disussed above)

SOLUTION:

Editorialist’s solution

If above link is dead
#include <bits/stdc++.h>
using namespace std;
#define tc int t;cin>>t;while(t--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff(i,a,b) for(int i=a;i<b;i++)
#define fb(i,b,a) for(int i=b;i>a;i--)
#define ffi(i,a,b,c) for(int i=a;i<b;i+=c)
#define fbi(i,b,a,c) for(int i=b;i>a;i-=c)
#define clin(s) getline(cin,s)
#define MOD 1e9+7
#define pb push_back
#define mp make_pair
#define all(var) var.begin(),var.end()
bool comp(vector<int> a,vector<int> b){
    return (a[2]+a[1])>(b[2]+b[1]);
}
int main() {
	int n;
	cin>>n;
	vector<vector<int>> tri;
	ff(i,0,n){
	    int a,b,c;
	    cin>>a>>b>>c;
	    tri.pb({a,b,c});
	}
	sort(all(tri),comp);
	int cobol=0,spent=0;
	for(int i=0;i<n;i++){
	    cobol+=tri[i][0];
	    spent=max(spent,cobol+tri[i][1]+tri[i][2]);
	}
	cout<<spent<<"\n";
	return 0;
}

Thank You for Reading :heart:

Describes an O(N) solution.

Disclaimer: Credit belongs to Md. Tanvir Ahmed for pointing this out in the CommonLounge comments.

Edit:
I have worked out the logic for the O(N) solution. Here is the code for it:

#include <bits/stdc++.h>

using namespace std;

int main () {
    size_t N;
    cin >> N;

    uint ans;

    /*
    O (N) sol.:
    Ordering of tasks is done to minimize
    time taken to perform b + c tasks in the end.
    I.e. ans = COBOL_tasks + Min_overflow_b_c_tasks

    Observation:
        We want shortest task last.
    */

    uint min_end_trail = UINT_MAX, largest_task_end = 0;
    for (size_t i = 0; i < N; i++) {
        uint cobol, b, c; cin >> cobol >> b >> c;
        ans += cobol;
        min_end_trail = min (min_end_trail, b + c);

        // case where last citizen is NOT the citizen which finishes last
        // i.e. case where b+c tasks of previous citizen goes on after the last citizen
        largest_task_end = max (largest_task_end, cobol + b + c);
    }

    ans = max (ans + min_end_trail, largest_task_end);
    cout << ans << endl;
}

As for logic, as stated in the comments, we are always benefited by a citizen who requires shorter time finishing task b, c being scheduled later. However, key observation is that we need not sort the whole array to find the minimum time a citizen takes.