You are not logged in. Please login at www.codechef.com to post your questions!

×

BINTREE - Editorial

14
2

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

EASY

PREREQUISITES:

Binary Tree
Lowest Common Ancestor

PROBLEM:

Given infinite full binary tree (each node has two children except leaf nodes), for queries of form (i,j) [i,j <= 10^9] print the length of shortest path between nodes labelled i and j.
Root is labelled 1. For each node labelled v, it's left child is labelled 2*v and right child, 2*v+1.

QUICK EXPLANATION:

We convert i,j to base 2 (without leading zeroes)
Let i in base 2 be = a1a2...an
Let j in base 2 be = b1b2...bm
If ap=bp for all p<=k, then our answer is (n+m-2*k).

EXPLANATION:

If we are at a node labelled v, if we move left we get 2*v ie. append a 0 to binary representation of v. If we move right we get 2*v+1 ie. append a 1 to binary representation of v. Thus from binary value of a node v, we completely know the path taken from the root.
image1
For example, Node 10 in binary is 1010, here first 1 is root node, next is 0, means a left turn, next 1 means are right child, next 0 means a left child.
We convert i,j to base 2 (without leading zeroes)
Let i in base 2 be = a1a2...an
Let j in base 2 be = b1b2...bm
If ap=bp for all p<=k, means their Lowest Common Ancestor(LCA) in binary is a0a1...ak. So the distance between i and j is dist(i,LCA(i,j))+dist(j,LCA(i,j)).
Since i in base 2 has n digits, the distance between i and LCA(i,j) will be (n-k). Since those are the extra steps taken from LCA moving towards node.
Therefore our answer is (n-k)+(m-k).
For example, i=10, j=13.
i in base2 = 1010
j in base2 = 1101
So, k=1 and our answer is 4-1+4-1=6.

Complexity for each query= log2(i)+log2(j).

AUTHOR'S AND TESTER'S SOLUTIONS:

To be updated soon.

This question is marked "community wiki".

asked 14 Apr '14, 15:07

darkshadows's gravatar image

5★darkshadows ♦♦
3.0k90161185
accept rate: 12%

wikified 14 Apr '14, 15:10

kunal361's gravatar image

4★kunal361
6.0k133272

Guys please explain me in the above explanation how 'k' value could 1. Please explain me.

(14 Apr '14, 21:07) pandu_492★

Best editorial!! THANKS

(20 Sep '16, 16:21) easy_2★

simplest solution that i came up with:

include<iostream>

using namespace std;

int main() { int t; cin>>t; while(t--) { long long int i,j,n=0; cin>>i>>j;

    while(i!=j)
    {
        if(i>j)
        {
            i=i/2;
            n++;

        }
        if(j>i)
        {
            j=j/2;
            n++;
        }
    }

    cout<<n<<endl;


}
return 0;

}

link
This answer is marked "community wiki".

answered 27 Oct '16, 23:00

iamcvarma's gravatar image

2★iamcvarma
1
accept rate: 0%

@pandu_49: i(10) in binary is 1010 and j(13) in binary is 1101, only for p<=1(k) is ap=bp true. Another example, i(8) in binary is 1000 and j(2) in binary is 10, only for p<=2(k) is ap=bp true. One more, i(10) in binary is 1010 and j(11) in binary is 1011, only for p<=3(k) is ap=bp true.

link

answered 14 Apr '14, 21:49

azix6's gravatar image

2★azix6
102
accept rate: 0%

include <stdio.h>

include<math.h>

long int poww(long int to) { if(to==0) return 1;

return 2*poww(to-1);

} long int other_path(long int h,long int l) { long int path=0; while(h!=l){ path+=2; h/=2;l/=2; } return path; }

long int level(long int i) {return (long int)(log10((double)i)/log10((double)2));}

int main(void) {

long int t;
scanf("%ld",&t);
long int i,j,l_i,l_j,l_df,ans;

while(t-- > 0)
{
    scanf("%ld %ld",&i,&j);
    if(i>j)
        {i=i+j; j=i-j; i=i-j;} // assigning max(j,i) to j and other i is always smaller one

    l_i=level(i);
    l_j=level(j);

    l_df=l_j-l_i;
    ans = l_df + other_path(j/poww(l_df),i); 
    /*bring them to same level and then decrease them to the common parent*/

        printf("%ld\n",ans);
}

return 0;

}

Please tell why this code is wrong ?

link

answered 19 Apr '14, 13:52

atuljain10's gravatar image

2★atuljain10
2113
accept rate: 0%

http://code.hackerearth.com/72c7f6j

here is link to run this code on hackerearth.com and please tell how this code is incorrect .

ThankYou

(19 Apr '14, 14:08) atuljain102★

I have followed the method in the editorial. But I am getting WA. what could be wrong? http://www.codechef.com/viewsolution/7022849

link

answered 25 May '15, 19:37

sreejithmm's gravatar image

0★sreejithmm
111
accept rate: 0%

I tried all edge cases I could imagine, and have no idea where my logic is going wrong. I didn't assume the numbers as binary numbers (as you did here though).

Could anyone give some test data?

link

answered 16 Jun '15, 22:07

suryak's gravatar image

0★suryak
111
accept rate: 0%

A simple yet an elegant solution on the basis of a simple observation. Helped to relate the binary tree structure to its binary representation and actually how the the LCA method inherently works on this principle! Cheers! Btw this also made me realize the effect of using cin/cout compared to scanf/printf!! http://www.codechef.com/status/BINTREE,tukku26 10 sec difference! :p

link

answered 24 Apr '14, 19:03

tukku26's gravatar image

4★tukku26
8613
accept rate: 12%

link

answered 01 May '14, 18:18

nitisha_rathi's gravatar image

2★nitisha_rathi
1
accept rate: 0%

Plz write in a bit detail . U have not explained what is k in here when u said ap=bp,p<=k What is K ???

link

answered 25 Dec '15, 21:42

vchhabra's gravatar image

1★vchhabra
795
accept rate: 0%

I don't know why it is coming wa...I have tested it for all possible cases link : https://www.codechef.com/viewsolution/10129222

link

answered 19 May '16, 16:22

lone_ranger97's gravatar image

4★lone_ranger97
1
accept rate: 0%

use long instead of int. As given in the question, 1 ≤ i,j ≤ 109.

try using


scanf( " %ld " , &valueToBeInserted );

(08 Jul '16, 20:46) radeonguy2★

As I understood , here k is value of the shared common ancestor of i and j. Or to understand it better follow this link http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

link

answered 21 Jul '16, 17:05

ankit9022's gravatar image

3★ankit9022
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×10,491
×2,418
×421
×18
×12

Asked: 14 Apr '14, 15:07

Seen: 9,154 times

Last updated: 27 Oct '16, 23:00