Page 1 of 7

122 - Trees on the level

Posted: Thu Jul 11, 2002 11:05 am
by rhtiwari
Hi,
I submitted the following program for Problem 122. However I get WA. The program works for the sample input as well as other inputs I devised.
Please help.
------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;

void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;

node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;

int main()
{
/*build tree*/

/*First things first. Any non empty tree will require a root */
ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;

buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */

return 0;
}

void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;

while (1)
{
tempchar = getchar() ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */

tempchar = getchar() ;
if (tempchar == ')')
break ; /*last entry was read */

/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}

/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert the node in the tree */
insertnode(numstr, path) ;
}
}

void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;

/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value != NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}

void levelorder()
{
int i = 0 ;
int nextpos = 0 ;

/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;

i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}

int complete()
{
int i = 0;

while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}

void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;

i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
}
------------------------------------------------------------------------------
Thanks and Regards,
Ratnakar

Re: WA to Problem 122,Trees on the Level". Please HELP

Posted: Thu Aug 01, 2002 12:49 pm
by rhtiwari
Rune Zedeler wrote:Over here the program does not work, and I cannot understand how you have tested it with success.
In your main routine you have no loops at all. How should the program be able to test more than one three - and hence correctly run the test example which have two trees?
I assumed that the program would be tested one tree at a time. I will resubmit after putting in a loop.

Thanks. I had almost given up hope of getting a reply.

Posted: Thu Aug 08, 2002 12:10 pm
by rhtiwari
I tried putting in a lop, so that it reads all the input. It now works with the test input. However, now I get Time Limit exceeded. If I take out the loop and process each tree at a time, I get WA.

The code with the loop is given below:
--------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
char* value ;
struct node* left ;
struct node* right ;
} node ;

void buildtree() ;
void insertnode (char* valuestr, char* path) ;
void levelorder() ;
int complete() ;
void printlevelorder() ;

node* node_queue[256] ;
node* ptr_root = NULL ;
int morethanonce = 0 ;

int main()
{
/*build tree*/

/*First things first. Any non empty tree will require a root */

while (1)
{
morethanonce = 0 ;
ptr_root = NULL ;

ptr_root = (node *)malloc(sizeof(node)) ;
ptr_root->value = NULL ;
ptr_root->left = NULL ;
ptr_root->right = NULL ;

buildtree() ;
/*put the nodes in node_queue in level order */
levelorder() ;
/*check to see if all the nodes are present */
if (morethanonce || !complete())
printf("not complete\n") ;
else
printlevelorder() ;
/*print the level order traversal of the tree */
}
return 0;
}

