prithviking98's blog

By prithviking98, history, 5 months 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 ?

 
 
 
 

»
5 months 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.