prithviking98's blog

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

 
 
 
 

»
3 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

Unable to parse markup [type=CF_TEX]

. Using optimal solution frog will jump:
  • Unable to parse markup [type=CF_TEX]

    frog must jump

    Unable to parse markup [type=CF_TEX]

    — greater distance than

    Unable to parse markup [type=CF_TEX]

    ;
  • Unable to parse markup [type=CF_TEX]

    frog must jump

    Unable to parse markup [type=CF_TEX]

    — greater distance than

    Unable to parse markup [type=CF_TEX]

    .

We got a contradiction, so your greedy is correct.