Editorial for CCC '24 J3 - Bronze Count


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.

There are several different ways of solving this problem.

One approach is to maintain six variables storing values for the gold, silver and bronze score as well as a count of the number of participants with each of these scores. Taking care to initialize these variables properly, they can then be updated as needed given each new score. This approach can be used to pass all three subtasks.

Another approach is to first store a collection of all the scores in a data structure (e.g. in a list in Python or an ArrayList in Java). Then the maximum score (gold score) can be calculated and all occurrences of this score removed from this collection. Then the new maximum score (silver score) can be calculated and all occurrences of this score removed from the updated smaller collection. The maximum of the scores remaining in this even smaller new collection is the bronze score and the number of times it occurs can be computed and printed. This approach will pass the first two subtasks. Whether or not this approach passes the last subtask depends on how computing and removing occurrences of the maximum score is implemented. As long as this is done by passing over the collection a fixed/constant number of times (i.e. increasing the size of the collection does not affect how often a pass is made over the collection), this approach should also pass the third subtask.

Sorting can also be used here. After sorting the scores, the bronze score can be identified quickly for the first subtask where the scores are distinct. Otherwise, a loop is needed to scan from highest to lowest score effectively finding the "boundaries" between the gold and silver scores and between the silver and bronze scores. Any built-in sorting function/method should be fast enough to pass the last subtask. It is also possible but challenging to implement a sorting algorithm which will be fast enough to earn full marks with this strategy.


Comments

There are no comments at the moment.