## 122 - Trees on the level

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

Moderator: Board moderators

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

### there is no need to build a tree

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

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

### ^^

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....

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

dear cym,

your code is so unreadable i'm sure even you can't read it back.

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.

/* and comments are your best friend. */

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

### thx

thx, epsilon0....
I will try to make my code more readable.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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

cym
New poster
Posts: 15
Joined: Mon Oct 14, 2002 3:45 pm
Contact:

### ....

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~~

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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

ojciec
New poster
Posts: 1
Joined: Tue Jan 14, 2003 4:57 pm
Location: Poland

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

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!
ojciec

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### #122 - RTE

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]

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i've found where the mistake was, and have fixed it, and got AC. thanks

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:

### 122 - Tree on level ( WA )

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??
peace...

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
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
Kalo mau kaya, buat apa sekolah?

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:
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[300],dir[300];
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);
}
}
}
``````
peace...

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:
c'mon man....

i've stucked with this one...
my stats goes bad and bad cause of this...
pliss....

-thanks-
peace...

rcotta
New poster
Posts: 6
Joined: Fri Jan 18, 2002 2:00 am
Location: Brazil

### 122 - WA nightmare!

Hi all,

Does someone have a tricky input for problem #122? I am checking for everything I could imagine but still get WA.

Thanks