Subtasks 1 and 2

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

Time Complexity: ~\mathcal O(10^N)~

Query Complexity: ~\mathcal O(1)~

Subtask 3

Official Solution

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

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

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

Lastly, subtract ~c_1x^N~ from all of the queried values, this turns ~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~ degree polynomial the above process can be repeated to find ~c_2, c_3, \dots~.

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

Query Complexity: ~\mathcal O(N)~

Alternative Solution

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

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

Query Complexity: ~\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}~ difference of a function follows a regular pattern, allowing the ~N^\text{th}~ difference to be calculated in ~\mathcal O(N \log N)~ time. This brings the overall complexity down to ~\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)~ or ~\mathcal O(N^2)~

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

Query Complexity: ~\mathcal O(N)~

Alternative Solution 2

Lagrange Polynomial