How can i solve this problem: https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4681 ? I only think on slow DP solution.

How can i solve this problem http://acm.timus.ru/problem.aspx?space=1&num=1103 ? I can think in an approach O(n^4), that's far from enough..... Basically i have N points and i want to draw a circle with 3 points on the edge, (N-3)/2 points inside and (N-3)/2 points outside of the circle. What are the points on the edge?

Hello,

I was thinking on problem of 1D clustering. I have n points and i want to partition them in k sets minimizing the within-cluster sum of squares, like here: http://en.wikipedia.org/wiki/K-means_clustering#Description. I can solve this problem using dynamic programming in O(n^2 * k). Can i improve this time? Can i use divide and conquer optimization? If yes, how to proof it?

Thanks!

EDIT: Here's a paper that explains the standard dynamic programming O(n^2 * k): http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf