Problem 1900. GJam 2014 China Rd A: Rational Number Tree (Large Values)
This Challenge is derived from GJam 2014 China Rational Number Tree.
The Goal is to determine the tree node if given [P,Q] or provide the [P,Q] if given a node. This is the Large Challenge with a Max of 64 Tree levels. Processing of uint64 size data requires extra care.
Consider an infinite complete binary tree where the root node is 1/1 and the left and right children of node P/Q are P/(P+Q) and (P+Q)/Q, respectively.
The Tree looks like:
1/1 ______|______ | | 1/2 2/1 ___|___ ___|___ | | | | 1/3 3/2 2/3 3/1
The nodes are 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...
Input: [N] or [P,Q] where N is a uint64 integer node or [P,Q] (double) are terms of a Node
Output: [P,Q](double) or [N](uint64) depends on Input type
Examples:
[Input] [Output] [2] [1 2] [1 2] [2] [5] [3 2] [3 2] [5]
Contest Performance: Best Delta Time of 14 minutes with only 368 able to process the large data set in less than 3 hours.
Notes:
1) Matlab has issues with uint64 for dec2bin and matrix multiplies.
2) Example of uint64 read is provided in test suite comments
3) Bitshift and bitget work on uint64
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers5
Suggested Problems
-
The Hitchhiker's Guide to MATLAB
3245 Solvers
-
Find a subset that divides the vector into equal halves
384 Solvers
-
Find last zero for each column
492 Solvers
-
165 Solvers
-
Help the Patriots get to the Super Bowl
176 Solvers
More from this Author294
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!