**Problem:** DP Made Easy

**Setter:** Abhishek Kanhar (abhikalpu_123)

**Tester and Editorialist:** Samarth Joshi (spj_29)

**Difficulty:** Easy-Medium

**Solution:**

Let us consider the First dimension as the X-axis and the Second dimension as the Y-axis.

From now on I will refer to a point in the first dimension as the X-coordinate and in the second dimension as the Y-coordinate.

Let us have a look at the transitions in the x-coordinate.

**DP[Xi][yi]=min(DP[Ti][yi])**; where “T” is the set of x-coordinates which are reachable from Xi.(given as transitions in the question).

Now it is easy to see that transitions in the X-coordinate are independent of the Y-coordinate.

That is, a transition from **(X1,Y)** to **(Xk,Y)** will have the same cost for any Y.

We can interpret the X-coordinates as nodes of a graph, given undirected weighted edges between some pairs of nodes.

Now let us have a look at the transitions in the y-coordinate.

**DP[i][j] = min ( DP[i][j-d] + ƒi(d) )**

It can be seen that the cost of transition in this dimension depends on the current value of the X-coordinate since the function F_i depends on the value of i (which is X here).

It makes sense to always keep “d” in the above transition = 1.

Why?

Let’s say we keep **d=k (k>1)** for a fixed **“i”**.

ƒi(x) = **a _{i}*x^{2} + b_{i}*x^{1} + c_{i}**

Now it is given that

**a**

_{i}>= b_{i}>= c_{i}>= 0Thus, *

*ƒi(k) >= ƒi(1)*.

*k*Since the DP is min of all possible transitions,

**“d”**should always be one.

Let us try to model the entire grid as a graph. Every point **(x,y)** is a node with certain weighted edges connecting it to other points. Note that edges connecting two points with a different Y-coordinate are directed with the Y-coordinate value always increasing along the edge. This is simply due to the way the transition is given in the Y-direction. Since we have shown that “d” should always be “1”, if there is an edge from **(X,Yi)** to **(X,Yj)** then **Yj** must be **Yi+1**.

Now the problem reduces to finding the shortest path between **(1,1)** and **(N,N)**. (Forget about updates for now).

Let us show that to move from Y=1 to Y=N, we don’t have to change the X coordinate, that is if we want to go to Y=N from Y=1 then the X coordinate will be the same for every intermediate Y coordinate.

Lets us say we were at some **P1=(Xi,1)** then we go to **P2=(Xi,Yj)** and then to **P3=(Xj,Yj)** and then to **P4=(Xj,N)** and then to **P5=(N,N)**.

Note that P2 to P3 involves transition in the X-coordinate. We have shown that such a transition is independent of the Y-coordinate. Thus the cost of X transition is not really changing.

So, if it was optimal to change X-coordinate at some intermediate Y, why not change it at Y=1 itself? Since the cost of Y transition then would depend on that X-coordinate value.

We can extend this idea to lead us to the fact that the optimal path will always be of the form

**(1,1)->(Xi,1)->(Xi,N)->(N,N)**.

Cost of **(Xi,1)** to **(Xi,N)** is simply (**a _{i} + b_{i} + c_{i}**)*

**(N-1)**. (Why? Because “d” = 1).

So all we need to do is find the length of shortest paths from X=1 to X=i for every i <= N (let us call it **Dist[i]**).

And between X=i and X=N for every i<=N (Which is simply the shortest path from X=N to X=i).(Let us call it **Dist_1[i]**).

Both these arrays can be built using the well known Dijkstra’s algorithm.

Then the final answer will be Min (**Dist[i]**+(**a _{i} + b_{i} + c_{i}**)*

**(N-1)**+

**Dist_1[i]**) For all

**i<=N**.

Dist and Dist_1 arrays do not change with the updates.

It is now easy to see that we can maintain a multiset of **G(i)=****Dist[i]**+(**a _{i} + b_{i} + c_{i}**)*

**(N-1)**+

**Dist__1[i]**to handle the updates. In every update for

**‘i’**th function remove

**G(i)**from the multiset and insert new

**G(i)**back. The new answer is simply the minimum value in the multiset.

Setter Code:

```
[4]
Tester Code:
```