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

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

Hey! Can anybody help me with a solution to this? We have an array of pairs [ (x1,y1) , (x2,y2), ... , (xn,yn) ]. Initially, we are at the coordinates (0,0). We can use whatever pair from the array (maximum one time) to move from the actual position (a,b) where we are to (x + xi, y + yi). The numbers from the array's pair are between [-10^4, +10^4]. Which is the maximum distance we can move from the origin (0,0) after using some of these pairs from the array? We have a maximum of 2000 pairs. I am grateful to those who brighten me.

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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

I don't know why this blog is (EDIT: was) being downvoted; it's a pretty good problem, and has a pretty interesting solution (described on math stackexchange here).

Essentially, this problem asks you to pick some subset of 2D vectors such that the norm of the sum is maximal. The key observation is as follows: if you have some optimal solution $$$v$$$, how can you characterize the vectors you're including and excluding? The short story is that all the vectors you are including must have positive dot product with $$$v$$$, otherwise you could remove them and increase the norm, and all the vectors you're excluding must have negative norm, otherwise you could include them and increase the norm. Thus, all the included vectors lie in the halfplane normal to $$$v$$$. There are $$$n$$$ of these halfplanes, so you can iterate through all of them and try adding all the vectors inside for an $$$O(n^2)$$$ solution.

EDIT: $$$O(n^2)$$$ seems sufficient for your problem, but I guess you can optimize it to $$$O(n \log n)$$$ by sorting radially and keeping track of front/back pointers.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Can you provide a link to the question? I would like to try this out, sounds like a really good problem.

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I've seen this problem most recently here: https://atcoder.jp/contests/abc139/tasks/abc139_f with $$$N = 100$$$. I think the ABC139 discussion thread on CF has more versions.