pedromnasc's blog

By pedromnasc, 10 years ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

By pedromnasc, 10 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +17
  • Vote: I do not like it

By pedromnasc, 11 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it