prithviking98's blog

Proof for a greedy solution
By prithviking98, history, 6 years ago, In English

the problem is UVa 11157 — lazy frog

i understand that the subproblem is to find the minimax jump between two closest big stones. but how to prove that alternating jumps on the small stones is the best strategy ?

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

Comments Comments (1)
| Write comment?
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Let us prove this by contradiction. Let this not be the optimal strategy and the maximum jump is Mi - 1 → Mi + 1. Using optimal solution frog will jump:

  • Mi - 1 → Mi frog must jump Mi - 2 → Mi + 1 — greater distance than Mi - 1 → Mi + 1;

  • Mi → Mi + 1 frog must jump Mi - 1 → Mi + 2 — greater distance than Mi - 1 → Mi + 1.

We got a contradiction, so your greedy is correct.

→ Reply