TRIPWAYS Unofficial Editorial

Please reply if anything requires more explanation. I’ll add it if I find it necessary.

Original Problem Statement

Explanation

Let dp[u][D] be the number of ways to finish the journey if you start at node number u and take D days to finish the journey ( We won’t be explicitly calculating this, this is just an intermediate step for the actual solution ).

When at node u, if we want to spend total D days, we can spend r days visiting tourist attractions (where 0 \le r \le D-1), and then go to any v \in \text{adj}[u] (taking up one day), and continue the journey form v. Here, adj[u] is the set of all vertices v such that (u,v) is an edge. On each day, we have L[u] choices of tourist attractions to visit, so number of ways to visit tourist attractions is L[u]^r.

So, dp[u][D] can be expressed recursively as \displaystyle dp[u][D] = \sum_{v \in \text{adj}[u]} \sum_{r=0}^{D-1} L[u]^r dp[v][D-1-r]

Also, dp[n][D] = L[n]^D

This is clearly a convolution. If we create generating functions ( 1 2 ) G_u(x) = \displaystyle \sum_{r=0}^{\infty} dp[u][r] x^r, we can recursively express the dp relation as

G_u(x) = \displaystyle \frac{x}{1-L[u]x} \sum_{v \in \text{adj}[u]} G_v(x)

with base case G_n(x) =\displaystyle \frac{1}{1 - L[n]x}

Now, looking at the expression here, we can say that the denominator will be exactly \displaystyle \prod_{\text{there exists a path from u to v}} (1 - L[v]x).

You can prove this by induction, but I won’t because it’s very straightforward, and should be intuitively obvious.

Also, the highest power of x in the numerator is exactly 1 less that that of denominator, since for G_n(x), it is 1 less and at each subsequent step we are multiplying numerator and denominator by equal powers of x.

Now, we can apply a method that is seen in solving linear homogenous recurrences

Since we know the factorisation of the denominator, we can do a partial fraction decompostion of the G_u(x)

Let \{l_1,l_2,l_3 \cdots l_k\} be the distinct values of L[u] for all the nodes, where L[u] = l_i for m_i different values of u i.e. its m_i is the multiplicity of l_i.

We can now assume that G_u(x) for any u is of the form

\displaystyle \frac{a_{1,1}}{(1 - l_1x)^1} + \frac{a_{1,2}}{(1 - l_1x)^2} \cdots \frac{a_{1,m_1}}{(1 - l_1x)^{m_1}} + \\ \frac{a_{2,1}}{(1 - l_2x)^1} + \frac{a_{2,2}}{(1 - l_2x)^2} \cdots \frac{a_{2,m_2}}{(1 - l_2x)^{m_2}} + \\ \vdots \\ \frac{a_{k,1}}{(1 - l_kx)^1} + \frac{a_{k,2}}{(1 - l_kx)^2} \cdots \frac{a_{k,m_k}}{(1 - l_kx)^{m_k}} ,

which is exactly n terms.

We can now represent G_u(x) as n coefficients of the form a_{u,i,j}.

To calculate G_u(x), we first calculate

\displaystyle \sum_{v \in \text{adj}[u]} G_v(x) = \sum_{v \in \text{adj}[u]} \sum_{i=1}^{k} \sum_{p=1}^{m_i} \frac{a_{v,i,j}}{(1 - l_ix)^p} = \sum_{i=1}^{k} \sum_{p=1}^{m_i} \frac{ \sum_{v \in \text{adj}[u]} a_{v,i,j}}{(1 - l_ix)^p} = \sum_{i=1}^{k} \sum_{p=1}^{m_i} \frac{T_{u,i,j}}{(1 - l_ix)^p}.

where \displaystyle T_{u,i,j} = \sum_{v \in \text{adj}[u]} a_{v,i,j}\ . We can calculate this in O(|\text{adj}[u]|N), which when added up for each u comes out to be O(MN).

We can easily derive expressions for a_{u,i,j} in terms of T_{u,i,j}, l_i \ \text{and}\ L[u]. There are 2 expressions, one for when L[u] = l_i and one for L[u] \neq l_i.

I won’t be providing these expression as they are fairly ugly and take away from the bigger picture of the overall solution. You can refer to my code for them ( as I said it’s not pretty ).

Knowing this representation of G_u(x), we can calculate dp[u][D] using the binomial theorem as \displaystyle \sum_{i=1}^{k} \sum_{p=1}^{m_i} a_{u,i,p} \cdot l_i^D \cdot \binom{D+p-1}{p} in O(N \log D)

We are of course interested in dp[1][D] for each query.

Overall complexity

O(NM + QN \log D)

Example

As an example, I will calculate G_1(x) for the sample test case in original problem statement.

