PROBLEM LINK:
Contest
Author: Akshay Padte
Tester: Aditya Prajapati
Editorialist: Akshay Padte
DIFFICULTY:
EASY
PREREQUISITES:
Sorting, Mod
PROBLEM:
Given N students, find if it’s possible to divide them into rows such that each row except the last contains P students and the last contains anywhere from P to P+K students, given the additional condition that all students must have a height strictly lesser than all students in all rows behind them
QUICK EXPLANATION:
This problem can be solved by sorting the students then dividing them into rows of P each until at most P+K remain. If not even one row is formed or if less than P remain or if the last student in the ith row has the same height as first student in the i+1th row, the answer is NO. Otherwise YES.
EXPLANATION:
We are given three integers N, P and K. We can test the possibilty of the arrangement by dividing the students into rows according to the given conditions. If we can’t, the answer is NO.
Notice that if N < P or if (N mod P) > K, the arrangement is not possible. If N < P, the first row itself is impossible to form. If (N mod P) > K, the last row would have to be of more than P+K students, which is not allowed.
Now that we have checked for these cases, we must also check the condition for heights. First we sort the students according to their heights. As the only parameter here that defines a student is their height, this can be done simply by sorting the list of heights.
Then we must divide them into rows of P each until atmost P+K remain in the last row. One way to imagine this is to place imaginary barriers between the Pth and P+1th student, 2Pth and 2P+1th student, etc starting from the shorter ones. We can keep a track of the position of the barrier by creating a list B = [P, 2P, 3P, …]
When we form the first row, N-P students still aren’t a part of any row. When the second row is formed N-2P students are still not in any row. We keep on assigning rows until we encounter N-iP <= P+K. The remaining students form the last row. That is, we keep on adding imaginary row barriers till we reach a point where we have <=P+K remaining students.
Now as the students are sorted by height, none can have height greater than a student in any row behind him/her. The only thing to consider is equality. If an equality of height exists, it must obviously be between two consecutive students in the sorted list. That means we just need to check if last the student in the ith row has the same height as first student in the i+1th row. This is where we use our list of barriers. As this list contains the indexes of students after which there is a row barrier, to compare the heights last the student in the ith row and first student in the i+1th row, we simply compare the heights of student number B[i] and B[i]+1.
What if P=K?
In this case the last 2P students can be divided into two rows of P or can be a part of a single row of 2P students. To avoid a case of height equality, the second arrangement is preferred. The above mentioned approach takes care of this.
Possible cases you may have missed:
6 3 1 101 102 103 103 104 105 4 2 2 103 102 102 101 6 1 1 102 101 105 103 105 104 4 5 1 100 100 100 100
Answers for these:
NO - The last student in the 1st row and the first student in the 2nd row have equal heights. YES - You must form only one row of 4 students. YES - Form only five rows. Put two students of height 105 in the last row. NO - As N < P, not even one row can be formed.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.