AOC01-Editorial

editorial
,
1

PROBLEM LINK:

contest

Author: hareesh29

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

matrix exponentiation

PROBLEM:

Given n cities(1 to n) and an integer k.find the number of combinations of cities the magician can visit using k teleportation given a restriction that he can’t teleport between two cities x and y.

EXPLANATION:

The information we know from the problem statement is that there are n cities and teleportation is restricted between two of these cites. Let’s split these cities into two different states A and B. State A contains n-2 cities where there are no travel restrictions and State B contains 2 cities(x,y) where teleportation is not allowed between these two cities.

Let A[k] denote the number of ways the magician ends in state A after k teleports and let B[k] denote the number of ways the magician ends in state B after k teleports.now the total number of combination can be calculated by finding A[k] + B[k].

we know that A[1]=n-2 and B[1]=2

now we can find A[2] and B[2] by using this relation

A[2] = A[1]*(n-2)+ B[1]*(n-2)

B[2] = A[1]*(2)+B[1]*(1)

Explanation of the above relation:

  • To reach state A from state A total ways are n-2 as the magician can teleport to any of the n-2 cities from state A

  • To reach state A from state B the total ways are n-2 as the magician can teleport to any of the n-2 cities from state B

  • To reach state B from state A the total ways are 2 as the magician can teleport to any of the 2 cities in state B from State A

  • To reach state B from state B the total ways are 1 as the magician can teleport only teleport to the same city(if he is in city x he can only travel to x similarly for y)

In general

A[k]=A[k-1]*(n-2)+B[k-1]*(n-2)

B[k]=A[K-1]*(2) +B[k-1]*(1)

It can be represented in matrix form as

\begin{bmatrix}A[k]& B[k] \end{bmatrix} = \begin{bmatrix}A[k-1] & B[k-1] \end{bmatrix} *\begin{bmatrix}n-2 & 2 \\n-2 & 1 \end{bmatrix}

Using this reccurence relation we can compute the below relation

\begin{bmatrix}A[k]& B[k] \end{bmatrix} = \begin{bmatrix}A[1] & B[1] \end{bmatrix} *\left[ \begin{array}{}n-2 & 2 \\n-2 & 1\end{array}\right]^{k-1}

now the solution can be found by calculating A[k]+B[k]

Time Complexity:

The time Complexity is O(8*log(k)) where 8 is for matrix multiplication log(k) for exponentiation

SOLUTIONS:

Setter's Solution 
mod=int(1e9)+7
def muL1(l,b):
    mux=[0,0]
    for i in range(2):
        mux[i]=(l[0]*b[0][i])%mod
        mux[i]=(mux[i]+(l[1]*b[1][i]))%mod
    return mux
def mul(b):
    mul=[[0,0],[0,0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                mul[i][j]=(mul[i][j]+b[i][k]*b[k][j])%mod
    return mul  
def matrixexpo(p,b,l):
    while(p>0):
        if(p%2==1):
            l=muL1(l,b)
        b=mul(b)
        p//=2
    return ((l[0]+l[1]))%mod
for _ in range(int(input())):
    n,k,x,y=map(int,input().split())
    l=[n-2,2]
    b=[[n-2,2],[n-2,1]]
    print(matrixexpo(k-1,b,l))
4 Likes