PROBLEM LINK
DIFFICULTY
Medium
SOLUTION
This problem requires us to solve a system of linear equations. But we need to solve a lot of different cases, in which the coefficients of the equations are fixed. Thus we need to some preprocessing. We can either calculate the inverse of the coefficient matrix as it is guaranteed that they have a unique solution, or we can maintain three matrices
P, L and U
which form the LUP decomposition of the matrix. We can get the LUP decomposition in time
O(N^3)
and then solve all subsequent cases in time
O(N^2)
using forward and backward substitution. More detail is available at the Wikipedia article.