122 - Trees on the level

epsilon0 · Post by **epsilon0** » 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

cym · Post by **cym** » 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....

epsilon0 · Post by **epsilon0** » Thu Nov 21, 2002 11:17 pm

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 · Post by **cym** » Sun Nov 24, 2002 11:26 am

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

Dominik Michniewski · Post by **Dominik Michniewski** » 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

cym · Post by **cym** » 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~~

Dominik Michniewski · Post by **Dominik Michniewski** » 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

ojciec · Post by **ojciec** » 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!

titid_gede · Post by **titid_gede** » 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]

titid_gede · Post by **titid_gede** » Thu Mar 06, 2003 2:58 pm

i've found where the mistake was, and have fixed it, and got AC. thanks

ayaw · Post by **ayaw** » 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??

titid_gede · Post by **titid_gede** » 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

ayaw · Post by **ayaw** » 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[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);
		}
	}
}

ayaw · Post by **ayaw** » Tue Jun 17, 2003 11:30 am

c'mon man....

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

-thanks-

rcotta · Post by **rcotta** » Sat Jul 19, 2003 5:54 pm

Hi all,

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

Thanks

UVa OJ Board

122 - Trees on the level

there is no need to build a tree

^^

another advice

thx

....

Test imput for 122 (Trees on the level)

#122 - RTE

122 - Tree on level ( WA )

122 - WA nightmare!