mahmoud_arafa's blog

AIM Tech Round 3 (Div. 2) — Problem B
By mahmoud_arafa, history, 8 years ago, In English

Hello,

Can anyone help me with a tutorial for this problem?

I had an idea using binary search. We can sort the array, then each time we look for the next nearest point using binary search. After that we remove that point from the points list and then we look for the next nearest point and so on. But the drawback is the 'erase' step, which takes O(N) complexity. That changes overall complexity from O(N log N) to O(N * [log N + N]) which is O(N^2).

So any help here please?

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

Comments Comments (4)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'll explain my solution, which works to find the optimal way to visit k points, not necessarily N - 1.

  • Sort all the points.
  • Find the first point that is greater than P, call it m.
  • Calculate li = the cost to visit i points to the left of m and ri = the cost to visit i points to the right of m (including m). These can be calculated easily in O(N) with just a simple subtraction.
  • Iterate over all values x from 0 through k, the number of points to the left we're gonna visit. Then we have two choices: go first to the left or go first to the right. If we go first to the left, the cost will be 2 * lx + rk - x. If we go first to the right, the cost will be lx + 2 * rk - x.
  • Keep the minimum among all costs found in the previous step.

Total complexity is O(NlogN) because of the sorting.

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

    Ok, but how this guarantees the optimal solution?

    I mean may be there is a situation where the points are sorted and the optimal solution is like:

    Move to the point right of p, move right again, move to the point left of p, then go to the 3rd point right of p, then left again and so on. Your idea is moving x points to left then k-x to the right (that doesn't involve alternating between left and right directions).

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

      Whatever you do, in the end you will walk a segment. By doing it the way I explained, you'll walk some subsegment at most twice, but on the other hand, if you walk left, then right, then left, and so on, there will be subsegments where you walk 3 times or more, and that's clearly not optimal. To prove it, suppose there's a subsegment [A, B] where you walk 3 times, whatever you do to the left of A and to the right of B, you can do it the first time you're there, there's no reason to do A, B, A or B, A, B.

      → Reply