CareerCup

Number of paths for part one = m ^ layers
Number of paths for part two = sum(i = 1 to layers) (m ^ i)
Where 'layers' is the number of layers considered i, i+1, etc

Edit:
The above approach is incorrect. After thinking about it some more, the actual count is

f(n) = m + m ( f (n -1) ) + f (n - 1)  when n > 0,  0 otherwise

where n is the number of layers.

Which roughly means
m possible paths if the only middle layer is layer 'n'
m ( f(n - 1) ) possible paths if layer 'n' is considered part of the path in combination with all the other layers < n
f(n -1) possible paths if layer 'n' is not part of the path using all the other layers < n

This simplifies to

f (n) = m + f (n -1) (m + 1)

1) m**n
2) (m + 1) ** (n - 2) * m * m if n > 1 else m

The answers are m^n and (m+1)^n respectively. It can be calculated by mathematical induction.

This can be solved using DFS, right?

Part one: m^n
Part two: m^n + m^(n-1) + m^(n-2) + ... m^(n-n) .... (Mathematical induction)

The solution is Dynamic programming the you'll calculate the number of path from node i to the sick no suppose you are analysis a edge i -> j, here you have calculate from j to sink the the number of path from i to j is D[j], so the total number of path from i to sink is the sum of the path for all children of node i. Here is the code for a better understatement because my english is a mess lol.
int D[1000] Fill it with -1
int calc(int node){
if(node == sink) return 1;
if(D[node==-1]){
D[node] = 0;
for(over all children of node called next)
D[node] += calc(next);
}
return D[node];
}


the solution is calc(source)

Part one is of course m^n.
Part two is sum_(i in 1..n)(m^i*(n choose n-i)).
Imagine paths that jump one level. The number of paths are in m^(n-1), but only for one level, hence you need to multiply by n (which is n choose 1).
Now imagine paths that jump two levels. The number of paths (if you fix which levels are being jumped) is m^(n-2), and this must be multiplied by the number of choices of the two levels to jump, that is n choose 2.
And so on and so forth :)

Solution:
- f(0) = 1
- f(1) = m
- f(n) = m*f(n-1) = pow(m, n);
- f(i, j) = f(i-1) * f(m-j) = pow(m, n+i-j-1), where i < j and i and j <= n.(a jump connection i, j)

See more here: cpluspluslearning-petert.blogspot.co.uk/2015/08/find-number-of-paths-from-source-to.html

First question, the total paths are m^n.
Second part, for each edge from level i to level i+k, there are m^(n-k-1) paths that use this edge, so this value is added to the total number of paths.

The answer will be -

m^2 + m^3 + m^4 + .... + m^n

How?

Let's consider the base case first -
n = 1, paths = m
n = 2, paths = m(m)
i.e. only possible paths are m*m
n = 3, paths = m(m + m(m))
i.e. we have three layers -
1. either directly reach the last layer (3nd layer) from first m nodes, paths = m*m
2. or reach via middle layer (1st layer), paths = m*m*m
so total paths = m*m + m*m*m
similarly, for n = 4
4 layers, 4 options
1. reach directly to 4th layer = m*m*m*m
2. reach via second last layer (3rd layer) = m*m*m
3. reach via second layer = m*m
total paths = m*m + m*m*m + m*m*m*m

Couldn't be problem attacked in the following way? :
There are N levels by M nodes each( for simplicity now I ignore source and sink levels ). So we have 2 ^ N - 1 possible ways to find a way between first and last level (no taking into account when path go only through nodes sink and source). For each combination of levels L, there are M^K ways to get node, where K is count of all set bits in L.So number of ways between first and last level would be : for (int l = 1; l< 2^n ;l++) sum+=m^k; where k is number of set bits in l. We now have to take into account sink and source nodes , which provides us addtional ways - > m^2*sum + 1 if n > 1 or m+1 if n = 1- this is total ways.

Couldn't be problem attacked in the following way? :
There are N levels by M nodes each( for simplicity now I ignore source and sink levels ). So we have 2 ^ N - 1 possible ways to find a way between first and last level (no taking into account when path go only through nodes sink and source). For each combination of levels L, there are M^K ways to get node, where K is count of all set bits in L.So number of ways between first and last level would be : for (int l = 1; l< 2^n ;l++) sum+=m^k; where k is number of set bits in l. We now have to take into account sink and source nodes , which provides us addtional ways - > m^2*sum + 1 if n > 1 or m+1 if n = 1- this

I used inductive logic to get an answer of m^n for part 1 and m (m+1)^(n-1).
This assumed you can only get to the sink from row i=n. But the source can jump to any i.

To check: assume m=10.
N=1->10
N=2->1 + 10 *1 +10*(10+1)
N=3->13310
etc.

The second part can be solved with dinamic programming, i think this function does the job

long long int NumberOfWays(int n, int m, vector<pair<int, int> > edges){
          vector<long long int> levels (n, 0);
          sort(edges.begin(), edges.end());
          v[0] = m;
          int j=0;
          for (int i=0;i<n-1;i++){
                v[i+1] +=v[i]*m;
                while(j<edges.size() and edges[j].first==i){
                      v[edges[j].second] += v[i]*m;
                       j++;
                 }
           }
          return v[n-1]*m;
}

long long int NumberOfWays(int n, int m, vector<pair<int, int> > edges){
          vector<long long int> levels (n, 0);
          sort(edges.begin(), edges.end());
          v[0] = m;
          int j=0;
          for (int i=0;i<n-1;i++){
                v[i+1] +=v[i]*m;
                while(j<edges.size() and edges[j].first==i){
                      v[edges[j].second] += v[i]*m;
                       j++;
                 }
           }
          return v[n-1]*m;

}

I think this a DP problem. Define dp[i] is the number of paths from source to level i, then we have dp[i] = m * (dp[1] + dp[2] + ... + dp[i - 1]) = m * dp[i - 1] + m * (dp[1] + dp[2] + ... + dp[i - 2]) = m * dp[i - 1] + dp[i - 1] = (m + 1) * dp[i - 1]

Isn't the second question solved with binomial coefficients?