Editorial for Theory of Relativity
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
In order to maximize the reliability ratio, the highest scoring trials must be selected, while skipping over any that come from a saturated experiment. To do this, go through the trials in descending order of reliability ratio while tracking the number of trials already taken from each experiment. Due to the magnitude of the reliability ratios, 32 bits is insufficient for the max score.
Pseudo code
int[] scores = new int[1000001];
long sum = 0;
Trial[] allTrials = new Trial[n];
sort(allTrials);
int added = 0;
for (Trial trial : allTrials) {
if (scores[trial.experiment]++ >= experimentLimit) {
sum += trial.score;
added++;
if (added == trialLimit) break;
}
}
print(sum);
This solution passes, however a more efficient method would be to use a binary heap to store the trials, as iterating through every trial is almost always unnecessary.
Comments