[Community Puzzle] Rational Number Tree

Puzzles
#1

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.

#2

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.

#3

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.

#4

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
#5

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

#8

Hi, Iā€™m having it ok in python but for cpp I pass the tests but do not pass validator 4 and cannot get the reason why? Could you help me (maybe private message)?
Thanks in advance,
Yves

#9

I suspect it is more likely related to either timeout or memory management. chk msg. If possible, share with me what kinds of error it was.

#10

I got through it thanks for your messages.