UVa OJ Board

Posted: **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.

Posted: **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.

Posted: **Sun Mar 13, 2005 10:28 pm**

Thanks Dreamer#1 I solve it.

Posted: **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

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]

Posted: **Tue Mar 15, 2005 4:40 pm**

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

Posted: **Tue Mar 15, 2005 6:34 pm**

Thanx

Posted: **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

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.

Please point out my err.[/code]

Posted: **Wed Sep 21, 2005 6:27 am**

what's wrong???????

Code: Select all

ac now:)

Posted: **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

Posted: **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!!!!

Posted: **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

UVa OJ Board

10821 - Constructing BST

10821 - Constructing BST

Wrong answer

Wrong Answer

10821, help

Re: 10821, help

Re: 10821, help