Page 2 of 7

### there is no need to build a tree

Posted: Thu Nov 21, 2002 4:39 pm
there is no need to build a tree

be smart, and your code shall be fast if each node (except root) has a daddy, then everything's fine.
and it's cool, cuz you have a very fast way to check wether a node has a daddy without building the tree!

look at this node: RLRLRLRL
clearly his daddy has to be: RLRLRLR
so all you have to do is compare the (n-1) first characters!

first sort all the strings using insertion sort for example.
BEWARE! strcmp won't do the job
strcmp will tell you LR is smaller than R, but what you want is that a longer string is always bigger than a shorter one.
if two strings have the same length, then use strcmp.

example:

(0,LR) (1,RL) (2,) (3,R) (4,L) ()

sort them like this:

begin
""
"L"
"R"
"LR"
"RL"
end

then from the end of this list to the beginning, check for daddies and doubles!!!

you first find "RL" and you see its daddy is there ("R") so you keep going...
you need two pointers to this list, one for regular nodes and one for daddies... also don't forget the root doesn't have a daddy and don't forget to check for doubles.

also if you know RL has a dad in the list, no need to check wether RR has one!

good luck

### ^^

Posted: Thu Nov 21, 2002 8:30 pm
epsilon0....I totally agree with you
and luckily, my code posted above just did what you mentioned
(you can take a look......though it's not easy to understand... )

but to my surprise, I got WA..... this is why I post my code here.......T_T....

Posted: Thu Nov 21, 2002 11:17 pm
dear cym,

for ***'s sake use functions.

this problems requires at least 5 or 6 functions and a function shouldn't be longer than 15 lines... ok i reckon i don't always respect this in my own programs, but these are good guidelines when it comes to coding.

### thx

Posted: Sun Nov 24, 2002 11:26 am
thx, epsilon0....
I will try to make my code more readable. Posted: Wed Dec 04, 2002 9:11 am
to cym:
In a lot of tests I make I figured only one thing:
AFTER last number (but not always) you print space ... and sometimes, in big tests your program print empty line but numbers in output are always correct (string "not complete" is in right places too ) I don't know what's wrong ... try to avoid this space on end of line and try to submit again - maybe this is problem?

best regards
Dominik

### ....

Posted: Wed Dec 04, 2002 11:01 am
Wrong Answer 0:00.004 64 23448 C++ 122 - Trees on the level

sigh.....
I send again, and wa again...

but thx anyway, Dominik It must take you a lot of time to test my code
thx again~~

Posted: Wed Dec 04, 2002 12:06 pm
No problem Some people help me, and I help some people ))

I think, that Judge must have more crazy tests than I have )

Regards '

Dominik

### Test imput for 122 (Trees on the level)

Posted: Tue Jan 14, 2003 5:02 pm
I need a test input for 122 problem! I wrote program and on my own test it work, but on acm i still got WA! Help please! ### #122 - RTE

Posted: Wed Mar 05, 2003 8:10 am
can you tell me what's wrong with my code? i've tried with several input, and OK, but OJ gave this Run Time Error [c]/*@JUDGE_ID: XXXXX 122 C*/
#include <stdio.h>
#include <string.h>

#define MAX 300

int printerror() {

printf ("not complete\n");
return 0;
}

int printresult (int tree[MAX], int temp[MAX], int max) {
int ct;

for (ct = 1; ct <= max; ct++)
if (temp[ct] == 1) printf ("%d ", tree[ct]);
printf ("\n");
return 0;
}

int checkerr (int temp[MAX], int max) {
int ct;

for (ct = max; ct > 1; ct--)
if (temp[ct] == 1)
if (temp[ct/2] == 0) return 1;
return 0;
}

