[CCC-HK 17S4] Cost

Difficulty Ratings

Idea Creativity: 4/5
Techniques Used: 2/5
Implementation : 2/5
When I asked people how to solve this problem they said its treap, but when i asked for details they run away smh... It is not a treap problem...

Statement

You are moving in a Cartesian plane. At the beginning you are at $(0, 0)$, and your target is $(n, m)$. Once you are at $(x, y)$, you can move to the point $(x, y + 1)$ with the cost $A_x$, or move to the point $(x + 1, y)$ with the cost $B_y$. Given the sequences $A$ and $B$, your task is to find out the minimum cost from $(0, 0)$ to $(n, m)$. $n,m \le 1e6$

Solution

So the problem is equivalent to having costs on each line and find shortest path. Obviously it is beneficial to walk on lines with small cost. Lets define $x_{min}$ to be the x-coordinate with smallest cost, and $y_{min}$ to be the y-coordinate with smallest cost (tiebreak arbitarily). Then, we can conclude that the optimal path passes through $(x_{min},y_{min})$. It is not hard to observe, you just do some replacement argument.

So, with the above observation, it is intuitive to think of divide and conquer solutions. However, this is not going to bring you everywhere (if it does tell me). We need other directions. Lets find more points that the shortest path must pass through. To this, we introduce a transformation:
We pick any real number $Z$ (can be negative):
For each $x_i$, do $x_i:=x_i+i*Z$
For each $y_i$, do $y_i:=y_i+i*Z$
Then, we realise that the costs of all possible paths will decrease by $Z \times n \times m$!!! That means, the shortest path on original graph will also be the shortest path after transformation. It is also not hard to see why this is true graphically.

So, what is the use of this transformation? It appears that, after the transformation, $x_{min}$ and $y_{min}$ will change, and we get a new point that we must pass through! Moreover, if we built a convex hull for points $(i,x_i)$ and another convex hull for points for $(i,y_i)$, then we can find out all turning points in our shortest path! Then you just have to compute the cost accordingly and you can solve the problem in $O(n+m)$.

Comments

I am very excited when i came up with this. Maybe someone can come up with a way that looks less random voodoo..?