UVA 10037: Bridge
Created at 2016-05-07T03:16:20.000Z

Problem definition

I had no idea how to achieve optimality, so I consulted two references about this problem:

Both references mentions that:

When the number of people is more than or equal to 4, the problem can be broken down into

  • move slowest 2 people to the other side,
  • repeat this until the number of people is less than 4.

Technically speaking, this "break down problem" is a crucial step to prove the optimality of the algorithm by induction, which is not obvious for me to understand intuitively.

So, I tried to formalize and prove a statement, but I failed. Here is some of notes about this.

Locally best strategy

2016-05-07 21.07.39

Compositionality of best strategies

2016-05-07 21.08.48

Rests are my crappy notes:

2016-05-07 21.09.11

2016-05-07 21.09.52