[Community Puzzle] Rational Number Tree

https://www.codingame.com/training/medium/rational-number-tree

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @R2B2,@Maurice_Moss and @JBM.
If you have any issues, feel free to ping them.

1/0, Division by zero exception - you must have encountered it at some moment in your computing life.

It is a taboo in computing. We try to avoid it, and Ouch! when seeing it.

In this puzzle we do the opposite. We embrace it.

We use 1/0 as a seed in growing up a Tree, a tree enormous enough to become a Number System. We try to traverse the tree among the branches to locate fruits of all varieties.

I am at a loss . I used a queue to first make the stern brocot tree and then normal BST operations to find the outputs. I am confused about the length of the tree needed for this problem. I iterated through all of the inputs and find the max number/ length , then I used it as the maximum height of my tree. But I am always getting TLE(Time limit exceeded) except the first test case(since its max length is quite small and my program gives the correct output too). I think my overall approach to it might have been wrong. If anyone can help or give me some guidance, I will be utterly grateful.

The tree itself is practically a number system. As far as the computer memory limit allows, it contains all possible positive rational numbers existing in the universe.

So, if you use the regular BFS or DFS, you are trying to search through the number system to find an answer, destined to have time limit problem.

To find a given p/q, you should have an efficient way to determine your target is on the L or R of each node you are in, then step onto the next node. Repeat this process several times or a few dozen times. Eventually you will land on the target.

2 Likes

Thanks. The way I approached the problem was fully wrong. I tried to find the pattern and now I solved it :grinning: