I_LOVE_ROMANIA's blog

Geometry problem

By I_LOVE_ROMANIA, history, 4 years ago, In English

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.

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

»
4 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    thank you. I did not have a link. one of my friends told me about this problem but he had not a solution, neither I

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks mate!

    → Reply