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

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Sun Jul 20, 2003 5:45 am

I just got AC yesterday
there is no tricky inputs, at least i dont think. check if you read your data in correctly if you use !cin.eof()

and read the part about "not complete" carefully. every node should have a parent (watch out for roots -- maybe this is a tricky input) and a node cannot be assigned a value twice.

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

Post by rcotta » Sun Jul 20, 2003 6:02 am

Posting code is not something I like, but here's my code. Could someone point me some test case where it fails? I just want to know what kind of stupid thing I am doing.

[c]
/* code removed */
[/c]

I found what I was doing wrong. When I read the tree could have at most 256 nodes, I assumed its depth would be at most 8, but it is not true.

Fixed this and know my code works.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

122, still got WA,

Post by Sanghack » Tue Aug 12, 2003 10:21 am

:evil: I am totally confused with pb 122.

I checked all the previous post about this 122 problem.

I checked,

no root.
more than one position (ex (5,LLR) (4,LLR)) (also root)
more than one same value (ex (5,LR) (5,RL))
even not given a value in a node (ex (,LR))


It's my sample input...

(1,)
(2,L) (3,LL)
()
(1,)
(2,) (3,L) ()

(1,L) (2,LL) (3,LLR) ()
(2,L) ()

(3,LL) (4,LLL)
(1,) (2,L)
(5,R) (6,RR) (7,RRL) (8,RRLR) ()
(1,) (2,L) ()
(1,) ()
(1,) (2,L) (2,R) ()
(,) ()
(,L) (1,) ()
(2,L) (4,RL) (1,) (3,R) (5,RLR) ()



and It's my output
1 2 3
not complete
not complete
not complete
1 2 5 3 6 4 7 8
1 2
1
not complete
not complete
not complete



I assume that the length of a node input between two parentheses ()
is 300. ( because of, integer number (less than 12?) and a comma, LRLRLRLLLRLRL - less than 256 characters )

And I assume that the position is only can be describes with
'L' and 'R' not 'l' or 'r'

my simple code is...

Code: Select all

loop{
    input
    chkNoGivenValue
    chkSameValue

    sortByDepthAndLeftRight

    chkSamePosition
    chkRootExistence
    
    setLastChildren
    findLastParent
    loop{
        findAllParent?
    }
    if(findAllParent){
        printOut
    }
    else{
        printOut
    }
}

[cpp]#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node NODE;
struct node{
unsigned int number;
char* position;
int depth;
};

NODE* nodeList[256];
int nodeIndex;



bool notGivenAValue;
bool input(){
char c;
char buffer[300];
char* bufferPtr=buffer;

// input '('
do{
fscanf(stdin,"%c",&c);
if(feof(stdin))
return false;
}while(c!='(');
// input ')'
do{
fscanf(stdin,"%c",bufferPtr);
}while(*bufferPtr++!=')');
*(--bufferPtr)='\0'; // except ')'
if(bufferPtr-buffer==0)
return false;
else{
char* pos=strchr(buffer,',');;
pos++;// for string not for ','
NODE* newNode=(NODE*)malloc(sizeof(NODE));

if(buffer[0]==','){ // not given a value
notGivenAValue=true;
}
else
sscanf(buffer,"%d",&(newNode->number));
newNode->depth=strlen(pos);
newNode->position=(char*)malloc(sizeof(char)*(newNode->depth+1));//+1 for null.
strcpy(newNode->position,pos);
nodeList[nodeIndex++]=newNode;
return true;
}
}



bool sameValueDetection;
int cmpValue(const void* a,const void* b){
NODE *s=*((NODE**)a);
NODE *d=*((NODE**)b);
if(s->number==d->number)
sameValueDetection=true;
return s->number - d->number;
}



