This problem featured in the Indian National Olympiad on Informatics in 2012. This problem is supposed to be of intermediate difficulty.
https://www.codechef.com/IOIPRAC/problems/INOI1201
The problem asks you to find out what is the minimum time in which the contest can be completed if you get to choose the order in which the participants start and given the times they take to complete each of the three tasks. Keep in mind that each task can only be completed if the previous task is completed before it.
There are a few observations to be made before we start solving this problem.
First of all the second and third tasks can be merged into one as they will be performed concurrently and sequentially by all the participants as soon as they have finished their first task.
d[i] = b[i] + c[i]
Where b[i] and c[i] are the times taken to complete the second and third tasks.
Now secondly, we need to decide in which order the participants will start. Think of it two at a time. What decides Person A will go before Person B given both their timing for the tasks ?
Assume Person A goes first and calculate the maximum time it will take. Now calculate it when Person B goes first. After some tedious analysis. It turns out that the person with the larger d[i] should go first. intuitively, it can be said that he will take a longer time to complete the second task and hence has to start it earlier. To do that he has to go first.
Now all we have to do is sort based on d values and let the contest proceed in that order. Calculate the end time of the contest and output it.
Java Code :
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int tim = 0;
Point p[] = new Point[N];
int ar[] = new int[N];
for (int i = 0; i < N; i++) {
p[i] = new Point();
st = new StringTokenizer(br.readLine());
p[i].x = Integer.parseInt(st.nextToken());
p[i].y = Integer.parseInt(st.nextToken()) + Integer.parseInt(st.nextToken());
}
Arrays.sort(p, new Comparator
@Override
public int compare(Point p1, Point p2) {
return p2.y – p1.y;
}
});
for(int i = 0; i < N; i++){
tim += p[i].x;
ar[i] = tim + p[i].y;
}
int m = 0;
for(int x : ar){
m = (x > m) ? x : m;
}
System.out.println(m);
}
}
Karthi
Karthikeyan M : Geek, Gamer, Coder, Blogger - he shares his love of Technology in the form of tutorials, reviews, and how-to’s. An avid reader, he is a student at SRM university pursuing his B.Tech. in Information Technology.