void buildtree()
{
char path[256] ;
char numstr[16] ; /*should be more than sufficient for a normal integer */
int tempchar ;
int nextpos ;

while (1)
{
if ((tempchar = getchar()) == EOF)
exit(0) ;
while (tempchar != '(')
tempchar = getchar() ;
/* OK. We have the opening parentheses. Now see what follows it */

tempchar = getchar() ;
if (tempchar == ')')
return ; /*last entry was read */

/*OK. It was not ')'. So now it should be a digit, followed immediately by a , */
nextpos = 0 ;
while (tempchar != ',')
{
numstr[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
/*OK. , read. Now terminate the numstr and see what follows the comma */
numstr[nextpos] = '\0' ;
tempchar = getchar() ;
if (tempchar == ')') /* No path string after the ,. This means the root node */
{
insertnode(numstr,"") ;
continue ;
}

/*OK. tempchar is either 'L' or 'R' followed by ')' */
nextpos = 0 ;
while (tempchar != ')')
{
path[nextpos] = (char)tempchar ;
nextpos++ ;
tempchar = getchar() ;
}
path[nextpos] = '\0' ;
/*Now we have the value for the node and the path. Insert
the node in the tree */
insertnode(numstr, path) ;
}
}

void insertnode(char* valuestr, char* path)
{
int pos = 0 ; /*This variable will be used to track the path */
node* lastnode = NULL ;
node *tmp = NULL ;

/* Traverse the tree as per the path, building and inserting missing
intermediate nodes till the specified node is inserted. */
lastnode = ptr_root ;
while(path[pos] != '\0')
{
if (path[pos] == 'L')
{
if (lastnode->left == NULL) /*The intermediate node
does not exist. Insert it*/
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->left = tmp ;
}
lastnode = lastnode->left ;
}
else if (path[pos] == 'R')
{
if (lastnode->right == NULL)
{
tmp = (node *)malloc(sizeof(node)) ;
tmp->value = NULL ;
tmp->left = NULL ;
tmp->right = NULL ;

lastnode->right = tmp ;
}
lastnode = lastnode->right ;
}
pos++ ;
}
/*The specified node along with all the intermediate nodes have been inserted.
lastnode points to the specified node */
if (lastnode->value == NULL)
{
lastnode->value = (char*)malloc(strlen(valuestr) + 1) ;
strcpy(lastnode->value, valuestr) ;
}
else
morethanonce = 1;
}

void levelorder()
{
int i = 0 ;
int nextpos = 0 ;

/*initialize node_queue to NULLs */
for (i = 0 ; i < 256 ; i++)
node_queue = (node *)NULL ;
/* first put a pointer to the root in the queue */
node_queue[nextpos] = ptr_root ;
nextpos++ ;

i = 0 ;
while (i < 256 && node_queue != NULL)
{
/*Add the children of node_queue at the end of the queue */
if (node_queue->left != NULL)
{
node_queue[nextpos] = node_queue->left ;
nextpos++ ;
}
if (node_queue->right != NULL)
{
node_queue[nextpos] = node_queue->right ;
nextpos++ ;
}
i++ ;
}
}

int complete()
{
int i = 0;

while (i < 256 && node_queue != NULL)
{
if (node_queue->value == NULL)
return 0 ; /*Incomplete tree */
i++ ;
}
return 1 ; /*Complete tree */
}

void printlevelorder()
{
int i = 0;
printf("%s",node_queue->value) ;

i++ ;
while (i < 256 && node_queue[i] != NULL)
{
printf(" %s", node_queue[i]->value) ;
i++ ;
}
printf("\n") ;
}

122 - WA

Posted: Thu Aug 29, 2002 2:04 am
by Spike
I've tried all of the different scenarios I could think of, and I don't think it's a logic problem or anything. Does anyone have any ideas for test data or see any things that might cause a problem?

[java]import java.util.*;

class Main{

static int[] tree = new int[256];
static int nodes = 0;

public static void main( String[] args ){
String g = "", tmp = "";
while( ( tmp = token() ) != null ){
g += tmp;
}
int x = 0;
while( ( x = g.indexOf("()") ) != -1 ){
String w = g.substring(0,x);
g = g.substring( x+2 );
neg();
createTree( w );
}

}

static void createTree( String w ){
StringTokenizer tok = new StringTokenizer(w, "(" );
while( tok.hasMoreTokens() ){
nodes++;
String element = tok.nextToken();
int x = Integer.parseInt( element.substring(0, element.indexOf(",") ) );
int loc = 0;
String bin = "1";
for( int i = element.indexOf(",") + 1 ; i < element.length()-1; i++ ){
if( element.charAt(i) == 'L' ) bin += 0;
else bin += 1;
}
loc = Integer.parseInt( bin, 2 );
loc--;
if( tree[loc] != -1 ){
System.out.println( "not complete" );
return;
}
tree[loc] = x;
}
boolean good = checkTree(0) == nodes;
if( ! good ) System.out.println( "not complete" );
else{
System.out.print( tree[0] );
for( int i = 1; i < tree.length; i++ )
if( tree != -1 ) System.out.print( " " + tree );
System.out.println();
}

}


static int checkTree( int x ){
if( x >= tree.length ) return 0;
if( tree[x] == -1 ) return 0;
return 1 + checkTree( x * 2 + 1 ) + checkTree( x * 2 + 2);
}

static void neg(){
for( int i = 0; i < tree.length; i++) tree = -1;
nodes = 0;
}

static String readLine(){return token( "\n" );}
static String token( ){return token( " \n\r\t" );}
static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
c = (char) System.in.read();
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
c = (char) System.in.read();
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}
}
[/java]

HELP

Posted: Wed Nov 13, 2002 12:38 pm
by cym
here is my code for 122. I got WA, too.
can anyone give me some test cases or help me with my code???

[cpp]
#include<stdio.h>
#include<string.h>
void main(void)
{
int i,sum,v[256],count=0,ch;
char c,temp,t[257],ad[257][257];
void tree(char tr[257][257],int n[256],int co);

for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(')
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')')
{
temp=c;
if(c<58 && c>47)
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')')
{
tree(ad,v,count);
count=0;
for(i=0;i<256;i++)
{
v=0;
strcpy(ad,"");
}
}
else
{
ch=0;
for(i=count;i>0;i--)
{
if(strlen(ad[i-1])>strlen(t))
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
if(strlen(ad[i-1])<strlen(t))
{
strcpy(ad,t);
v=sum;
ch=1;
break;
}
else
{
if(strcmp(ad[i-1],t)>0)
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
strcpy(ad,t);
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
strcpy(ad[0],t);
v[0]=sum;
}
count++;
}
}
}
}


void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;


for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}

if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}

}
[/cpp]

here's a hint

Posted: Thu Nov 14, 2002 3:25 pm
by epsilon0
i tried 122 too, and got WA.
i was sure my program was correct, even thought the judge might be corrupted 8)
then i read the problem again and realize i missed something BIG:

If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string ``not complete'' should be printed.

it took only a few seconds to fix the problem...

??

Posted: Sun Nov 17, 2002 12:16 pm
by cym
but.....epsilon0,
if I don't misunderstand, I don't think my code would neglect what you metioned.
Can you give me some test cases?
or can you try my code and tell me what's wrong?
thx a lot~

here is your error

