Given numbers $0<x_1<x_2< \dots<x_{n^2}<1,$ for every subset of $n$ of them $x_{i_1}<x_{i_2}< \dots<x_{i_n},$ let us consider the size: $$\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}\}$$

Give an algorithm to find the minimal size that subset of $n$ numbers can achieve.

My thoughts:

I would like to use dynamic programming.

I started by defining the following:

$$d(1) = x_{i_1}, d(j)=\max\{d(j-1), x_{i_j}-x_{i_{j-1}}\}$$

The solution to the problem will have to minimise the following:


I got stuck here, and my question is how can I continue to finish the solution.

Any help is appreciated.

  • $\begingroup$ I can give you some advice to get on your way. First step to solving this as a dynamic program is defining the problem in such a way that solving a smaller version of that problem allows you to quickly find the solution to the larger problem. The dynamic programming solution to finding the edit distance of two strings has some similarities with this problem, so you could have a look at that for ideas: geeksforgeeks.org/dynamic-programming-set-5-edit-distance $\endgroup$ – Simon Prins Jun 26 '18 at 13:42

A dynamic programming approach would be: $f (p, k)$ is the minimum size when we considered prefix $\{x_1, x_2, \ldots, x_p\}$, and selected exactly $k$ items from it, the last one being $x_p$. We add sentinels $x_0 = 0$ and $x_{n^2 + 1} = 1$ for our comfort.

Base: $f (0, 0) = 0$.

Transitions: $f (p, k) = \min\limits_{q = 1, 2, \ldots, p - 1} \max \left\{f (q, k - 1), x_p - x_q\right\}$.

Answer: $f (n^2 + 1, n + 1)$, the point number $n + 1$ being the added value $x_{n^2 + 1} = 1$.

In total, this takes $O(n^2)$ to calculate a single $f (p, k)$, and there are $O (n^3)$ such values, so the approach will take $O(n^5)$ time and $O(n^3)$ memory.

The memory could be reduced to $O(n^2)$ by calculating iteratively, like:

for k = 1, 2, ..., n+1:
    for p = 1, 2, ..., n^2 + 1:
        calculate f (p, k)

And storing $f (p, k)$ only for the current and the previous values of $k$ at every moment: the storage strategy can be to store $f (p, k)$ in f[p][k mod 2].

The time could be perhaps reduced to $O(n^3)$ by altering the function to optimize the $O (n^2)$ transition cost to something like $O (1)$ amortized. But instead, let us consider another approach.

Say we want the answer to be at most $s$. We can then greedily construct a subset. First, let $x_{i_1}$ be the greatest possible: $i_1 = \max i : x_i \le s$. Next, let $x_{i_2}$ be the greatest possible: $i_2 = \max i: x_i - x_{i_1} \le s$. Then define $i_3 = \max i: x_i - x_{i_2} \le s$, and so on. If this leads to $x_{i_n}$ such that $1 - x_{i_n} > s$, the answer can't be $s$. Otherwise, we just constructed a subset of $\le n$ elements with the answer at most $s$. As the value $i$ is always increasing, for a given fixed value $s$, the check whether $s$ can be the answer takes $O (n^2)$ time and $O (1)$ additional memory.

What's left is to run a binary search over the value $s$, and for each candidate $s$, execute the greedy algorithm above. The number of binary search iterations can be $\log n$ (there are $O (n^4)$ possible candidates for $s$), or $\log C$ where $C$ is the required precision. For example, if all $x_i$ are integers from $0$ to $L$, we have a binary search over integers from $0$ to $L \cdot n^2$, so it will complete in $O (\log (L \cdot n^2))$.

In total, this approach takes $O (n^2 \log n)$ or $O (n^2 \log C)$, which is better than an optimized dynamic programming approach would achieve.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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