\displaystyle G_4(x) = \frac{1}{1-7x}

\displaystyle G_3(x) = \frac{x}{1-6x} \left( \frac{1}{1-7x} \right) = \frac{-1}{1-6x} + \frac{1}{1-7x}

\displaystyle G_2(x) = \frac{x}{1-6x} \left( \frac{1}{1-7x} \right) = \frac{-1}{1-6x} + \frac{1}{1-7x}

\displaystyle G_1(x) = \frac{x}{1-2x} \left( \left( \frac{-1}{1-6x} + \frac{1}{1-7x} \right) + \left( \frac{-1}{1-6x} + \frac{1}{1-7x} \right) \right) \\ = \frac{x}{1-2x} \left( \frac{-2}{1-6x} + \frac{2}{1-7x} \right) \\ = -\frac{1}{2} \left( \frac{1}{1-6x} \right) + \frac{2}{5} \left( \frac{1}{1-7x} \right) + \frac{1}{10} \left( \frac{1}{1-2x} \right)

So, number of ways of finishing the journey in D days is \displaystyle \frac{(-5)\cdot 6^D + 4\cdot7^D + 2^D}{10}

Another Example

Another example, which has multiplicity greater than 1 for a term.

I’ll take the same testcase as before but take L[4] = 6 and L[3] = 7 instead.

\displaystyle G_4(x) = \frac{1}{1-6x}

\displaystyle G_3(x) = \frac{x}{1-7x} \left( \frac{1}{1-6x} \right) = \frac{-1}{1-6x} + \frac{1}{1-7x}

\displaystyle G_2(x) = \frac{x}{1-6x} \left( \frac{1}{1-6x} \right) \\ = -\frac{1}{6} \frac{1}{1-6x} + \frac{1}{6} \frac{1}{(1-6x)^2}

\displaystyle G_1(x) = \frac{x}{1-2x} \left( \left( -\frac{1}{6} \frac{1}{1-6x} + \frac{1}{6} \frac{1}{(1-6x)^2} \right) + \left( \frac{-1}{1-6x} + \frac{1}{1-7x} \right) \right) \\ \ \\ = \frac{x}{1-2x}\left( -\frac{7}{6} \frac{1}{1-6x} + \frac{1}{6} \frac{1}{(1-6x)^2} + \frac{1}{1-7x} \right ) \\ \ \\ = \frac{9}{80} \frac{1}{1-2x} + \frac{1}{5} \frac{1}{1-7x} + \frac{-17}{48} \frac{1}{1-6x} + \frac{1}{24} \frac{1}{(1-6x)^2}

18 Likes

Thanks for sharing your solution!
I had been trying to compute the kth power of the matrix using the closed form for powers of triangular matrices as described here - https://arxiv.org/pdf/1301.6820.pdf, but couldn’t get it working.

3 Likes

Thanks for sharing this! When I was trying to solve this question (using a completely different approach), i ended up requiring to compute a sum over all possible subsets of all cities (which was ofc out of constraints and didn’t work :stuck_out_tongue:)

2 Likes

I tried this question with langrange interpolation as I thought answer would be in degree n, as I am not so good at maths. Thanks for the editorial.i thought it is Lagrange interpolation because of This question. It also has some similar dp as I used in this question for 5 points. But both are totally different.

Here’s another approach: We have P(x), Q(x) = \prod_{i=1}^r {(1-a_ix)^{k_i}}. We want to calculcate the coefficient of

\frac{P}{Q} = \sum _{i=1}^r \frac{R_i (x)}{(1-a_ix)^{k_i}}, \quad \deg R_i < k_i

Let q_i(x) = (1-a_ix)^{k_i}, V_i(x) = R_i(x) Q(x)/q_i(x), we found out that P(x) \bmod q_i(x) = V_i(x) \bmod q_i(x).
Hence we just need to calculate R_i(x) = P(x) \left[Q(x)/q_i(x) \bmod q_i(x)\right]^{-1} \bmod q_i(x). Through the extended euclidean algorithm on polynomial is \Theta(nk_i), this algorithm has total complexity of \Theta(n^2).
BTW, if we use FFT, the time complexity would be \Theta(n\log n\log r).

5 Likes

Thanks for the solution , but I don,t know this much mathematics. But I was trying to solve this problem with what I have in my knowledge base.
Here is my approach but I am stuck at one point where I want to find it in minimum time.

I was thinking this problem from MULTINOMIAL THEOREM.
Let,s denote a example path from 1 to N as 1->2->4->N and tourists places be L[1],L[2],L[4] and L[N]. Now I will spare 3 days for going from 1 to N that is , no. of edges in path from 1 to N. Suppose we have “D” days for this journey.

