Блог пользователя pedromnasc

Автор pedromnasc, 10 лет назад, По-английски
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор pedromnasc, 10 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

Автор pedromnasc, 10 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится