Tourist DP Problem Concept Doubt

#1

So I didn’t exactly get the idea that Manhattan Distance between tourist 1 and tourist 2 will be same all the time…
I mean, how?

#2

Hi @Kinjal
The distance between tourist 1 and tourist 2 will remain the same at any point of time. This is very intuitive.
consider a grid like
a b c d
e f g h
i j k l
m n o p
q r s t
suppose u want to go from a to t.
so for that u will hv to go 4 steps left and 5 steps down.So, it will take total nine steps for u to reach t.
so whichever path u take, it will take 9 steps to reach t.So, inorder to reach any point. tourist will take x steps no matter which path he follows.

Moreover, at any point, tourist 1 and 2 are taking 1 step each. So, at any point, they both would have taken equal number of steps to reach wherever they are.
SO, if tourist 1 has travelled total x1+y1, tourist 2 would also have taken x1+y1 steps.
Hope dis helps.

#3

Bhaiya, can you kindly tell me, how you compute manhattan distance for tourist 1 and tourist 2 if the points are like (1,2) for tourist 1 and (2,3) for tourist 2 inside the grid…

#4

abs(1-2) + abs(2-3)…
abs(x1-x2) +abs(y1-y2)

#5

So how this distance will always be same for all the possible coordinates for tourist 1 and tourist 2?

#6

… . … . …

#7

And how can I find y2 for tourist 2 by Manhattan distance relation?

#8

hello @Kinjal do you still have any query in this question ?
i think @Kartikkhariwal1 has explained very well .

#9

It’s not the explanation I seek here, I need assistance on my doubts regarding this problem. If I get my doubts cleared then it’ll be helpful.

I asked this question because by computing y2 mathematically we can reduce its time complexity from O(n^4) to O(n^3)

#10

We can reduce the complexity to O(n3). If we know the position of first tourist is (x1,y1) the x coordinate of second tourist is x2 then we must have x1+y1=x2+y2 since they both cover same distance in same amount of time. So y2=x1+y1−x2 and our state depends only on (x1,y1,x2).

#11

And this relation or equation, x1+y1=x2+y2; is there any relation with Manhattan distance?

Because Manhattan distance of points (x1,y1) for tourist 1 and (x2,y2) for tourist 2 will be: abs(x1-x2) + abs(y1-y2)
And from my point of view I didn’t see any relation with above equation but if you think, is there any connection between those two then kindly tell me…

#12

at any point, they both would have taken equal number of steps to reach wherever they are.
SO, if tourist 1 has travelled total x1+y1, tourist 2 would also have taken x1+y1 steps… This is the only reason why the equation exists

#13

Okay, got your point.
So I was watching this tourist DP problem video narrated by Sanyam Bhaiya and he’s also mentioned about Manhattan Distance on this problem. So, my question is that do we need to know about Manhattan distance concept to solve this DP problem?

#14

Manhattan distance is nothing but the distance between two points measured along axes at right angles.
In a plane with p1 at (x1, y1) and p2 at (x2, y2), it is |x1 - x2| + |y1 - y2|.
we just needed this to write the equation