bool samePositionDetection;
int cmpLevel(const void* a,const void* b){
NODE *s=*((NODE**)a);
NODE *d=*((NODE**)b);
if(d->depth != s->depth)
return s->depth - d->depth;
else{
char* ss=s->position;
char* dd=d->position;
while(*ss++==*dd++ && *ss);
ss--;dd--;
if(*ss=='L' && *dd=='R')
return -1;
else if(*ss=='R' && *dd=='L'){
return 1;
}
else{
samePositionDetection=true;
return 0;
}
}
}

bool isParent(NODE* son,NODE* parent){
if(son->depth == parent->depth +1 &&
strncmp(son->position,parent->position,parent->depth)==0)
return true;
else
return false;
}

// tree determine rule
// all node except has a parent and there is a root.
// any node can't be same.
void main(){
freopen("122.txt","r+",stdin);
while(true){
// initialize and input
nodeIndex=0;
notGivenAValue=false;
if(!input())
break;
while(input());

if(notGivenAValue){
printf("not complete\n");
continue;
}


// value check.
sameValueDetection=false;
qsort((void*)nodeList,nodeIndex,sizeof(NODE*),cmpValue);
if(sameValueDetection){ // can't be.
printf("not complete\n");
continue;
}

// sort by depth and position
samePositionDetection=false;
qsort((void*)nodeList,nodeIndex,sizeof(NODE*),cmpLevel);
if(samePositionDetection){ // same position? it can't be!
printf("not complete\n");
continue;
}

// check root
if(nodeList[0]->depth!=0){ // if no root.
printf("not complete\n");
continue;
}
// check first parent, except root
int sonIndex,parentIndex;
sonIndex=nodeIndex-1; // last node
// find first parent(able)
if(sonIndex){
parentIndex=sonIndex-1;
int properParentDepth=nodeList[sonIndex]->depth-1;
while(parentIndex>=0){
// (same means success , less means fail)
if(nodeList[parentIndex]->depth<=properParentDepth)
break;
parentIndex--;
}
// same or less
if(parentIndex<0 || nodeList[parentIndex]->depth!=properParentDepth){
printf("not complete\n");
continue;
}
}
bool parentChk=true;
while(sonIndex>0 && parentIndex>=0){// mean .. except root
while(parentIndex>=0 && isParent(nodeList[sonIndex],nodeList[parentIndex])==false){
parentIndex--;
}
if(parentIndex<0){
parentChk=false;
break;
}
sonIndex--;
}
if(parentChk){
printf("%u",nodeList[0]->number);
for(int i=1;i<nodeIndex;i++){
printf(" %u",nodeList->number);
}
printf("\n");
}
else
printf("not complete\n");
}
}[/cpp]

I wanna get Accepted.

Any help appreciated.

p.s

Why first sample input is complete?
eventhough number 4 is appeared twice.

Sample Input

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

Sample Output

5 4 8 11 13 4 7 2 1
not complete

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Aug 12, 2003 2:07 pm

Did you make an assumption that the depth of the tree is not greater than 8? It is a common mistake.

As for the example input, it is ok.
Actually, the labels of the nodes are of no importance. Tree (1,)(1,L)(1,LL) is a complete tree. The node is identyfied by a string consisting of L/R letters, the tree is complete iff every LR string appears only once and for every LR string all its prefixes appears as well.

I hope that will be helpful.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

Thanks a lot...

Post by Sanghack » Fri Aug 15, 2003 6:09 am

My poor english makes me get wrong answer...
The meaning of the value was the position what i meant not the number.

:D Be happy Krzysztof Duleba
A farmer learns more from a bad harvest than a good one.

Betty
New poster
Posts: 19
Joined: Sun Aug 17, 2003 2:10 pm

Post by Betty » Tue Aug 19, 2003 7:21 am

is
(,)(3,)() valid?

although you define the root node twice ur not giving it a value twice, I so was under impression that that would be ok

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Mon Aug 25, 2003 3:19 pm

Are you checking if the node has already had a value assigned? I never read through your code but that constraint caught me the first time around.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

WA

