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: $\mathcal O(10^N)$ ~\mathcal O(10^N)~

Query Complexity: $\mathcal O(1)$ ~\mathcal O(1)~

Subtask 3

Official Solution

Observe that the $N^\text{th}$ ~N^\text{th}~ difference of an $N$ ~N~ degree polynomial is equivalent to its $N^\text{th}$ ~N^\text{th}~ derivative.

First, query any $N+1$ ~N+1~ adjacent values.

Now, calculate the $N^\text{th}$ ~N^\text{th}~ difference of the original function, this can be done in $\mathcal O(N^2)$ ~\mathcal O(N^2)~ time using brute force. Then, find the function for the $N^\text{th}$ ~N^\text{th}~ derivative using the power rule and finally solve for the first coefficient ( $c_1$ ~c_1~) using algebra. Note that modular inverse is required for this part.

Lastly, subtract $c_1x^N$ ~c_1x^N~ from all of the queried values, this turns $f(x)$ ~f(x)~ into $c_2x^{N-1}+c_3x^{N-2}+\dots+c_Nx+c_{N+1}$ . As the polynomial has now been reduced to an $N-1$ ~N-1~ degree polynomial the above process can be repeated to find $c_2, c_3, \dots$ ~c_2, c_3, \dots~.

Time Complexity: $\mathcal O(N^3)$ ~\mathcal O(N^3)~

Query Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Alternative Solution

Observe that any $N$ ~N~ values can be queried to set up a system of $N$ ~N~ equations to solve for the coefficients. The coefficients can be found using Gaussian elimination in $\mathcal O(N^3)$ ~\mathcal O(N^3)~.

Time Complexity: $\mathcal O(N^3)$ ~\mathcal O(N^3)~

Query Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Subtask 4

Official Solution

To get the full solution, simply optimize the method from the previous subtask. Observe that the $N^\text{th}$ ~N^\text{th}~ difference of a function follows a regular pattern, allowing the $N^\text{th}$ ~N^\text{th}~ difference to be calculated in $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ time. This brings the overall complexity down to $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~.

The pattern:

$\displaystyle \begin{align*} \Delta x &= f(x)-f(x-1) \\ \Delta^2 x &= \Delta x - \Delta (x-1) = f(x) - 2f(x-1) + f(x-2) \\ \Delta^3 x &= \Delta^2 x - \Delta^2 (x-1) = f(x) - 3f(x-1) + 3f(x-2) - f(x-3) \\ \Delta^4 x &= \Delta^3 x - \Delta^3 (x-1) = f(x) - 4f(x-1) + 6f(x-2) - 4f(x-3) + f(x-4) \\ \vdots \end{align*}$

The pattern follows Pascal's triangle.

Time Complexity: $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~ or $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Query Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

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: $\mathcal O(N^2 \log N)$ ~\mathcal O(N^2 \log N)~ or $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Query Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Alternative Solution 2

Lagrange Polynomial

Comments

6

crackersamdjam commented on March 21, 2020, 1:37 p.m. ← edited →

Why don't you mention the $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ solution? https://en.wikipedia.org/wiki/Lagrange_polynomial

2

Plasmatic commented on March 21, 2020, 6: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.

-11

666245 commented on March 21, 2020, 5:10 p.m. ← edited →

Why don't you mention the $\mathcal{O}(1)$ ~\mathcal{O}(1)~ solution? https://en.wikipedia.org/wiki/Hard_coding

This comment is hidden due to too much negative feedback. Show it anyway.

10

zxyl commented on March 21, 2020, 6:13 p.m.

I challenge you to implement that solution :)

-6

pblpbl commented on March 22, 2020, 3:26 a.m.

Hard coding more like hard coding (difficult)

This comment is hidden due to too much negative feedback. Show it anyway.

3

harry7557558 commented on March 21, 2020, 7:50 a.m. ← edited →

Precalculating Pascal's triangle only require $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~ time.

0

Plasmatic commented on March 21, 2020, 5:40 p.m. ← edited →

Noted, thanks!