Let \(f(z)\) be the probability that the answer is not less than \(z\). Then, we can find the probability by integrating \(f\), so let us try to find \(f(z)\).

We can solve the problem for a fixed \(z\) as follows. Let us consider the \(N\) intervals \([x_i-(i-1)z,x_{i+1}-(i-1)z]\). Then, we have to find the probability that the real numbers \(y_i\) chosen uniformly at random from those intervals satisfy \(y_1<y_2<\ldots<y_N\). Let us sort the endpoints of the intervals and let \(v_1<v_2<\ldots<v_{2N}\) denote them. Then, we have the following DP solution:

• \(dp[i][j][k]=\) (The probability that \(y_{i-k}< v_j < y_{i-k+1} < \ldots < y_i \leq v_{j+1}\) when the values up to \(y_i\) are chosen.

This makes us able to compute the transitions. The important transition is \(dp[i][j][k] \rightarrow dp[i+1][j][k+1]\), where the “weight” of the transition is the probability where \(y_{i+1}\) is in \([v_j,v_{j+1}]\), multiplied by \(1/(k+1)\), which corresponds to the change from the probability that \(k\) values are in ascending order to the probability that \(k+1\) values are in ascending order.

With this DP, we are now able to find the answer for a fixed \(z\) in \(O(poly(N))\) time.

Now, let us unfix \(z\). The values \(v_i\) are all in the form \(-az+b\). Also, the result of the DP above is a polynomial of variables \(v_i\). In the end, for sequences \((v_1,v_2,\ldots,v_{2N})\) that are the same when seen as polynomials of \(z\) whose degrees are \(1\), the result of the DP is the same polynomial of \(z\). Thus, for unfixed \(z\), we focus on the moment when the values \(v_i\) change (the magnitude relation of the polynomials changes), and do the DP above for parts where they do not change. If we store the values in the DP table as polynomials of \(z\), or evaluate the result for some number of \(z\) and use polynomial interpolation, we can integrate \(f(z)\) in the end.

Since the values \(v_i\) change most \(O(N^2)\) times, we now have a solution that works in \(O(poly(N))\) time. Our intended solution is \(O(N^6)\), but solutions such as \(O(N^7)\) will also pass if the constant factors are not too big.