Post by pavelph » Wed Jan 14, 2004 10:57 pm

Why WA? My program doesn't build tree, it only sort strings (like 'LR', 'LLL' etc). I think it is enough to solve this problem. But my program has some bug. Please help me to find it.
[pascal]
Program acm122; {About BIN trees}
const kolichestvo = 300;
type types = array [0 .. kolichestvo] of string;
Var n: array [0 .. kolichestvo] of integer;
p: types;
kol, z: integer;
st: string;
flag: boolean;

Procedure stroki; {reading input}
var vs: string;
code: integer;
Begin
kol:=0;
while true do begin
readln(st);
while st<>'' do begin
while (st<>'') and (st[1] <> '(') do delete(st, 1, 1);
if st='' then continue;
delete(st, 1, 1);
if st[1]=')' then exit;
vs:=copy(st, 1, pos(',', st)-1);
delete(st, 1, pos(',', st));
inc(kol);
val(vs, n[kol], code);
flag:=true;
If (code<>0) OR (vs='') Then Begin {maybe value wrong?}
write('not complete');
While pos('()', st)=0 Do readln(st);
flag:=false;
exit;
End;
p[kol]:=copy(st, 1, pos(')', st)-1);
while (st<>'') and (st[1]<>'(') do delete(st, 1, 1);
end;
end;
End;

Procedure sort; {sort strings and their values}

function bthena(a, b: string): boolean;
var f: boolean;
ii: integer;
begin
f:=false;
if length(a)<length(b) then f:=false;
if length(a)>length(b) then f:=true;
if (length(a)=length(b)) and (length(a)>0) then begin
f:=false;
ii:=1;
while (ii<length(a)) and (a[ii]=b[ii]) do inc(ii);
if a[ii]>b[ii] then f:=true;
end;
bthena:=f;
end;

var i, j, v2: integer;
v1: string;
Begin
for i:=1 to kol-1 do
for j:=i+1 to kol do
if bthena(p, p[j]) then begin
v1:=p; p:=p[j]; p[j]:=v1;
v2:=n; n:=n[j]; n[j]:=v2;
end;
End;

function check_sim(a: types): boolean; {check that has't similar nodes}
var i: integer;
begin
for i:=1 to kol-1 do
if p=p[i+1] then begin check_sim:=false; exit; end;
check_sim:=true;
end;

function check_daddy(a: types): boolean; {check that every node have father}
var i, j: integer;
vs: string;
f: boolean;
begin
for i:=2 to kol do begin
vs:=p;
delete(vs, length(vs), 1);
f:=false;
for j:=1 to i-1 do
if p[j]=vs then f:=true;
if not f then break;
end;
check_daddy:=f;
end;

Begin
{ assign(input, 'input.txt');
reset(input);}
while not eof do begin
stroki;
if flag then begin

sort;
if (not check_sim(p)) or (not check_daddy(p)) then write('not complete')
else begin
for z:=1 to kol-1 do write(n[z], ' ');
write(n[kol]);
end;

end;
writeln;
fillchar(n, sizeof(n), 0);
for z:=1 to kolichestvo do p[z]:='';
end;
End.[/pascal][/pascal]

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Thu Jan 15, 2004 4:23 am

Try increasing your buffer.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Thu Feb 05, 2004 4:32 pm

I changed const kolichestvo to 100000. But also WA :cry:
Maybe else mistke ... :oops:

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Sat Feb 07, 2004 6:49 pm

pavelph wrote:I changed const kolichestvo to 100000. But also WA :cry:
Maybe else mistke ... :oops:

just create a test data where there are 255 nodes. Each node is a right child (except root node). Then create another test data where each node is a left child (except root node). Lastly, create one test data where each node has 2 children whenever possible.

If your program can pass these 3 tests, it should not be a problem of memory.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Trick.

Post by sohel » Sun Feb 08, 2004 7:01 am

This problem is actually easy.

First sort the strings by length;
if lengths are equal sort lexicographically.

Check:
1) for every string [ a1a2a3....an] ( except the root ) there exists a
string [ a1a2a3...an-1 ]. example ( if there is LLRLRL then there must exist LLRLR ).