int getinput (int *bil, char data[MAX]) {
char ch, temp[MAX];
int len;

*bil = -1;
strcpy (data, "");
ch = getchar();
if (ch == EOF) return 0;
while ((ch != EOF) && (ch != '(')) ch = getchar();
if (ch == EOF) return 0;
if (ch == '(') {
memset(temp, 0, sizeof (char)* MAX);
ch = getchar(); len = 0;
if (isdigit (ch)) {
while (isdigit (ch)) {
temp[len++] = ch;
ch = getchar();
}

temp[len] = '\x0';
*bil = atoi (temp);
/*throw the comma*/
ch = getchar();

memset (temp, 0, sizeof (char)*MAX);
len = 0;
while (isalpha (ch)) {
temp[len++] = ch;
ch = getchar();
}
temp[len] = '\x0';
strcpy (data, temp);
} else
ch = getchar();
}
return 1;
}
int main () {
char data[MAX];
int bil, tree[MAX], temp[MAX], top, ct, len, err, max;

while (1) {
if (getinput (&bil, data) == 0) break;
memset (temp, 0, sizeof (int)*MAX);
err = 0; max = 0;
do {
len = strlen (data);
top = 1;
for (ct = 0; ct < len; ct++) {
top = 2*top;
if (data[ct] == 'R') top++;
}
if (temp[top] == 1)
err = 1;

tree[top] = bil;
temp[top] = 1;
if (top > max) max = top;
getinput (&bil, data);
if (bil == -1) break;
} while (1);

if (err == 1)
printerror();
else {
err = checkerr (temp, max);
if (err == 1)
printerror();
else {
printresult (tree, temp, max);
}
}
}
return 0;
}
[/c]

Posted: Thu Mar 06, 2003 2:58 pm
i've found where the mistake was, and have fixed it, and got AC. thanks ### 122 - Tree on level ( WA )

Posted: Fri May 23, 2003 3:57 pm
why i got WA??

i've checked for the empty node and double node case!!

anyone can help me??
what else case i've forgot??

Posted: Fri May 23, 2003 4:16 pm
uhm... why dont you share you algorithm? how can we give you advise or somethin if we dont know what your algo?

with love & light,

titid

Posted: Sat May 24, 2003 8:31 am
okay... here is my code!!

Code: Select all

``````#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#define MAX 300

int arr[MAX][MAX];

struct tree {
int n;
struct tree *left,*right;
} *root=0;

int BROKEN;

void make(struct tree **parent,char child) {
int lock=0;
struct tree *temp = (struct tree *) malloc(sizeof(struct tree));
if(!temp) { printf("Error!"); exit(1); }
temp->left=0;
temp->right=0;
temp->n=-1;
if(*parent==0) {
*parent = temp;
lock = 1;
} else if(child=='L') {
if((*parent)->left==0) { (*parent)->left = temp; lock=1; }
*parent = (*parent)->left;
} else if(child=='R') {
if((*parent)->right==0) { (*parent)->right = temp; lock=1; }
*parent = (*parent)->right;
}
if(!lock) free(temp);
}

void insert(int n, char *dir) {
int i;
struct tree *temp=root;
make(&root,0);
temp=root;
for(i=0;dir[i];i++) make(&temp,dir[i]);
if(temp->n==-1) temp->n=n;
else BROKEN=1;
}

void clear(struct tree*parent) {
if(parent) {
clear(parent->left);
clear(parent->right);
free(parent);
}
}

void broken(struct tree*parent,int level) {
int i=0;
if(parent) {
if(parent->n==-1) BROKEN=1;
else {
while(arr[level][i]!=-1) i++;
arr[level][i]=parent->n;
}
broken(parent->left,level+1);
broken(parent->right,level+1);
}
}

void endTree(void) {
int i,j,flag=1;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++) arr[i][j]=-1;
broken(root,0);
if(BROKEN) printf("not complete\n");
else {
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++) {
if(arr[i][j]!=-1) {
if(!flag) printf(" ");
printf("%d",arr[i][j]);
flag = 0;
}
}
printf("\n");
}
clear(root);
root = 0;
BROKEN = 0;
}

main() {
char buffer,dir;
int n;
BROKEN = 0;
while(1) {
if( scanf("%s",buffer)==EOF ) return 0;
if( strcmp(buffer,"()")==0 ) endTree();
else {
sscanf(buffer,"(%d,%[LR]s)",&n,dir);
insert(n,dir);
}
}
}
``````

Posted: Tue Jun 17, 2003 11:30 am
c'mon man....

i've stucked with this one...