Editorial for BPC 1 J3 - Group Project - DMOJ: Modern Online Judge

Editorial for BPC 1 J3 - Group Project

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: squishybanana04

Hint 1

Try to pair students with those of similar quality. For example, it would make sense to pair the worst student with the second worst, and the best with the second best.

Solution

If you sort the list of students, you will find the optimal pairings. Then you can iterate to find the number of complaints.

Proof: After optimally pairing up every student, look at a subset of 2 pairs. Let $A$ ~A~ be paired with $B$ ~B~, and $C$ ~C~ be paired with $D$ ~D~. Also, without loss of generality, let $q_A \le q_C$ ~q_A \le q_C~. If $q_B > q_D$ ~q_B > q_D~, then it is better to pair $A$ ~A~ with $D$ ~D~. Therefore, in an optimal pairing, $q_A \le q_C \implies q_B \le q_D$ ~q_A \le q_C \implies q_B \le q_D~.

Comments

There are no comments at the moment.