Question link : Hasan and Trip | Practice Problems
Editorial link : Hasan and Trip | Practice Problems
Hii, This is the link of question and editorial of a DP Question. Can someone please explain the logic behind it.
Thanks in advance😀
This is fairly easy problem. See you just have to go from city 1 to N. First lets map all the cities with their given F values. After mapping you know which city has what F value. Then, as you know that the path should be in increasing order, so it’s definitely better to sort the cities.
Let’s not talk about DP and do simple thinking. If you are at city i you will either choose this city as part of your path and add Fi to your happiness, or you will look for other city after city i. This what decision you have to make. Hence, if you choose this city as part of your path your total distance will be added by 1 else it will not.
Now coming to the implementation. You can see a simple recursive relation building up here. If you started at city 1, you will store the city’s F value, add 1 to your distance and pass distance and total F_so_far in your recursive function as arguments. Hence at each recursion you will land at a city in the array, and you either choose this as your part of path or not. If you choose this, add +1 to your distance and Fi to your F_so_far while calling the next recursion. Call the first recursion and store the return value in say A and second recursion return value in B. The answer to this do state is min(A,B).
And mind it to store the return values in dp[city][F_so_far][distance][option].
Option denotes 0 or 1, that is choosing or not choosing the particular city respectively.
Now the base case is when index reaches the end, then you just subtract F_so_far by distance, and this be your return value to your dp state.
Therefore the answer will be min( dp[0][0][0][0], dp[0][0][0][1]).
1 Like
Thanks @real_adarsh
Is it not possible via 2d array? I think it might be similar to knapsack problem.
1 Like
Yes I think that is possible. Sorting the cities and running a nested for for loop for each i and j<i. In that case I think the challenge would be to store the distance you had to travel in order to get the optimal answer for some dp state at city i.
So another dist[] will be used going this way.
If you have another possible solution please let me know. 
Actually I have a recursive solution in which I am facing problem in one line in code.
In line 33, I am comparing for the maximum answer. but if i compare (ans1<ans2) and execute the code then it give correct answer on following test case.
Test case :
3
0 0 1
3 1 1
6 0 9
Answer :
4.675445
And if I compare for any other testcase then it give wrong answer.
and if i change line 33 to ans1>ans2, then it gives correct answer for most of the cases.
I know according to question (ans1>ans2) is correct, but I am unable to understand that why it is giving wrong answer on the above mentioned test case.
Link to the Code : ZB2vV6 - Online C++0x Compiler & Debugging Tool - Ideone.com
Sorry I misinterpereted the question. I solved it recently using Dynamic Programming. Here’s the algo behind it.
In my solution, dp[i] state represents the maximum happiness we can attain by ending our tour from city 1 to city i.
Now, obviously dp[1], i.e the maximum happiness you can gain by starting your tour from city 1 and ending it at city 1 itself is going to be the F1. This stands as our base case.
Now, I am using an iterative style DP. Suppose I have to fill dp[i], then I will check for each j ( 1<=j<i ), which city ( j ) to choose from 1 to i so that if I end my tour at city i, I will have the maximum magnitude of happiness. THIS IS IMPORTANT.
Now for each i iterating through 1 to N, you will subsequently be solving dp[i], and if you focus you will find that the answer to the problem is nothing but dp[N]. Thats it!
Now I’ve set each dp[i] except i=1 as -1e9 so that when I iterate through all the j’s ([1,i-1]) I wil have to choose the max of happiness possible at state i, because there is no way I’'ll have any smaller happiness than -1e9, so taking it as maximum initially before checking for all j will give me a result.
CODE
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define elif else if
#define pb push_back
#define pf push_front
#define PI 3.1415926535897932384
#define MOD 1000000007
using namespace std;
string s;
double dp[3005];
struct city{
double X,Y,F;
};
vector<city> cities(3005);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i=1; i<n+1; i++){
cin >> cities[i].X >> cities[i].Y >> cities[i].F;
}
for(int i=0; i<3005; i++){
dp[i]=-1*1e9;
}
dp[1]=cities[1].F;
for(int i=1; i<=n; i++){
for(int j=1; j<i; j++){
dp[i] = max( dp[i], dp[j]+cities[i].F-(sqrt(pow(cities[i].X-cities[j].X,2)+pow(cities[i].Y-cities[j].Y,2))));
}
}
printf("%.6f",dp[n]);
}
Hope you understand this. If there’s a problem, let me know.
3 Likes
Thankyou @real_adarsh
I understand the code. It is really very much clarified code with explaination.
Thank you for this solution @real_adarsh and @priyanshi_garg !
I want to know can we do this problem with memoization instead of iterative DP? If yes then how?
Hope you will help me!
Thank you
Regards
Tanish