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

Subtask 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^{th} difference of an N degree polynomial is equivalent to its N^{th} derivative.

First, query any N+1 adjacent values.

Now, calculate the N^{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^{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 hasnow 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^{th} difference of a function follows a regular patten, allowing the N^{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 adjecent 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


Comments


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

    Why don't you mention the O(n^2) solution? https://en.wikipedia.org/wiki/Lagrange_polynomial


    • 2
      Plasmatic  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.


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

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


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

        I challenge you to implement that solution :)


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

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


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

    Precalculating Pascal's triangle only require O(N^2) time.