# Finding a partition with minimum “maximal length”

We're given $n^2$ different points in $(0,1)$ : $x_1< x_2 < \dots < x_{n^2}$.

We are required to choose $n$ points $x_{i_1}<\dots<x_{i_n}$ such that the value of $\max\,\{x_{i_1}, x_{i_2}-x_{i_1}, x_{i_3}-x_{i_2},\dots,x_{i_n} - x_{i_{n-1}}, 1-x_{i_n}\}$ is minimal.

It feels a lot like a dynamic programming problem, but I didn't manage to divide it into appropriate subproblems.

Any ideas?

• Keep trying! The only way to learn is to solve problems. – Yuval Filmus Feb 27 '17 at 13:28
• Just to make clear: there is indeed a way to solve it using dynamic programming. – Yuval Filmus Feb 27 '17 at 13:43
• What did you try? What subproblems did you already try? We have some material on how to systematically solve dynamic programming problems here: cs.stackexchange.com/tags/dynamic-programming/info. Please review the material in those links, try some more, and if you're still stuck, edit the question to show what you've tried and what progress you've made. – D.W. Feb 27 '17 at 20:28

## 1 Answer

This problem is slightly misleading in that one might wonder how to use the condition that the number of points to choose from is the square of the number of chosen points. That is actually a distraction.

Here comes an hint:

How about instead of $n^2$, you are given some $m$ different numbers where $m\geq n$? This more general problem is not in any way harder then the original question.

This problem can indeed be solved by dynamic programming efficiently. In case when the previous hint is not enough, here are the subproblems stated explicitly.

Can you compute the following function of integer $w$ and $k$, where $1\leq k \leq w$? $$m(w,k) := \min_{i_0 = 0,\,i_k = w,\,i_1\lt\cdots<i_k} \max\{x_{i_1} - x_{i_0},\,x_{i_2}-x_{i_1},\,\cdots,\,x_{i_k} - x_{i_{k-1}}\}$$ What is the technique? We replace the last item $1-x_{i_n}$ with $x_k - x_{i_{k-1}}$. We can compute subproblem $m(w,k)$ from subproblems $m(w',k-1)$ with $w'<w$. The original problem is just the special case $m(n^2+1, n+1)$ if we set $x_{n^2+1} = 1$.