Description
Hackerrank Link: www.hackerrank.com/midsem-1
Problem Statement
Create a class in C++ to represent Students(similar to the previous assignment).
The class should have the following attributes:
● Marks of 5 subjects (No two students will have the same set of scores in all five subjects)
● Skill level(Two students can have the same skill level)
The condition for comparing arbitrary students A and B is:
● Rank(A) < Rank(B) if M1(A)>M1(B)
● Rank(A) < Rank(B) if M (A)>M
(A)==M (B) and M (B) for i=1 to 4 where M (A)
i
i
i+1
i+1
i
denotes marks of student A in subject i
Rank is defined as the position of a student in the sorted order using the above condition. It is indexed from 1.
Let the skill levels of student A and student B (A ≠ B) be S and S, and let their ranks be R and
A B A
R. (A, B) is a special pair if A’s skill level is higher than B’s skill level, but A has a
B
greater(worse) rank than B, i.e. (A, B) is a special pair if SA > SB and RA > RB
Count the total number of special pairs.
(Hint: Merge-Sort)
Input Format
The first line contains the total number of students n.
Each of the following n lines contains 6 space-separated integers: marks of 5 subjects and skill level.
n // Number of total students
n lines in the following format:
Output Format
A single integer denoting the number of special pairs.
Constraints
1 ≤ Number of students ≤ 105
1 ≤ Marks in any subject ≤ 103
1 ≤ Skill level ≤ 109
Subtasks
10 marks:
1 ≤ Number of students ≤ 5000
1 ≤ Marks in any subject ≤ 103
1 ≤ Skill level ≤ 109
5 marks:
1 ≤ Number of students ≤ 105
1 ≤ Marks in any subject ≤ 103
1 ≤ Skill level ≤ 102
10 marks:
1 ≤ Number of students ≤ 105
1 ≤ Marks in any subject ≤ 103
1 ≤ Skill level ≤ 109
Sample Testcase
Input:
5
123455
234514
345123
451232
512341
Output:
10