Problem 1900. GJam 2014 China Rd A: Rational Number Tree (Large Values)

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 Large Challenge with a Max of 64 Tree levels. Processing of uint64 size data requires extra care.</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 children 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 a uint64 integer node or [P,Q] (double) 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](double) or [N](uint64) 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 only 368 able to process the large data set in less than 3 hours.</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>Notes:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>1) Matlab has issues with uint64 for dec2bin and matrix multiplies.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>2) Example of uint64 read is provided in test suite comments</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>3) Bitshift and bitget work on uint64</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 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:<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 a uint64 integer node or [P,Q] (double) are terms of a NodeOutput: [P,Q](double) or [N](uint64) 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 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 comments3) Bitshift and bitget work on uint64

Solve

Solution Stats

30 Solutions
5 Solvers

Last Solution submitted on Dec 17, 2018

Last 200 Solutions

Solution Comments

Solution 1203316

1 Comment

1 Comment

yurenchu on 8 Jun 2017

I'm relatively new to Cody; can anyone please tell me, why does this solution of mine not appear in the Solution List?

Problem Recent Solvers5

Problem Tags

bitget bitshift china 2014 gjam rational tree uint64

Community Treasure Hunt

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

Start Hunting!

Problem 1900. GJam 2014 China Rd A: Rational Number Tree (Large Values)

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Problem 1900. GJam 2014 China Rd A: Rational Number Tree (Large Values)

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author241

Problem Tags

Community Treasure Hunt

Players