## Editorial for Angie and Functions

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

#### Subtasks 1 and 2

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

Time Complexity: Query Complexity: #### Subtask 3

##### Official Solution

Observe that the difference of an degree polynomial is equivalent to its derivative.

First, query any adjacent values.

Now, calculate the difference of the original function, this can be done in time using brute force. Then, find the function for the derivative using the power rule and finally solve for the first coefficient ( ) using algebra. Note that modular inverse is required for this part.

Lastly, subtract from all of the queried values, this turns into . As the polynomial has now been reduced to an degree polynomial the above process can be repeated to find .

Time Complexity: Query Complexity: ##### Alternative Solution

Observe that any values can be queried to set up a system of equations to solve for the coefficients. The coefficients can be found using Gaussian elimination in .

Time Complexity: Query Complexity: #### Subtask 4

##### Official Solution

To get the full solution, simply optimize the method from the previous subtask. Observe that the difference of a function follows a regular pattern, allowing the difference to be calculated in time. This brings the overall complexity down to .

The pattern: The pattern follows Pascal's triangle.

Time Complexity: or Query Complexity: ##### Alternative Solution

Alternatively, observe that if adjacent values are queried, the matrix that is created follows certain patterns. These patterns can be exploited to improve the overall time complexity.

Interestingly, the resulting code is almost identical to that of the official solution.

Time Complexity: or Query Complexity: ##### Alternative Solution 2

Lagrange Polynomial

## Comments

• commented on March 21, 2020, 9:37 a.m.

Why don't you mention the solution? https://en.wikipedia.org/wiki/Lagrange_polynomial

• commented on March 21, 2020, 2:06 p.m.

The solution didn't seem interesting so I didn't include it originally, seeing as it was just copy paste some code/implement an equation. However, it was a pretty big oversight when I first wrote the problem.

• commented on March 21, 2020, 1:10 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on March 21, 2020, 2:13 p.m.

I challenge you to implement that solution :)

• commented on March 21, 2020, 11:26 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on March 21, 2020, 3:50 a.m.

Precalculating Pascal's triangle only require time.

• commented on March 21, 2020, 1:40 p.m. edited

Noted, thanks!