10821 - Constructing BST

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

10821 - Constructing BST

Post by Programmer » Sun Mar 13, 2005 11:45 am

Hello.
I'm trying to solve this problem.Can anyone give some hint how to solve it.
Thanks.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Mar 13, 2005 8:10 pm

[1.....N]

now let 1<=K<=N then

if you insert K first then in the left subtree you have to accommodate K-1 elements and N-K-1 elements in the right subtree within a height of <=H-1

now check if you can have a subtree of height <=H-1 with K-1 elements and also N-K-1 elements... for every K, starting from 1, check the possibility and whenever its possible try the samething for each subtree with height decreasing by 1 for each level...

hope it helps. :)

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

Post by Programmer » Sun Mar 13, 2005 10:28 pm

Thanks Dreamer#1 I solve it. :D

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Wrong answer

Post by jagadish » Tue Mar 15, 2005 3:44 pm

i guess this problem cannot have any tricky inputs so maybe i have missed something basic ..Can someone check this I/O please..

Code: Select all

30 5
30 30
50 30
50 6
60 7
4 1
10000 30
0 0

Code: Select all

Case 1: 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30
Case 2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Case 3: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 35 27 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 4: 19 3 1 2 11 7 5 4 6 9 8 10 15 13 12 14 17 16 18 35 27 23 21 20 22 25 24 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 5: 1 29 13 5 2 3 4 9 7 6 8 11 10 12 21 17 15 14 16 19 18 20 25 23 22 24 27 26 28 45 37 33 31 30 32 35 34 36 41 39 38 40 43 42 44 53 49 47 46 48 51 50 52 57 55 54 56 59 58 60
Case 6: Impossible
Case 7: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1809 17 18 785 273 19 145 81 49 33 25 21 20 23 22 24 29 27 26 28 31 30 32 41 37 35 34 36 39 38 40 45 43 42 44 47 46 48 65 57 53 51 50 52 55 54 56 61 59 58 60 63 62 64 73 69 67 66 68 71 70 72 77 75 74 76 79 78 80 113 97 89 85 83 82 84 87 86 88 93 91 90 92 95 94 96 105 101 99 98 100 103 102 104 109 107 106 108 111 110 112 129 121 117 115 114 116 119 118 120 125 123 122 124 127 126 128 137 133 131 130 132 135 134 136 141 139 138 140 143 142 144 209 177 161 153 149 147 146 148 15.............

[/code]
if u can think of it .. u can do it in software.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Mar 15, 2005 4:40 pm

Your output is correct, but you missed period after the word "Impossible"

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Tue Mar 15, 2005 6:34 pm

Thanx :D
if u can think of it .. u can do it in software.

james299
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

Wrong Answer

Post by james299 » Tue Jul 26, 2005 9:27 am

hi !
I'm trying to solve this problem .
I use the alog just like what Dreamer#1 did, but I got WA for serveral times.And now I can't find out what's wrong with my code.
1. I check the input N & H, if N is over 2^H-1 or less than H, and print impossible.
2. And I use recursion to build the tree.
3. I use preorder to traverse the tree, and print each one.
4. I check the space ' ' at the tail of my output.

and my program I/O

Code: Select all

30 5 
30 30 
50 30 
50 6 
60 7 
4 1 
10000 30 
0 0 

Code: Select all

Case 1: 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30
Case 2: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Case 3: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 35 27 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 4: 19 3 1 2 11 7 5 4 6 9 8 10 15 13 12 14 17 16 18 35 27 23 21 20 22 25 24 26 31 29 28 30 33 32 34 43 39 37 36 38 41 40 42 47 45 44 46 49 48 50
Case 5: 1 29 13 5 2 3 4 9 7 6 8 11 10 12 21 17 15 14 16 19 18 20 25 23 22 24 27 26 28 45 37 33 31 30 32 35 34 36 41 39 38 40 43 42 44 53 49 47 46 48 51 50 52 57 55 54 56 59 58 60
Case 6: Impossible.
Case 7: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1809 .......
here are my part of bulidtree code

Code: Select all

struct MyTree* buildTree( int N , int H , int inti ) {
       struct MyTree *left = NULL , *right = NULL , *nowptr;  
       /* tree */   
       int i ;      
       if(H==1&&N==1)
       return newItem(inti+1);
       /* at the root */
       if(H<=0)
       return NULL;
       /* just in case */
       for( i = 1 ; i <= N ; i ++ )
       if(isTree(i-1,H-1)==1&&isTree(N-i,H-1)==1) {
       /* isTree is a method check that N is samller than 2^H*/
       if(i!=1) {
       left = buildTree(i-1,H-1,inti);
       if(left==NULL)
       continue;
       }
       if(i!=N) {
       right = buildTree(N-i,H-1,inti+i);
       if(right==NULL) {
       free(left);
       continue;
         }
       }
       nowptr = newItem(inti+i);
       nowptr->left = left ;
       nowptr->right = right ;
       return nowptr;
       }/* for */
       return NULL;
}
here are my main function

Code: Select all

 while(scanf("%d %d",&N,&H)!=EOF&&N+H!=0) {
    if(isTree(N,H)==1&&N>=H) {
       topptr = buildTree(N,H,0);
       if(topptr!=NULL) {
       printf("Case %d:",times++);
       PrintLev(topptr);
       printf("\n");
       }
       else 
       printf("Case %d: Impossible.\n",times++);
     }
    else
    printf("Case %d: Impossible.\n",times++);
    }
Thanks you guys spend your precious time. :D
Please point out my err.[/code]

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

10821, help

Post by mysword » Wed Sep 21, 2005 6:27 am

what's wrong???????

Code: Select all

ac now:)
Last edited by mysword on Fri Sep 23, 2005 9:00 am, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10821, help

Post by Martin Macko » Fri Sep 23, 2005 2:36 am

mysword wrote:what's wrong???????
Your solution's not working for

Code: Select all

1 2
0 0
The output should be

Code: Select all

Case 1: 1

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Re: 10821, help

Post by mysword » Fri Sep 23, 2005 8:59 am

Martin Macko wrote:
mysword wrote:what's wrong???????
Your solution's not working for

Code: Select all

1 2
0 0
The output should be

Code: Select all

Case 1: 1
Thank you very much!!!!

User avatar
moham_87
New poster
Posts: 2
Joined: Mon Jul 31, 2006 1:23 pm
Location: Egypt

Post by moham_87 » Tue Aug 22, 2006 11:33 am

1. I check the input N & H, if N is over 2^H-1 or less than H, and print impossible.
why should u check if N is less than H? I think if N<H, it should work
The problem statement says:
In this problem, you have to find the order of 1 to N integers such that the BST constructed by them has height of at most H.
good luck :)

Post Reply

Return to “Volume 108 (10800-10899)”