2) Make sure there is a root

3) Check that no repetition occurs.

These conditions should be enough.

Dows
New poster
Posts: 3
Joined: Mon Apr 19, 2004 12:19 am

WA in problem 122 once and again... that's hell!

Post by Dows » Mon Apr 19, 2004 12:33 am

Hello, i've been doing this problem for a good amount of hours and the judge doesn't want to accept it : S.


The input file checks all the different cases i think:
- All sons are L
- All sons are R
- All sons are repeated (500 repeated nodes)
- Tree without root.
- Disconected trees.
- And not defined nodes.

Mainly i have a question... what will happen in this case?
(3,R) (,L) (22,L) (22,) ()

22 22 3
or maybe "not complete"?


There's an input file, and the output:
input file:
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
()
()
()
(22,) (33,L) (44,LL) ()
(22,) (44,LL) ()
(11,LL)
(7,LLL)
(8,R)
()
(11,LL)
(7,LLL)
(8,R)
(6,L)
(4,)
()
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) (2,RRR) ()
(5,) (4,L) (13,RL) (5,L) (6,R) ()
(5,) (6,L) ()
(3,) ()
()
()
() ()
(4,LL) (3,L) (2,) (6,R) ()
(4294967295,) ()
(4294967295,LLR) (2,LL) (3,R) ()
(65536,) ()
(65537,) ()
(2147483648,) ()
(2147483647,) ()
(,L) (22,L) (22,) ()
(3,R) (,L) (22,L) (22,) ()
output file:
5 4 8 11 13 4 7 2 1
not complete
22 33 44
not complete
not complete
4 6 8 11 7
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
5 6
3
2 3 6 4
4294967295
not complete
65536
65537
2147483648
2147483647
22 22
22 22 3
thanks a lot

skeeve
New poster
Posts: 6
Joined: Sun Apr 18, 2004 4:17 pm

Post by skeeve » Mon Apr 19, 2004 10:47 am

My ACC program gives a alsightly different output
your output:
5 4 8 11 13 4 7 2 1
not complete
22 33 44
not complete
not complete
4 6 8 11 7
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
5 6
3
2 3 6 4
4294967295
not complete
65536
65537
2147483648
2147483647
22 22
22 22 3
my output
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
not complete
22 33 44
not complete
not complete
4 6 8 11 7
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
5 6
3
not complete
not complete
not complete
not complete
2 3 6 4
2147483647 [this is wrong in my output - they don't use so large numbers :)]
not complete
65536
65537
2147483647
2147483647
not complete
not complete
not complete
< and starts cycling an outputting not compelete somewhere here for a while - so this is probably not a correct input >
we mostly differ in number of "not completes written" - you get many empty inputs and don't write any "not complete"
I hope this helps

Dows
New poster
Posts: 3
Joined: Mon Apr 19, 2004 12:19 am

Post by Dows » Mon Apr 19, 2004 4:37 pm

So you get accepted... my output is now:
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
not complete
22 33 44
not complete
not complete
4 6 8 11 7
5 4 8 11 13 4 7 2 1
not complete
not complete
not complete
5 6
3
not complete
not complete
not complete
not complete
2 3 6 4
4294967295
not complete
65536
65537
2147483648
2147483647
not complete
not complete
And i don't get accepted... u_u'


i think that now my output file is exactly equal than yours... i don't know what kind of tricky input can't my program pass...

what will your program answer to :
(,L) (1,) () -> ?
(,L) (2,L) (1,) () -> it seems that your program will answer not complete to a redefinition of a non defined node.

And i can't invent any more difficult input, can anyone help me in that?

Thanks.

Post Reply

Return to “Volume 1 (100-199)”