Proof for the problem "Icy Roads of Nomel" regarding convex hulls

Revision en3, by SamuraiBebop, 2023-06-23 17:23:13

I recently came across this problem Icy Roads of Nomel from Petrozavodsk Summer-2013. Gennady Korotkevich Contest 1. The problem statement is simple:

You are given an $$$(n+1)\times (m+1)$$$ grid with row costs $$$a_1,a_2,\dots,a_{n+1}$$$ and column costs $$$b_1,b_2,\dots,b_{m+1}$$$. You are at $$$(1,1)$$$ and want to go to $$$(n+1,m+1)$$$ by repeatedly performing one of the two following operations when you are at $$$(x,y)$$$:

  • Move to $$$(x,y+1)$$$ with a cost of $$$a_x$$$;
  • Move to $$$(x+1,y)$$$ with a cost of $$$b_y$$$.

You want to know what is the minimum total cost you can achieve. The constraints are $$$1\leq n,m\leq 5\times 10^5$$$, and costs are of magnitude $$$10^9$$$.

This does look like Problem 1 and Problem 2, where one usually utilizes the convexity of costs to speed up the dynamic programming. However, here the costs are arbitrary and there is absolutely no convexity.

From reading some code from the Atcoder mirror, (I think) the solution looks likes performing some kind of greedy on two lower convex hulls formed by points $$$(i,a_i)$$$ and points $$$(j,b_j)$$$. However, I have no idea how to prove this. Could someone please help?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English SamuraiBebop 2023-06-24 06:46:30 7
en5 English SamuraiBebop 2023-06-23 18:13:15 14
en4 English SamuraiBebop 2023-06-23 17:28:55 27
en3 English SamuraiBebop 2023-06-23 17:23:13 0 (published)
en2 English SamuraiBebop 2023-06-23 17:23:00 2 Tiny change: 'f $b_y$.\nYou want' -> 'f $b_y$.\n\nYou want' (saved to drafts)
en1 English SamuraiBebop 2023-06-23 17:19:31 1415 Initial revision (published)