Now we just need to find-:
coefficient of (x^(D-3)) in[ (1-L[1]*x) * (1-L[2]*x) * (1-L[4]*x) * (1-L[N]*x)]^-1 . How should I find it ? I have got one Idea from your approach that I will do partial fraction that will reduce the polynomial into easier terms and then It would be the summation of respective binomial coefficients from from each of the terms . Grateful for the article. Please suggest me how to take this approach forward to solve it very efficiently.

@dks2111

I can start from your approach and get to my solution if that helps.

Firstly, coefficient of x^{D-3} in \frac{1}{(1-L[1]x)(1-L[2]x)(1-L[4]x)(1-L[N]x)} = coefficient of x^D in \frac{x^3}{(1-L[1]x)(1-L[2]x)(1-L[4]x)(1-L[N]x)}

Your approach is then, to sum coefficient of x^D in \frac{x^{k-1}}{(1-L[u_1]x)(1-L[u_2]x) \ldots (1-L[u_{k-1}]x)(1-L[u_{k}]x)} for all paths u_1,u_2,\ldots u_k where u_1=1 and u_k=n, which is the same as coefficient of x^D in the sum of all of these functions. We will call this sum of functions G_1(x).

Since the degree of numerator and denominator of such a function is at most n, we can store this polynomial in O(n) space.

But since there can be exponential number of such paths (consider the graph where (i,j) is an edge if i<j), we cannot directly go through all of them in reasonable time.

However we can ‘reuse’ some calculations to create a dynamic programming solution. A path from 1 to n is just a path from 1 to v + a path from v to n where v is directly reachable from 1.

So, we can say G_u(x) = \frac{x}{1-L[u]x} \sum_{v\in \text{adj}[u]} G_v(x)

I would say that any math I’ve included here is just to make it unambiguous and compact ( sigma notation for sums ). Maybe that makes it look complicated but it really is very simple stuff. At least, it is no more math than what would be required to understand partial fractions, which is what you’d learn around 11th grade ( in India ).

1 Like

@psaini72 is there any prerequisites that I should study before this… as many things seems unclear as I try to read it :pleading_face:

1 Like

@patwari26 The resource I gave on Partial Fraction decomposition and the following fact should be enough.

For any sequence a = \{a_0, a_1, a_2 \ldots \} let \displaystyle g_a(x) = \sum_{i=0}^{\infty}a_i x^i i.e. its generating function.

If there are sequences a,b,c such that \displaystyle c_n = \sum_{i=0}^{n} a_ib_{n-1-i} then g_c(x) = g_a(x)g_b(x)

In the above case, I took a as a_0=0, a_n=L[u]^{n-1} \forall n>0, giving g_a(x) \frac{x}{1-L[u]x} and b_n = dp[v][n], giving g_b(x) = G_v(x)

I also suggest expanding out the \sum s just to get a better idea of what exactly I am doing here. Maybe you can un-comment some print statements in my code to do that too.

If you have any specific doubt, comment here again.

1 Like

How is a i,j calculated and why we have obtained terms with multiplicity more than degree 1 .

The L value of 2 nodes on a path from 1 to n can be the same. Consider the testcase

4 4 10
2 6 7 6
1 2
1 3
2 4
3 4
1 2 3 4 5 6 7 8 9 10

The multiplicity of \frac{1}{1-6x} in G_1(x) is 2.

From the post:

I still haven’t added these expressions. I guess I will add them in a few days.

I do not know why I am not able to understand multiplicity.I thought multiplicity is the degree of denominator after partial fraction decomposition.But again I failed to understand this thing .I am not understanding the meaning of multiplicity here .
Lets consider G1(x) as obained by you in the explanation .
Then it has terms with only degree 1 in denominator after Decomposition into Partial Fractions.The thing I am not understanding is why we will have terms like 1/(1-lx)^k .Why wont we have only terms like 1/(1-lx) .Basically I am failing to understand what is multiplicity referring to here .
Thanks for your Efforts and Time !!

@bhavyarustgi10 The multiplicity is simply the exponent of a given value in the denominator. I’ve added another example in the original post that should help clarify things.

That is not correct. The denominator is of the form (1 - L[u_1]x)(1 - L[u_2]x)\ldots(1 - L[u_k]x). It may look like we have terms of only degree 1, but different nodes can have the same value of L[u] i.e. L[u_i] can equal L[u_j] even if i \neq j. This is what is happening in the case I provided (for G_2(x) and G_1(x)). The multiplicity of 1-6x is 2 in that case.

Maybe this example from the wiki page will help. Ignore the x^2+1 term

1 Like

Oh !! Now I got it .I just assumed they are different every-time .Now I got it .Thanks :slight_smile: for your so much efforts and time .