Description
Contest Link
https://www.hackerrank.com/cs2810-ooaia-a7
Objective
● To learn about Incremental sort and also use streams in C++.
Problem Statement
Create a class in C++ to represent Students. This class should also support the functionality to compare two Students based on the given constraints.
The class should have the following attributes.
● ID (Unique for a student)
● Scores in five subjects(No two students will have the same set of scores in all five subjects).
● Skill value (Unique for a student).
● Any other attributes of your choice.
The condition for comparing arbitrary students A and B is:
● Rank(A) < Rank(B) if M(A)>M(B)
1 1
Rank(A) < Rank(B) if M (A)==M (B) and M (A)>M (B) for i=1 to 4 where
● i i i+1 i+1
Mi(A) 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.
There can be 5 types of operations:
1. ADD: Add a student.
2. FIND: Find the difference in ranks between two students given their respective IDs.
3. COUNT: Given a student ID, find the number of students with absolute difference in skill values more than d. i.e. count(|val_i – val_id| > d) ∀ i.
4. PRINT: Print the currentlist of student IDs in the order of their ranks.
As and when a new student is added it is expected that all of them are to be in sorted order i.e. positioning them in their appropriate rank.
You need to choose an appropriate data structure to perform operations efficiently.
Input Format
The operations format are as follows:
1.
2.
3.
4.
Output Format
Output of every query should be printed on a separate line.
1. ADD: nothing to be printed. (no newline as well).
2. FIND: output is an integer.
3. COUNT: output is an integer.
4. PRINT: output is a space separated list of student IDs. Note that there is a trailing space in the end.
Constraints
Number of ADD operations ≤ 105
Number of PRINT operations ≤ 102
Number of FIND+COUNT operations ≤ 105
Sample Testcase
ADD 1 28 15 72 79 53 880704511
ADD 2 9 27 78 89 81 133736473
ADD 3 94 2 98 99 43 102803388
ADD 4 92 61 56 39 96 154547114
ADD 5 19 73 39 13 88 138195161
ADD 6 33 68 17 69 73 749942762
FIND 2 3
COUNT 5 7006739
ADD 7 58 64 7 12 3 587319490
ADD 9 96 89 58 43 49 550217891
PRINT
Output
3 1 2
346152
5
4
93476152
Design Submission Format
For the design submission on Moodle, please submit a .tar.gzfile named as your roll number.
