N students attend a school contest. Every student can be described with five values:
his/her, grades in Math, Physics, Biology, English and Chemistry (each out of 10). To
simplify the competition, if student X has all of this values less than or equal to the values
of student Y, the student X should be dismissed from the contest.
For example:
Math Physics Biology English Chemistry
Student X 7 5 4 6 8
Student Y 8 7 6 6 9
We need to find an efficient way to compute how many students should be dismissed
from the contest.
Input
The first line contains one integer N – the number of contestants
The next N lines contains the scores of each student apart (i.e., the score of the first
student in Math, Physics, Biology, English and Chemistry) the grades of the second
student is in the next line and so on.
Output
Output the answer to the problem.
Examples
Ex1 Ex2 Ex3
input 3
1 4 2 5 6
4 3 2 4 8
2 5 3 6 7
4
4 5 8 4 6
4 6 7 2 9
5 4 7 1 6
6 7 8 9 6
3
2 4 5 7 9
4 4 2 4 8
1 5 8 6 7
output 1 2 0
Note
In the first example, you can find the values of the 1st student is less than or equal to the
values of the 3rd student, and hence the 1st student should be dismissed. On the other
hand the 2nd and 3rd student do not comply with this dismiss rule.
a) Using a brute-force approach, design an algorithm to solve this problem, and analyze
its complexity (3+2 marks)
b) Design an efficient algorithm to solve this problem, and analyze its complexity [Hint:
you can use any data-structure] (7+3 marks)
c) Implement your efficient algorithm using Python (10 marks)
d) Prepare a brief report (250 words) comparing the two algorithms (5 marks)
