throwaway_1234's blog

By throwaway_1234, history, 7 years ago, In English

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 ?

Full text and comments »

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

By throwaway_1234, history, 8 years ago, In English

Hello,

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

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

Thanks!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By throwaway_1234, 8 years ago, In English

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?

Full text and comments »

Tags ioi
  • Vote: I like it
  • +23
  • Vote: I do not like it