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

Автор throwaway_1234, история, 7 лет назад, По-английски

I thought of this problem and I was wondering if there is any polynomial time solution?

Given a weighted tree of N nodes, pick K nodes such that sum of distances from each node to the nearest picked node is minimized.

For K = 1, the answer is the centroid of the tree. What about K > 1 ?

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

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

Автор throwaway_1234, история, 8 лет назад, По-английски

Hello,

Can someone from China help me find the problem referenced here, and what it says?

BZOJ 3850 贪心,请参照国王游戏||皇后游戏。

Thanks!

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

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

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

Does anyone know of problems which have solutions similar to that of IOI 2014 Friend where you try to use something like Induction.

For example in that problem, we try to remove each node and changing the remaining graph somehow so that the answer doesn't change.

One example I know is: http://main.edu.pl/en/archive/oi/12/dwa

Does anyone know of any other problems?

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

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