Need help for the problem "Icy Roads of Nomel" regarding convex hulls

Revision en5, by SamuraiBebop, 2023-06-23 18:13:15

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

Unable to parse markup [type=CF_MATHJAX]

grid with row costs

Unable to parse markup [type=CF_MATHJAX]

and column costs

Unable to parse markup [type=CF_MATHJAX]

. You are at $$$(1,1)$$$ and want to go to

Unable to parse markup [type=CF_MATHJAX]

by repeatedly performing one of the two following operations when you are at $$$(x,y)$$$:
  • Move to

    Unable to parse markup [type=CF_MATHJAX]

    with a cost of $$$a_x$$$;
  • Move to

    Unable to parse markup [type=CF_MATHJAX]

    with a cost of

    Unable to parse markup [type=CF_MATHJAX]

    .

You want to know what is the minimum total cost you can achieve. The constraints are

Unable to parse markup [type=CF_MATHJAX]

, 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 like performing some kind of greedy on two lower convex hulls formed by points

Unable to parse markup [type=CF_MATHJAX]

and points

Unable to parse markup [type=CF_MATHJAX]

. However, I have no idea how to prove this. Could someone please help? Many thanks in advance!

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)