Editorial for TLE '17 Contest 2 P4 - ECOO - DMOJ: Modern Online Judge

Editorial for TLE '17 Contest 2 P4 - ECOO

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

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 $t$ ~t~. Then, we sum up the points for both ourselves and our opponent. Then, we suppose that we earn 0 more points, and the opponent gets perfect on every problem they have remaining. That is, our opponent receives $P$ ~P~ plus whatever time bonus is earned by submitting at time $t$ ~t~ for each problem they have yet to submit to. If our score is still higher, then we are guaranteed to win at time $t$ ~t~. We can find the minimal $t$ ~t~ by performing a binary search.

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: $\mathcal{O}(QN \log N)$ ~\mathcal{O}(QN \log N)~

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 $10^{10}$ ~10^{10}~. Therefore, we must compress all possible times that appear, which can be done by processing all of the queries first. Be wary that your count of how many problems the other team has solved by a given time $t$ ~t~ is correct; another BIT may be needed to accomplish this.

Also be careful that a submission that scores $0$ ~0~ does not get any time bonus.

Time Complexity: $\mathcal{O}(Q \log^2 N)$ ~\mathcal{O}(Q \log^2 N)~

Comments

1

jkguipqnjcy49979693 commented on Oct. 29, 2017, 9:17 p.m. ← edited →

"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."