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:

For Subtask 3, because and , we can add up , , and for all to create one function and evaluate it over

Time Complexity:

The intended solution for Subtasks 4 and 5 was to use a triple Prefix Difference Array. For example, we store it in . After accumulating quadratic, linear, and constant differences, compute . The answer is in for all .

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: or up to