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.

Solve

Solution Stats

25 Solutions
18 Solvers

Last Solution submitted on Jul 10, 2018

Last 200 Solutions

Problem Comments

Problem Recent Solvers18

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers18

Suggested Problems

More from this Author236

Problem Tags

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

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers18

Suggested Problems

More from this Author236

Problem Tags

Players