2
$\begingroup$

We have a map of a branching river without any islands (tree of confluences, see picture), there are piers on the river bank ( not necessarily on the confluences). We are given the distances between individual confluences and distances between piers and confluences on any particular river segment.

How would we algorithmically find if there exist piers, that are distance $X$ from each other? ( They need to be in the same stream)

Ilustration

The red dots are the piers.

This is a homework problem I can't solve, so hints are welcome.

What i am considering.

Checking individual stream until the distance between the first and furthest pier is bigger than the given distance, then backtrack and go left on the confluence, basically use DFS, but then i can't quite grasp the recursion behind it.

Will keep updated if i move somewhere.

What i considered.

Let's begin at the start of the river, we check if there is a pier on the closest 2 segments, let's say there is one, we pass it and arrive at the second confluence, again we explore and check if we have the correct distance if there are any piers, if there are and if it's the distance X we are done, if the distance is too large, we enqueue pier 1 and start anew at current spot, if the distance is not sufficient we can enqueue, we can move forward and check again, if the distance is too large, we can dequeue a pier either continue or dequeue again...

This algorithm would just always choose the only one river turn, if the river is endless and there exists such a pair of piers on that particular stream, it would find it. But i can't figure out a way of searching all the streams simultaneously.

Another Idea is to create sets of pier distances sort them and greedily try to combine them to get the distance, but there are too many streams so it would be ineffective again..

$\endgroup$
  • 1
    $\begingroup$ Could you try to propose any solution? What tree traversal or graph distance algorithms do you know? Have you tried them? What part you cannot handle (which part is really problematic to you)? Do you think, the problem given to you could be rewritten without using river nomenclature (making it more abstract)? $\endgroup$ – Evil Mar 6 '18 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.