Editorial for GlobeX Cup '18 S2 - Test Scores


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: alextxu

We can observe that in order to obtain an average of at least K, your test scores need to add up to a value of at least N \times K. Thus, in the solution, we can keep adding on to this total score until N \times K is reached.

For the first subtask, we add 1 to the total score each time. We can decide the test score we should add to by iterating through all of the test scores that are below M and finding the test with the lowest y_i value. We can then add 1 to that test score.

For the second subtask, we also add 1 to the total score each time. Instead of looping through all the tests this time, we can use a data structure such as a priority queue to help us find the lowest y_i value faster.

For the third subtask, we can store two values for each test in an array: M - x_i, and y_i. The first value represents the number of points we can increase this test by until it reaches M. The second represents the number of hours you need to study to increase the score by 1 point. Then, we can sort the array to form an array with non-decreasing y_i values. Then, we traverse the array and keep increasing the total score by M - x_i until it exceeds N \times K. Finally, we subtract the extra hours that we studied to lower the total score to N \times K.


Comments

There are no comments at the moment.