# LTIME74 - Weak test case OR I misunderstood the approach?

I am talking about PROFTIP question.

What I thought of is there must be some state j to which we first go and then buy the fuel for the rest of the journey from the state j.

My dp[i][j] denotes the minimum cost of fuel needed to go from state i to state j.
So, my dp transition is dp[i][k] = dp[i][j] + fuel[j] * dist[j][k], where dist[i][j] is the minimum distance from state i to state j.

But, when I submitted this, it fails on some of the test cases.
So, then I tried dp[i][k] = dp[i][j] + dp[j][k] and it passed!

I didnâ€™t understand whether I am going wrong OR the test cases are weak.

4 Likes

Interesting. I will get back to it in a while. Meanwhile if you want the pdf of (unapproved) editorial, I can provide you that if it helps. Tester and Setterâ€™s solution use â€śdp[i][k] = dp[i][j] + fuel[j] * dist[j][k],â€ť thing itself, so I think their approach and solutions are correct.

1 Like

And if you can give the unapproved solution then may be I can analyze their solution and approach

Write me an email - I have it on PC. I will do the needful. (I dont want you to share your email publicly )

4 Likes

See hardworking editorialist.
Writing editorial for last question + replying on discuss + replying on FB + replying on mail + mailing editorials to people + â€¦

6 Likes

Hi

I was thinking almost the same idea and failed in some submissions then i read this post, i got accepted and i understood why changing the transition you mentioned above works.

Lets calculate W[ i ][ j ] := the minimum cost needed to go from node i to node j if you can only buy fuel at node i, then the answer is W[ i ][ j ] = fuel[ i ]*dist[ i ][ j ].

And you can imagine this as a completed graph wich each edge is weighted with W[ i ][ j ] and if you calculate the minimum path between nodes P and Q you will get the answer for the problem.

And this is the reason of the change in the transition.

Hope this approach helps you, because i was making the same idea.

My submission

sorry but I didnâ€™t understand your idea .

If possible can you please explain with a small example? OR can explain it a little more?

I will do my best trying to explain it XD

The answer to the problem can be modeled as a subsequence of nodes P = x_1 , x_2 , ... , x_k = Q such that you bought the minimun fuel needed in node x_i to reach node x_{i+1}. Note that x_i is not neccesary adjacent to x_{i+1}.

For example, in the test case of the problem the subsequence will be 1 , 3 , 4 which means that you bought the minimun fuel needed in node 1 to reach node 3 and then you bought the minimun fuel needed to reach node 4.

Why can we do this? Because if we donâ€™t buy the minimun fuel needed in x_i to reach x_{i+1} we have two cases:

1. If fuel[ x_i ] < fuel[ x_{i+1} ] then we should have bought more fuel in node x_i instead of buy in node x_{i+1} to continue our path.

2. If fuel[ x_i ] > fuel[ x_{i+1} ] then we should have bought the minimun fuel needed to reach x_{i+1}.

So with this, we can calculate W[i][j] as i said before. Note that this is a complete directed graph, because W[i][j] is not necessary equal to W[j][i].

And with this in mind and the first part, the solution to the problem is the minimum distance between P and Q in this new graph described by W[i][j], because this will represent the sequence.

Sorry brotherâ€¦just one more thing I want to clearâ€¦

I am not saying that we brought all the fuel at p itself while going from p to q. Rather, I would go to some node j (which have the less cost of fuel probably) and we continue our journey from j to q by buying all required fuel at state j itself.
Now, this process is recursive as while going from p to j, I donâ€™t take the entire fuel at state p, rather I used the same argument for going from the state p to state j.

Sorry, if I misunderstood your approach.

Maybe i explained it in a wrong way.

Yes, it is not necessary buy all the fuel in node P. What iâ€™m saying is that we need to buy the minimum amount of fuel needed to reach some node j from P and then try to go to Q in the cheapest way, and here is where we need the DP. But this problem becomes in the shortest path in graph W describe above.

And the nodes in the shortest path (in this graph W, not the original) represent the sequence.