BIKE - Editorial

[kingofnumbers]

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

HARD

PREREQUISITES:

math, matrix expontiation, polynomial multiplication, lagrange polynomial

PROBLEM:

Given a directed graph of N vertices and integer T, each edge has two types of costs F_i and R_i, for each i, j, k count the number of paths of length T which starts at vertex i and end at same vertex, and the total cost of first type is j (modulo N) and the total cost of the second type is k (modulo N-1)

SHORT EXPLANATION

let’s first find a way to mix both edge costs into a single cost in range 0 … n * (n-1)-1 then we use matrix exponentiation where each cell is a polynomial of degree n * (n-1)-1, the coefficient xⁱ of polynomial in cell in j-th row and k-th column tells us the number of ways to go from vertex j to vertex k in a route of length i modulo n * (n-1)

so let’s create matrix A of size N*N such that cell in j-th row and k-th column have polynomial equal to 0 if there’s no edge from vertex j to vertex k, otherwise it is equal to xⁱ where i is the length of that edge

Now all we need is to compute A^T using matrix exponentiation then we are done, as you know fastest method to multiply two polynomials is O(m log m) where m is the degree of the biggest polynomial but this will be slow so we need to store polynomials in interpolation form of N * (N-1) values in a way that support circular convolution

EXPLANATION

Changing double costs of an edge into single cost

first thing to do is to find a way to change from double costs into a single cost L_i, this cost should satisfy L_i = F_i (mod N) and L_i = R_i (mod N-1), and it should be in range [0,N*(N-1)-1], this value L_i always exists and unique in that range since N-1 and N are coprimes, to find this value:

since L_i = F_i (mod N) then L_i should be of form K*N+F_i, let’s substitute it in L_i = R_i (mod N-1) so we have

K*N+F_i = R_i (mod N-1)

K = R_i- F_i (mod N-1)

so K should be equal to (R_i- F_i) mod N-1

Transformation matrix

Let’s create a matrix A of N * N cells such that cell in j-th row and k-th column have polynomial equal to 0 if there’s no edge from vertex j to vertex k, otherwise it is equal to xⁱ where i is the length of that edge.

now A^T will give us the information we need, cell i-th row and j-th column will give us a polynomial of degree N(N-1)-1* such that its coefficient of x^k will tell us the number of paths from vertex i to j of length k (modulo N * (N-1))

how to compute A^T? if we used O(N^3) matrix multiplication algorithm and O(M log M) FFT polynomial multiplication algorithm (where M is degree of polynomial which is N * (N-1)), then we will have O(N^5 log N log T) solution which is so slow specially with the hight constant factor from FFT algorithm so we need a faster method.

Faster multiplication method

actually we can make polynomial multiplication faster if we store polynomials in other way than the set of coefficient values, a polynomial of degree N * (N-1)-1 can be uniquely determined by interpolation of N * (N-1) points, usually it’s fine to choose any N * (N-1) points but since in our case our polynomial multiplication should be circular (i.e. if exponent of some X became bigger or equal N * (N-1) then we should take the exponent modulo N * (N-1))

for this reason we have to choose N * (N-1) points carefully, now let w be an integer such that w^(N * (N-1)) = 1 (mod 1163962801), then in each cell of transformation matrix we store those N * (N-1) values

P(w⁰), P(w¹), P(w²), … P(w^{N * (N-1)-1})

where P is the polynomial in that cell, now to multiply two polynomials A and B we just calculate N * (N-1) new points which are

A(w⁰) * B(w⁰), A(w¹) * B(w¹), A(w²) * B(w²), … A(w^{N * (N-1)-1}) * B(w^{N * (N-1)-1})

and this is O(N * (N-1)) instead of O(N * (N-1) log (N * (N-1))), now we just need to restore coefficients of polynomials on the diagonal of A^T, which can be done using lagrange interpolation.

Lagrange Interpolation

say we have N points (**X₁,Y₁), (**X₂,Y₂) … (**X_N,Y_N)

and we want to find a polynomial which passes through all these points, it can be done in the following way.

let L_i(X) be polynomial such that it returns zero on all X_j except when i=j it returns non-zero value

it’s easy to see that L_i(X) = (X-X₁)(X-X₂) … (X-X_i-1)(X-X_i+1)…(X-X_N)

now say P is the required polynomial then

P(X) = Y₁ * L₁(X) / L₁(X₁) + Y₂ * L₂(X) / L₂(X₂) … Y_N * L_N(X) / L_N(X_N)

now we extract P(X) to get the desired coefficients

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

[ceilks]

Seems like we’re effectively still using the (number-theoretic) DFT. The evaluation at points w^i are (n=N\cdot(N-1))

P(w^i)=\sum_{j=0}^{n-1}a_j w^{ij}

with the coefficients a_i of the polynomial and w a n-th root of unity. So the evaluation and interpolation steps could be speeded up further using a fast number theoritic transform.