Butskhrikidze's blog

By Butskhrikidze, history, 6 years ago, In English

given $$$n$$$ segments $$$[l_i, r_i]$$$ where $$$-10^9 \leq l, r \leq 10^9$$$. we are given $$$q$$$ query. each query characterized by one integer $$$x$$$. for each query we must determine how many segment involves $$$x$$$ and detect segments itself by its number. How to solve this problem?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Butskhrikidze, history, 6 years ago, In English

see tutorial about stern-brocot's tree Tutorial. this is infinity binary tree which nodes are irreducible fractions. enumerate nodes of tree using BFS. it is given one number n and one fraction . Your task is to determine what fraction is written on the node LCA(n, ) where LCA is Lowest Common Ancestor of nodes n and . (in first case node is defined by its number and in second case node is defined by fraction). 0 < a, b < 109 and 0 < n < 1018.

what is efficient method for finding what fraction is written on the node by its fraction and vice versa?

see example of tree

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it