Problem 1897. GJam 2014 China Rd A: Rational Number Tree

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2924486/dashboard#s=p1\"><w:r><w:t>GJam 2014 China Rational Number Tree</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Goal is to determine the tree node if given [P,Q] or provide the [P,Q] if given a node. This is the small Challenge with a Max of 16 Tree levels. The large Challenge is 64 Tree levels.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Consider an infinite complete binary tree where the root node is 1/1 and the left and right childs of node P/Q are P/(P+Q) and (P+Q)/Q, respectively.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Tree looks like:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 1/1\n ______|______\n | |\n 1/2 2/1\n ___|___ ___|___\n | | | |\n1/3 3/2 2/3 3/1]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The nodes are 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1,...</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [N] or [P,Q] where N is an integer node or [P,Q] are terms of a Node</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> [P,Q] or [N] depends on Input type</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[Input] [Output]\n [2] [1 2]\n [1 2] [2]\n [5] [3 2]\n [3 2] [5]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Contest Performance:</w:t></w:r><w:r><w:t> Best Delta Time of 14 minutes with 1193 out of 3058 completing in less than 3 hours.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/2924486/dashboard#s=p1">GJam 2014 China Rational Number Tree</a>.The Goal is to determine the tree node if given [P,Q] or provide the [P,Q] if given a node. This is the small Challenge with a Max of 16 Tree levels. The large Challenge is 64 Tree levels.Consider an infinite complete binary tree where the root node is 1/1 and the left and right childs of node P/Q are P/(P+Q) and (P+Q)/Q, respectively.The Tree looks like:<pre> 1/1
 ______|______
 | |
 1/2 2/1
 ___|___ ___|___
 | | | |
1/3 3/2 2/3 3/1</pre>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 an integer node or [P,Q] are terms of a NodeOutput: [P,Q] or [N] depends on Input typeExamples:<pre class="language-matlab">[Input] [Output]
 [2] [1 2]
 [1 2] [2]
 [5] [3 2]
 [3 2] [5]
</pre>Contest Performance: Best Delta Time of 14 minutes with 1193 out of 3058 completing in less than 3 hours.

This Challenge is derived from <http://code.google.com/codejam/contest/2924486/dashboard#s=p1 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 small Challenge with a Max of 16 Tree levels. The large Challenge is 64 Tree levels.

Consider an infinite complete binary tree where the root node is 1/1 and the left and right childs 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 an integer node or [P,Q] are terms of a Node

*Output:* [P,Q] or [N]  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 1193 out of 3058 completing in less than 3 hours.

Solve

Solution Stats

26 Solutions
9 Solvers

Last Solution submitted on Oct 14, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1897. GJam 2014 China Rd A: Rational Number Tree

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author247

Problem Tags

Community Treasure Hunt

Problem 1897. GJam 2014 China Rd A: Rational Number Tree

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author247

Problem Tags

Community Treasure Hunt

Players