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?

  • $\begingroup$ Keep trying! The only way to learn is to solve problems. $\endgroup$ Feb 27, 2017 at 13:28
  • $\begingroup$ Just to make clear: there is indeed a way to solve it using dynamic programming. $\endgroup$ Feb 27, 2017 at 13:43
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 27, 2017 at 20:28

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.