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: \mathcal{O}(NM^2)

Let's say student i solves problem j with extra help, and problem j was their k^{th} unsolved problem, the amount of penalty they lose is

\displaystyle kv_j+v_{j+1}+v_{j+2}+\cdots+v_M

Previously, v_{j+1}+v_{j+2}+\cdots+v_M was calculated manually in \mathcal{O}(M) time. Using a prefix sum array speeds this up to \mathcal{O}(1)

Time Complexity: \mathcal{O}(NM)

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

\displaystyle v_{i+1}+2v_{i+2}+\cdots+(M-i)v_M= \sum_{k=i+1}^M v_k + \sum_{k=i+2}^M v_k + ... + \sum_{k=M}^M v_k

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 #i:

Let m=v_i

Let b=v_{i+1}+v_{i+2}+\cdots+v_M

A student who solves problem i when it's their x^{th} unsolved problem loses mx+b 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 y=mx+b.

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 x-value to compute the answer for a student.

The only issue left is that for each student, we query x=1 for their first unsolved problem, x=2 for their second, etc. To fix this, we simply shift the x^{th} line i units to the left for all 1 \le i \le M so that we only query 1 x-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: \mathcal{O}((N+M) \log{M} + N \log{N})

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: seg[l..r] maintains a Dynamic CHT for all the problems that are available in the days [l, r]. When inserting problem i, stop when seg[l..r] is completely within [l_i, r_i] and insert the problem into seg[l..r].

When querying for student i, we query every seg[l..r] where l \le d_i \le r. There are \le \log{D} 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 [l, r]. Then, relevant students and problems are passed onto solve(l, mid) and solve(mid + 1, r) respectively, where mid= \left\lfloor \frac{l+r}{2} \right\rfloor. Calling solve(1, D) will compute the answer for each student and we can simply print it out afterwards.

Time Complexity: \mathcal{O}((N+M)\log{M} \log{D} + N \log{N})

There is also a solution with complexity \mathcal{O}(M \sqrt{M} + N \log{M} \sqrt{M}) that does a linesweep on the days. In order to delete lines from the CHT, they're stored in blocks of size \sqrt{M} and the CHT is rebuilt each time. However, that solution won't be gone over in full detail here.

As always, feedback is welcome.


Comments

There are no comments at the moment.