122 - Trees on the level

[bugzpodder]

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]

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]

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

[Krzysztof Duleba]

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]

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

Be happy Krzysztof Duleba

[Betty]

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]

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]

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]

Try increasing your buffer.

[pavelph]

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

[junbin]

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

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.

[sohel]

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]

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]

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]

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.