Editorial for CCC '22 S2 - Good Groups


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.

The second problem in this year's competition requires input to be stored together in a data structure. Because the assignment of students to groups is not given until the end of the input, the constraints cannot be fully considered as they are encountered, and so must be stored in memory. It is helpful to also store the student groups in memory.

Once both types of input are in memory, a solution can be obtained by considering each constraint individually and maintaining a count of how many are violated.

Likely pitfalls include incorrectly assuming something about the order in which student names appear, and erroneously thinking that a group can only violate one constraint.

Care must be taken with the Boolean logic required to test if a given constraint is violated. This will require determining if a given student is in a given group. Doing this inefficiently by looping through all the groups or looping through all the students should have allowed a submission to earn 8 of the available 15 marks. To earn the final mark, this look-up must be made more efficient. This can be accomplished using a data structure built-in to the language designed for this very purpose (e.g., a dictionary in Python, a HashMap in Java, or an unordered_map in C++).


Comments

There are no comments at the moment.