SATA05 - Editorial

PROBLEM LINK:

Practice

Contest

Author: Akul Sareen

Tester: Akashdeep Nain

Editorialist: Akul Sareen

DIFFICULTY:

HARD

PREREQUISITES:

Polynomial interpolation

PROBLEM:

Given the value of l(x) for x = 0,1,…,n-1, find the value of p(x) for x = 0,1,…,n-1 where

p(x) = a1 * x1 + a2 * x2 + .... + aN * xN mod(109+7) and l(x) = a1 * 1x + a2 * 2x + .... + aN * Nx mod(109+7)

QUICK EXPLANATION:

The question can be re-written to find the inverse of a matrix. The inverse of this matrix is a Vandermonde matrix, whose inverse can be found using polynomial interpolation techniques.

EXPLANATION:

Using the definition of l(x) we can re-write the values l(x) we know in the following form:

$\begin{pmatrix}
1^0 && 2^0 && \ldots && N^0\
1^1 && 2^1 && \ldots && N^1\
\vdots && \vdots && \vdots && \vdots\
1^N && 2^N && \ldots && N^N
\end{pmatrix}
\times
\begin{pmatrix}
a_1\
a_2\
\vdots\
a_N
\end{pmatrix}

\begin{pmatrix}
l(1)\
l(2)\
\vdots\
l(N)
\end{pmatrix}$

which we can write in short as, A \times X = B. Therefore, X = A^{-1} \times B. Once we know X, then we can easily find the value of p(x) at x = 0,1,…,n-1.

So the question boils down to finding A^{-1}. Using Gaussian elimination we can find A^{-1} in \mathcal{O}(N^3). However, this is not fast enough for us.

So, let us look at A once again. It should look strangely familiar to anyone who has performed polynomial interpolation. In fact, if we look at the transpose of A:

A^T = \begin{pmatrix} 1^0 && 1^1 && \ldots && 1^N\\ 2^0 && 2^1 && \ldots && 2^N\\ \vdots && \vdots && \vdots && \vdots\\ N^0 && N^1 && \ldots && N^N \end{pmatrix}

This is a Vandermonde matrix. It is the exact matrix whose inverse we would want to find if we wanted to interpolate a polynomial f(x), given its value at x = 1,2,…,N.

We know polynomials can be interpolated in \mathcal{O}(N^2) time. So hopefully, we will be able to find (A^T)^{-1} in \mathcal{O}(N^2), and then use the fact that (A^T)^{-1} = (A^{-1})^T to find A^{-1}.

Let us consider one of the standard ways of polynomial interpolation using Lagrange polynomials.

This says, that if f(x) = c_1 + c_2x + \dots + c_Nx^{N-1}, and you are only given (x_1,f(x_1)),(x_2,f(x_2)),\dots,(x_N,f(x_N)) then you can recover f(x) as

f(x) = \sum_{i = 1}^{N}l_i(x) \times f(x_i)

where

l_i(x) = \prod_{0 \le j \le N, j \ne i} \frac{x - x_j}{x_i - x_j}

i.e. $\begin{pmatrix}l_1(x) \ l_2(x) \ \ldots \ l_N(x)\end{pmatrix}
\times
\begin{pmatrix}f(x_1) \ f(x_2) \ \ldots \ f(x_N)\end{pmatrix}^T

\begin{pmatrix}f(x)\end{pmatrix}
$

In fact, if we denote the coefficient of x^j in l_i(x) as l_{i,j}, then we can expand the previous expression to:

$
\begin{pmatrix}
l_{1,0} && l_{2,0} && \ldots && l_{N,0}\
l_{1,1} && l_{2,1} && \ldots && l_{N,1}\
\vdots && \vdots && \vdots && \vdots\
l_{1,N-1} && l_{2,N-1} && \ldots && l_{N,N-1}
\end{pmatrix}
\times
\begin{pmatrix}
f(x_1)\
f(x_2)\
\vdots\
f(x_N)
\end{pmatrix}

\begin{pmatrix}
c_1\
c_2\
\vdots\
c_N
\end{pmatrix}
$

where c_1,c_2,\dots,c_N are the coefficients of f(x)

Now, if we let x_1 = 1, x_2 = 2, \dots, x_N = N, then we can show:

$A^T \times
\begin{pmatrix}
c_1\
c_2\
\vdots\
c_N
\end{pmatrix}

\begin{pmatrix}
f(x_1)\
f(x_2)\
\vdots\
f(x_N)
\end{pmatrix}
$

Therefore,

(A^T)^{-1} = \begin{pmatrix} l_{1,0} && l_{2,0} && \ldots && l_{N,0}\\ l_{1,1} && l_{2,1} && \ldots && l_{N,1}\\ \vdots && \vdots && \vdots && \vdots\\ l_{1,N-1} && l_{2,N-1} && \ldots && l_{N,N-1} \end{pmatrix}

This means, we can find A^{-1} quickly if we can find all l_i(x) quickly. To compute all l_i(x) quickly we can first precompute T(x) = \prod_{1 \le i \le N}x - x_i in \mathcal{O}(N^2).

Now,

l_i(x) = \frac{T(x)}{x - x_i}\prod_{0 \le j \le N, j \ne i} \frac{1}{x_i - x_j}

This calculation can be done in \mathcal{O}(N) for each l_i(x). Hence, we can find all l_i(x) in \mathcal{O}(N^2) time. Using these we can find A^{-1}. After that we can easily find the coefficients of the lopymonial. Once, we have those we can easily evaluate our polynomial at all the required points.

ALTERNATIVE SOLUTION:

The tester came up with an entirely different approach (I think) which I have no clue about. However, I am attaching it so that if anyone wishes they can consult it.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

//