CS3230 programming assignment 2
Due: 17 Nov 23:59
1 Problem statement
You are a coach of an athletic team with n athletes. You wish to send some of
your athletes to a competition.
The rules of the competition are as follows:
• A team consists of x runners and y swimmers.
• Each person is only allowed to participate in one sport; in other words a
single person cannot be both a runner and a swimmer.
• The score of a team is the total time taken by all x runners and all y
swimmers.
As the coach, you know that athlete i (1 ≤ i ≤ n) takes a[i] time to run and
b[i] time to swim. Your task is to form the best team and find the minimum
possible total time taken by choosing x runners and y swimmers.
2 Input format
The first line of the input consists three space-separated integers, n, x, y. n lines
then follow. The i-th of these lines consists of two space-separated integers a[i]
and b[i].
3 Output format
Output a single integer, the minimum possible total time taken by x runners
and y swimmers.
4 Samples
Sample input 1
3 1 1
1
670 7279
1264 4798
7392 135
Sample output 1
805
Sample input 2
4 1 1
8580 8343
3721 6099
5225 4247
940 340
Sample output 2
4061
Sample input 3
5 1 1
6082 1564
4428 5648
6992 6200
3946 9225
9944 6939
Sample output 3
5510
5 Constraints
• 3 ≤ n ≤ 105
• 0 ≤ x, y ≤ n, x + y ≤ n
• 1 ≤ a[i] ≤ 104 (for all 1 ≤ i ≤ n)
• 1 ≤ b[i] ≤ 104 (for all 1 ≤ i ≤ n)
Required time complexity for full credit (5 points): O(n log n).
Solutions which run in O(n2 log n) will receive 4 points – you will only need
to pass test cases satisfying n ≤ 4000 to get these 4 points.
2
6 Submission instructions and grading
(Same policy as previous assignment) Submit your solution to CodeCrunch in
either C++ or Java. You need to pass all test cases to get 5 points (or all test
cases satisfying n ≤ 4000 to get 4 points).
The tasks will be labelled full and partial.
• If your final submission to full is correct, you will receive 5 points and
your submission to partial will be ignored. If you are confident of your
submission to full, you do not need to submit to partial.
• If your submission to full is incorrect, or you did not submit to full, then
your solution to partial will be graded, in which you may receive 3 points
if your solution to partial is correct.
• If multiple submissions are made, only the last one will be graded.
7 Collaboration policy
You may discuss the problems with your classmates, though you should write
up your solutions on your own. Please note the names of your collaborators in
your submission. You may want to refer to the plagiarism policy from Lecture
2.
You are not allowed to share code.
3
cs3230_programming_assignment_2
