askhelper's blog

Help for POI 2018 Round #1 problem: Stone
By askhelper, 7 years ago, In English

Hello, all! I need your help for this problem. Basically, we have n vectors originated in (0, 0) and we are to find a subset of these vectors such that length of their sum is maximum.

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

Comments Comments (3)
| Write comment?
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it +20 Vote: I do not like it

Try to think about some optimal solution (and some final point). Which vectors should we use to reach this point?

→ Reply
  • »
    »
    7 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    That makes me think about some kind of dp. For example, if the answer is (x, y) then we need to get $$$(x, y)$$$ or $$$(x - a[1].x, y - a[1].y)$$$ from the vectors 2 to n.

    → Reply
    • »
      »
      »
      7 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      What I'm trying to suggest is that the chosen vectors in the optimal solution have some specific property. Finding this property should later lead to a pretty straightforward solution.

      → Reply