Suppose given $T= a_1\leq a_2\leq\dots\leq a_n $ that $a_i$ is real number and given a number $k$. we want to find $k$ triples $x_i\leq y_i\leq z_i\in T$ such that $$\sum_{i=1}^ k (y_i-x_i)^2$$ minimized, also each $a_i$ can belong to at most one triple.

How we can solve above problem in $O(nk)$? I think it's possible to use Dynamic programming but i can't find a recurrence relation for my problem. Above problem belong to my final exam that our TA didn't solve it for us and i want how we can solve it.

  • $\begingroup$ What are $x_i$, $y_i$ and $z_i$? Are they to be chosen among $a_1, …, a_n$? In this case, what is the link between the $i$ in $a_i$ and the $i$ in $x_i$ (and others)? Finally, is $k$ an input of the problem? Please clarify your post accordingly. $\endgroup$
    – Nathaniel
    Dec 20, 2021 at 21:48
  • $\begingroup$ Yes $k$ is input. $\endgroup$ Dec 20, 2021 at 21:51

1 Answer 1


Note that to minimize the sum, you can always chose $x_i$ and $y_i$ to be consecutive in $T$. The choice of $z_i$ only obliges you to have enough "big values" after having chosen $x_i$ and $y_i$.

I think you could do some dynamic programming using a function like the following:

For $i = 1$ to $n-1$ and $\ell = 0$ to $k$, define $F(i, \ell)$ as the couple composed of:

  • the set $S$ of $\ell$ values among $\{1, 2, …, i\}$ that minimizes $\sum\limits_{j\in S} (a_{j+1}-a_j)^2$;
  • the number of values that still need to be chosen among $\{a_{i+1}, …, a_n\}$ for $z_1$, …, $z_i$.

The second point is a bit informal and corresponds to the "big values" still needed after chosing as much as possible among $\{a_1, …, a_i\}$.


Your Answer

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

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