Editorial for Perfect Test
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.
Hints
Hint 1
Show Hint
Suppose Sean just went from left to right, including every question in the test that he is able to, and skipping those that he cannot. Why would this solution fail?Hint 2
Answer to Previous Hint
An input like 5 -5 -3 -2 is an example that would fail this intuition. By taking the -5 question, we make an inoptimal choice, as we could instead choose the -2 and -3 questions.Show Hint
Let's try making a change to the greedy solution described above. Let's suppose we've greedily picked questions until we can no longer. And the next question is-3.Under what conditions might it be optimal to take the
-3 question, and change our previous decisions?Hint 3
Answer to Previous Hint
It would be better to take the-3 question if one of the previous questions we've taken is worse than -3. This then has us using the same number of questions, but the current student mark would be higher.Show Hint
How can we quickly find the worst question we've included so far? This would help our greedy approach above.Solution
View Solution
If we greedily take the questions from left to right, and store their values in a min-heap, then we can very quickly query to find the worst question we have included so far.If at any point our expected score would go negative, then we can check the worst question we've taken so far, and if this is worse than the prospective next question, we can remove it from the heap and add the next question instead. Since we are removing a negative question, and replacing it with a smaller one further along in the test, we are guaranteed that our previous selection is still valid, and our total never goes negative.
Comments