Editorial for TLE '17 Contest 2 P4 - ECOO
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
We first must determine what is meant by a "guaranteed win". From the description, we are guaranteed to win at a certain time if there is no possible way for the opponent to win, regardless of what happens in the future. Therefore, we consider the worst case scenario: we fail to get any points on unsolved problems after the time, and our opponent immediately perfectly solves any problems that they haven't solved.
Suppose we are checking if we win at time
For the first two subtasks, it suffices to perform a binary search per query and loop through all submissions to determine the points the two teams can get.
Time Complexity:
For the third subtask, we can optimize our summation process by using a data structure such as a Binary Indexed Tree. However, we cannot simply have the indexes of our BIT represent time, since it can be up to
Also be careful that a submission that scores
Time Complexity:
Comments
"Therefore, we consider the worst case scenario: we fail to get any points on unsolved problems after the time, and our opponent immediately perfectly solves any problems that they haven't solved."
What about the problems that they have already solved but did not get a perfect score on them? Mustn't they consider whether it is worthwhile to redo the problem in case they would get a higher score overall with the new time bonus and perfect score?
EDIT: nvm, "To simplify, all teams will make up to one submission to each problem."