Chenliang Xu
BAN USERWhen we shift a solution to the right by one seat, every person who moved right have to move one extra step, no matter how many steps one moved; and everyone who were moving left can save one step. All the persons who were not moving will move one extra step when we shift to the left or right by one step.
If the total saving is larger than the total cost, one can improve the solution by shift solution to the left or to the right. Otherwise, it is the optimized solution.
It is entirely correct. If it's possible in each coordinate, that means a feasible coordinate, x[0], ... x[n-1], and y[0], ..., y[n-1], then (x[0], y[0]), ..., (y[n-1], y[n-1]) is a solution to the original 2D question.
- Chenliang Xu November 06, 2014@gudujarlson, please see a proof below.
- Chenliang Xu November 06, 2014@gudujarlson points out median is the fast way to go. I'll give a
proof here.
Let's start with two observations,
- Some persons move left, some persons move right. They should never
move cross each other, otherwise they can just take the new seat of
each others, reducing the total moves.
- For two persons move the same direction, there is no need for one
person to pass the other one. They can switch their new seats,
resulting the same number of move.
Hence, we can find an optimized solution, such that the order of seats
were kept. For a solution that l persons on the left move right, m
persons in the middle don't move, and r persons on the right move left.
- If l > m + r, we can improve the solution by shift left by one seat
- If l + m < r, we can improve the solution by shift right by one seat
- Otherwise ( |l - r| < m ), we reach a local minimal.
Then it is easy to show that a solution constructed by aligning the
median meet the requirement.
If you found the proof complex, you may want to compare it with a
classical question: If we want to move all the people to one seat,
which is the best seat?
After remove the first line, we don't have a good reason to remove another one. It's hard to argue both of them should not be in the solution. So it's hard to remove every line.
- Chenliang Xu November 07, 2014Instead of selecting starting point, we can select starting segment. Select one segment, consider all the segment intersecting with it. If all the intersected neighbors are not in the solution, then it must be in the solution. So we need to try all the neighbors and itself as starting segment, and find the best solution.
To improve speed, we may want to start with a segment with small number of neighbor. But I'm not quite sure how difficult it is compared to the original question.