To solve UVa problem 11364 (Parking), it would be beneficial to know that the minimal distance Michael has to walk is simply twice the distance from the farthest store to the nearest store. For example, consider the following setup:

A________B______________C_____D

X______________________________

A, B, C and D are the stores while X is Michael’s car. To get to all the stores and return to his car, Michael would have to walk:

A to B

B to C

C to D

D to C

C to B

B to A

In essense, the total distance he would have traveled would be just twice the distance from A to D.

Consider now the following setup:

A________B______________C_____D

__________________X____________

For Michael to get to all stores and return to his car, he would need to walk:

X to B

B to A

A to B

B to X

X to C

C to D

D to C

C to X

Again, analyzing this series of walks, it is simply twice the distance from A to D.

Hence to compute the minimal distance given a series of stores to walk to, simply find the nearest store and the farthest store, get their difference and then multiply the difference by 2.

thnx (Y)

ReplyDelete