Posted: Sun Nov 17, 2002 4:57 pm
by epsilon0
running your program:
> (0,L) ()
< 0
>

clearly your program should output "not complete\n", not "0\n". a tree needs a root, right?

i can't see where the error lies within your program because it's unreadable :P

....

Posted: Mon Nov 18, 2002 2:54 am
by cym
I fix the bug....but still got WA....><

:(
I also find something strange...
can two nodes have the same value??
ex: (5,) (4,L) (4,R) ()
my code will print 5 4 4

thx for help~~

Posted: Mon Nov 18, 2002 9:01 am
by Dominik Michniewski
yes, two (or more) nodes can have the same value .... :-) why not ?

If you want to get accepted in this problem, assume that you must have a proper tree after reading all nodes belongs to it. that means:
1) any node within the tree must be defined (must have a value in input)
2) any node can't be defined twice ...

Algorithm is quite simple - read data and build tree :-))
It's all - if this in not enough - you must have a bug inside your code .

I have a problem with this quesion long time ago - I got RTE first time. But I discovered, that I can't free memory in C. When I commented line which fries memory I got Acepted :-)

Best regards
Dominik

Posted: Mon Nov 18, 2002 1:26 pm
by cym
hmm...dominik
here's my code now
I think it will do what you said, but I got another WA..... :(
why~~

[c]
#include<stdio.h>
#include<string.h>

void main(void)
{
int i,sum,v[256],count=0,ch;
char c,temp,t[257],ad[257][257];
void tree(char tr[257][257],int n[256],int co);

for(i=0;i<256;i++)
v=0;
while((c=getchar())!=-1)
{
if(c=='(') /*start to catch a node*/
{
temp=c;
sum=0;
strcpy(t,"");
while((c=getchar())!=')') /*while it's not a node's end*/
{
temp=c;
if(c<='9' && c>='0')
{
for(i=48;i<58;i++)
if(c==i) break;
sum=sum*10+i-48;
}
if(c=='L')
strcat(t,"L");
if(c=='R')
strcat(t,"R");
}
if(temp=='(' && c==')') /*if it's the end of a tree*/
{
tree(ad,v,count);
count=0;
for(i=0;i<256;i++)
{
v=0;
strcpy(ad,"");
}
}
else /*if it's not the end of a tree*/
{
ch=0;
for(i=count;i>0;i--)
/*the following are insertion sort to sort the nodes */
{
if(strlen(ad[i-1])>strlen(t))
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
if(strlen(ad[i-1])<strlen(t))
{
strcpy(ad,t);
v=sum;
ch=1;
break;
}
else
{
if(strcmp(ad[i-1],t)>0)
{
strcpy(ad,ad[i-1]);
v=v[i-1];
}
else
{
strcpy(ad,t);
v[i]=sum;
ch=1;
break;
}
}
}
}
if(ch==0)
{
strcpy(ad[0],t);
v[0]=sum;
}
count++;
}
}
}
}

/*the function is to check if the input is a valid tree*/

void tree(char tr[257][257],int n[256],int co)
{
int i,j,esc=0;


for(i=0;i<co-1;i++)
{
if(!strcmp(tr[i],tr[i+1]) || n[i]==0 || n[i+1]==0)
{
esc=1;
break;
}
}
if(n[0]==0) esc=1;
if(esc==0)
{
for(i=0;i<co;i++)
{
for(j=0;j<i;j++)
{
esc=1;
if(strlen(tr[j])==strlen(tr[i])-1)
{
if(strlen(tr[j])==0)
{
esc=0;
break;
}
else
{
if(!strncmp(tr[j],tr[i],strlen(tr[j])))
{
esc=0;
break;
}
}
}
}
if(esc==1)
break;
}
}

if(esc==1)
printf("not complete\n");
else
{
for(i=0;i<co;i++)
printf("%d ",n[i]);
printf("\n");
}

}
[/c]

Posted: Mon Nov 18, 2002 2:51 pm
by Dominik Michniewski
BTW Why don't you use character names instead of numbers :-) ?
More readable is

Code: Select all

if((ch >'0') %% (ch < '9')) 
than

Code: Select all

if((ch > 49) %% (ch < 58)) 
I try to check your program afternoon ..... I'm working now and I don't have a C++ compiler to run your code ...

Best regards
Dominik

Posted: Tue Nov 19, 2002 4:27 am
by cym
thx for your advice, dominik... :P
you are right...I didn't pay attention to this.....

besides, I think my code can run in a C compiler, like gcc
I just use vc++ to code, but in fact, I use C syntax.... 8)

thx for help~~

Posted: Wed Nov 20, 2002 12:53 pm
by Dominik Michniewski
cym: please send me private message with windows-executable file of your code - I send you back tests, on which your program fails ....ok?

sorry, but I have problems with my C++/C compiler :(

Dominik

Posted: Wed Nov 20, 2002 2:11 pm
by cym
sorry~~
I can't use private message.... :cry:
can you give me your email??
my email is atias@pchome.com.tw
thx~~