# TRIPWAYS Unofficial Editorial

**URL:** <https://discuss.codechef.com/t/tripways-unofficial-editorial/61745>\
**Category:** tutorial\
**Tags:** april20\
**Created:** [April 13, 2020, 11:23am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745 "2020-04-13T11:23:15Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\
**Post date:** [April 13, 2020, 11:23am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/1 "2020-04-13T11:23:15Z")

</div>

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

[Original Problem Statement](https://www.codechef.com/APRIL20A/problems/TRIPWAYS)

# 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](https://en.wikipedia.org/wiki/Generating_function#Ordinary_generating_function_(OGF)) [2](https://en.wikipedia.org/wiki/Generating_function#Tables_of_special_generating_functions) ) 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](https://www.math.cmu.edu/~af1p/Teaching/Combinatorics/Slides/Generating-Functions.pdf)

Since we know the factorisation of the denominator, we can do a [partial fraction decompostion](https://www.mathsisfun.com/algebra/partial-fractions.html) 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](https://www.codechef.com/APRIL20A/status/TRIPWAYS,psaini72) 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](https://mathworld.wolfram.com/NegativeBinomialSeries.html) 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}

---

<div class="post-metadata">

**Author:** ![blackgold](https://discuss.codechef.com/user_avatar/discuss.codechef.com/blackgold/32/3653_2.png) [@blackgold](https://discuss.codechef.com/u/blackgold)\
**Post date:** [April 13, 2020, 12:01pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/2 "2020-04-13T12:01:28Z")

</div>

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](https://arxiv.org/pdf/1301.6820.pdf), but couldn’t get it working.

---

<div class="post-metadata">

**Author:** ![sigma\_g](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sigma_g/32/24644_2.png) [@sigma\_g](https://discuss.codechef.com/u/sigma_g)\
**Post date:** [April 13, 2020, 1:29pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/3 "2020-04-13T13:29:15Z")

</div>

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 😛)

---

<div class="post-metadata">

**Author:** ![nvdrag\_123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nvdrag_123/32/3653_2.png) [@nvdrag\_123](https://discuss.codechef.com/u/nvdrag_123)\
**Post date:** [April 14, 2020, 3:59am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/4 "2020-04-14T03:59:18Z")

</div>

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](https://codeforces.com/problemset/problem/995/F). It also has some similar dp as I used in this question for 5 points. But both are totally different.

---

<div class="post-metadata">

**Author:** ![ei\_captain](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ei_captain/32/11177_2.png) [@ei\_captain](https://discuss.codechef.com/u/ei_captain)\
**Post date:** [April 14, 2020, 4:10pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/5 "2020-04-14T16:10:49Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![dks2111](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dks2111/32/13974_2.png) [@dks2111](https://discuss.codechef.com/u/dks2111)\
**Post date:** [April 16, 2020, 7:41am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/6 "2020-04-16T07:41:55Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\
**Post date:** [April 16, 2020, 11:24am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/7 "2020-04-16T11:24:07Z")

</div>

@dks2111

> [@dks2111](#):
>
> Please suggest me how to take this approach forward

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)

> [@dks2111](#):
>
> but I don,t know this much mathematics

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 ).

---

<div class="post-metadata">

**Author:** ![patwari26](https://discuss.codechef.com/user_avatar/discuss.codechef.com/patwari26/32/14385_2.png) [@patwari26](https://discuss.codechef.com/u/patwari26)\
**Post date:** [April 25, 2020, 12:17pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/8 "2020-04-25T12:17:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\
**Post date:** [April 25, 2020, 5:31pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/9 "2020-04-25T17:31:32Z")

</div>

@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.

---

<div class="post-metadata">

**Author:** ![bhavyarustgi10](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bhavyarustgi10/32/21376_2.png) [@bhavyarustgi10](https://discuss.codechef.com/u/bhavyarustgi10)\
**Post date:** [May 10, 2020, 11:41am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/10 "2020-05-10T11:41:20Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\
**Post date:** [May 11, 2020, 12:19pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/11 "2020-05-11T12:19:32Z")

</div>

> [@bhavyarustgi10](#):
>
> 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

```auto
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.

> [@bhavyarustgi10](#):
>
> How is a i,j calculated

From the post:

> [@psaini72](#):
>
> 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.

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

---

<div class="post-metadata">

**Author:** ![bhavyarustgi10](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bhavyarustgi10/32/21376_2.png) [@bhavyarustgi10](https://discuss.codechef.com/u/bhavyarustgi10)\
**Post date:** [May 11, 2020, 2:53pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/12 "2020-05-11T14:53:49Z")

</div>

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 !!

---

<div class="post-metadata">

**Author:** ![psaini72](https://discuss.codechef.com/user_avatar/discuss.codechef.com/psaini72/32/254485_2.png) [@psaini72](https://discuss.codechef.com/u/psaini72)\
**Post date:** [May 11, 2020, 4:53pm UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/13 "2020-05-11T16:53:20Z")

</div>

@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.

> [@bhavyarustgi10](#):
>
> Then it has terms with only degree 1 in denominator after Decomposition into Partial Fractions

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](https://en.wikipedia.org/wiki/Partial_fraction_decomposition#Example_3) will help. Ignore the x^2+1 term

---

<div class="post-metadata">

**Author:** ![bhavyarustgi10](https://discuss.codechef.com/user_avatar/discuss.codechef.com/bhavyarustgi10/32/21376_2.png) [@bhavyarustgi10](https://discuss.codechef.com/u/bhavyarustgi10)\
**Post date:** [May 12, 2020, 5:49am UTC](https://discuss.codechef.com/t/tripways-unofficial-editorial/61745/14 "2020-05-12T05:49:49Z")

</div>

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