Maximizing the Expected Steps of a Random Walk in a Directed Graph

We have a directed graph with n nodes (numbered 1 through n). Initially, for every i = 1,2,…,n−1 there is an edge from node i to node i+1. You are allowed to add m extra directed edges (the added edge may go from any node to any node; multiple edges and self‐loops are allowed) but you cannot add any extra edge originating at node n (since node n is the destination).

A random walker starts at node 1 and at every step chooses uniformly at random one out‐edge from the current node. The process terminates immediately when node n is reached. Your task is to add the extra edges (i.e. choose their start and end vertices) so that the expected number of steps until termination is maximized.

More precisely, if a node x has d out‐edges then the walker chooses each with probability 1/d. (All choices are independent.)

It can be shown that when m extra edges are added optimally the maximum expected number of steps is a rational number. (Under the optimal construction the absorption probability is 1 – the walker eventually reaches node n almost surely.)

Your task is to compute the maximum possible expected number of steps achievable by adding exactly m extra edges optimally.

All formulas in this statement are given in ( \LaTeX ) format. For example, the initial edges are given by

[ \forall; i\in{1,2,\dots,n-1},\quad i\to i+1. ]

and the random–walk step is defined by

[ E(x)=1+\frac{1}{d} \sum_{y:, (x\to y)\in E}E(y), \quad \text{for } x\neq n, \qquad E(n)=0. ]

inputFormat

The input consists of two integers n and m on a single line, where 2 ≤ n ≤ 10 and 0 ≤ m ≤ 10. Here n is the number of nodes in the graph and m is the number of extra edges you may add.

outputFormat

Output a single number – the maximum expected number of steps from node 1 to node n under an optimal choice of extra edges. It is guaranteed that the answer is a rational number. For this problem, print the answer exactly (do not round).

sample

3 0

2