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) = ai*x2 + bi*x1 + ci
Now it is given that ai >= bi >= ci >= 0
Thus, *ƒ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 (ai + bi + ci)*(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]+(ai + bi + ci)*(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]+(ai + bi + ci)*(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: