Editorial for Back To School '18: The Golden Porcupine

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

Subtasks 1 and 2 are intended to reward brute force solutions.

Time Complexity: $\mathcal{O}(NT)$ ~\mathcal{O}(NT)~

For Subtask 3, because $l=1$ ~l=1~ and $r=T$ ~r=T~, we can add up $a_i$ ~a_i~, $b_i$ ~b_i~, and $c_i$ ~c_i~ for all $1 \le i \le N$ ~1 \le i \le N~ to create one function and evaluate it over $[1, T]$ ~[1, T]~.

Time Complexity: $\mathcal{O}(N+T)$ ~\mathcal{O}(N+T)~

The intended solution for Subtasks 4 and 5 was to use a triple Prefix Difference Array. For example, we store all differences in $P[T][4]$ ~P[T][4]~. After accumulating quadratic, linear, and constant differences, compute $P[T][k] = P[T-1][k] + P[T][k+1]$ ~P[T][k] = P[T-1][k] + P[T][k+1]~. The answer is in $P[i][0]$ ~P[i][0]~ for all $1 \le i \le T$ ~1 \le i \le T~.

There are many ways to solve this problem. One common solution during the contest was to keep distinct Prefix Difference Arrays for the quadratic, linear, and constant differences. Another approach that avoids the Prefix Difference Array altogether is a line sweep.

Time complexity: $\mathcal{O}(N+T)$ ~\mathcal{O}(N+T)~ or up to $\mathcal{O}((N+T) \times (\log N + \log T))$

Comments

6

madhur4127 commented on Jan. 21, 2020, 3:06 p.m.

Every fast solution I see uses prefix sums technique. Can you explain more about the line sweep?

2
d commented on July 6, 2022, 9:20 p.m.
Each quill represents 2 events:

Add $(a_i, b_i, c_i)$ ~(a_i, b_i, c_i)~ at time $L_i$ ~L_i~.

Subtract $(a_i, b_i, c_i)$ ~(a_i, b_i, c_i)~ at time $R_i+1$ ~R_i+1~.

Sort the events by increasing time.