2
$\begingroup$

This is a follow-up to this question: Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

Which algorithm should i use to get minimal possible value of $d(X,Y)$?

I tried do develop dynamic programming algorithm but didn't succeed. In my previous question i was told that this problem is known as unweighted one-dimensional k-center problem. I've looked through some papers on the net but all of them offered the ways to find some particular $Y$. But my current problem seems to be easier: i need only the optimal value of $d(X,Y)$. So i expect the solution to be rather standard and rather easy.

Thanks in advance.

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

$\endgroup$
2
$\begingroup$

Hint: Turn the problem upside down and ask yourself: can I easily check if the answer is less than or equal to $t$?

$\endgroup$
  • $\begingroup$ Unforunately i don't understand how this helps with original problem. Could you please elaborate a bit more on this? $\endgroup$ – Igor Mar 14 '16 at 14:12
  • $\begingroup$ If you know how to answer this question, you can do a binary search on the answer. $\endgroup$ – Mihai Mar 14 '16 at 14:33
  • $\begingroup$ Isn't binary search in such situation applicable only when answer is integer? I can have rational number. $\endgroup$ – Igor Mar 14 '16 at 14:47
  • $\begingroup$ Well no, why would it? In this problem you're required to output only two digits after the decimal point, you're not supposed to output a fraction (even then, sometimes you can binary search for fractions!). $\endgroup$ – Mihai Mar 14 '16 at 15:48

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.