I was trying to solve this question.
https://www.codechef.com/problems/FROGV
What I am not able to understand is why two frogs can communicate only when their maximum distance is equal? Can somebody please explain this with help of a proof. I am not able to prove it. Please help.
Please someone help
I don’t understand your question, at all. What does it even mean for their maximum distance to be equal?
I read the editorial of the question. https://discuss.codechef.com/t/frogv-editorial/6301
It is written that two frogs can communicate only if their max distance is equal. I am asking how and why is it true?
Oh. It’s like creating a graph, where two frogs have an edge between each other if they can directly communicate with each other. Then two frogs can send a message between each other if and only if they’re in the same component. This is equivalent to their “maximum reach” being the same.
I could solve it using graph but I wanted to know the dp approach. So,can you help?
I mean, that’s the proof you wanted - the graph equivalent. But okay. Sort the array by coordinates, maintaining the original indices (so it’d be like a pair of (a_i, pos_i)). Then you can find the farthest a frog can reach to the left and right independently. For an index i in the sorted array, dp_{left}[i] = dp_{left}[i - 1] if a_i - a_{i - 1} \leq K, and dp_{left}[i] = a_i otherwise. Do the same for dp_{right}. Then you can set the values at the original positions (because the queries are on the original positions), and just compare them for queries.
Does the maximum distance here refers to “actual distance” or “max coordinate”?
I don’t know, that’s their terminology, not mine. But “max coordinate” makes more sense.
OK.How come they did it by checking only in one direction? They used only one loop.
Well, can it ever be true that the “reaches” for the left are the same, but not for the right?
Oh yes, you are right. I understood. Thanks a lot.