## Editorial for DMOPC '19 Contest 6 P6 - Math is Difficult

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

A brute force solution suffices for this subtask.

Time Complexity:

Let's say student solves problem with extra help, and problem was their unsolved problem, the amount of penalty they lose is

Previously, was calculated manually in time. Using a prefix sum array speeds this up to .

Time Complexity:

Firstly, calculate the penalty for each student assuming that they don't ask for help. The penalty for a student who has solved problems is.

This can be calculated quickly using a prefix sum array (there are other ways to do this as well).

Now, we just have to find the maximum penalty loss a student can obtain.

Consider problem #:

Let

Let

A student who solves problem when it's their unsolved problem loses penalty. Notice how this is the same as getting the y-coordinate of a line at a given x-coordinate. Thus, we now convert each problem into a line .

Additionally, if we loop through the students from most problems solved to least problems solved, problems become available for extra help in the order of highest index to lowest index (and don't ever become unavailable). Thus, we can simply insert problems into a data structure when they become available, and query for the maximal value at a certain -value to compute the answer for a student.

The only issue left is that for each student, we query for their first unsolved problem, for their second, etc. To fix this, we simply shift the line units to the left for all so that we only query -value per student. This works because the set of unsolved problems for each student occupies a continuous range of indices.

A data structure that maintains this set of available lines efficiently is the Dynamic Convex Hull Trick.

Time Complexity:

We can expand on our solution from subtask 3 to account for the availability of help on certain days.

We can do this with a segment tree: maintains a Dynamic CHT for all the problems that are available in the days . When inserting problem , stop when is completely within and insert the problem into .

When querying for student , we query every where . There are such ranges and they also cover the set of all problems available to that student.

This can also be done using divide and conquer: solve(l, r) considers only the problems and students available in the days . Then, relevant students and problems are passed onto solve(l, mid) and solve(mid + 1, r) respectively, where . Calling solve(1, D) will compute the answer for each student and we can simply print it out afterwards.

Time Complexity:

There is also a solution with complexity that does a linesweep on the days. In order to delete lines from the CHT, they're stored in blocks of size and the CHT is rebuilt each time. However, that solution won't be gone over in full detail here.

As always, feedback is welcome.