UVa 10077

From Algorithmist
Jump to navigation Jump to search

10077 - The Stern-Brocot Number System[edit]

Summary[edit]

This problem involves divide & conquer but can be solved using some properties of Stern-Brocot tree.

Explanation[edit]

Stern-Brocot tree has some beautiful properties. We don't need to design a divide & conquer fashioned code, rather there are some interesting tricks.

If we start with irreducible fractions representing zero and infinity,

and then between adjacent fractions and we insert fraction , then we obtain,

Repeating this process, we get,


and so forth. It can be proven that every irreducible fraction appears at some iteration and no fraction ever appears twice. The process can be represented graphically by means of so-called Stern-Brocot tree, named after its discoverers, Moritz Stern and Achille Brocot.

If we specify position of a fraction in the tree as a path consisting of L(eft) an R(ight) moves along the tree starting from the top (fraction ), and also define matrices,

then product of the matrices corresponding to the path is matrix whose entries are numerators and denominators of parent fractions. For example, the path leading to fraction is . The corresponding matrix product is,

and the parents of are and .

Continued fractions and Stern-Brocot tree are closely related. A continued fraction corresponds to fraction whose path from the top is with the last element removed. For example,

Pretty much cool, huh?

Gotchas[edit]

  • Take care of the scenario when m is less than n i.e. .

Sample Input[edit]

5 7
878 323
1 1

Sample Output[edit]

LRRL
RRLRRLRLLLLRLRRR

Implementation[edit]

C++: http://pastebin.com/bdAHFTbW