## 10960 - The Party, Part II

Moderator: Board moderators

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### 10960 - The Party, Part II

I've tried this problem, and got WA over and over. I have several questions as follow:
May I assume that in the input, the persons will always be represented as consecutive letters starting from 'A'?
May I assume that in the input, the items will always be represented as consecutive integers starting from 0?
May I assume that in the input, the colors will always be represented as consecutive integers starting from 0?

I have several input cases, and I really get confused about what should be the output. Could someone please tell me the output?
21

4 2 3 6
Same colour of item 0 = A B D
Colour 2 for item 0 = B
Not colour 2 for item 1 = C
Not colour 1 for item 1 = C
Same colour of item 1 = C D
Same colour of item 1 = A D

4 2 3 7
Same colour of item 0 = A B D
Colour 2 for item 0 = B
Not colour 2 for item 1 = C
Not colour 1 for item 1 = C
Same colour of item 1 = C D
Same colour of item 1 = A D
Colour 1 for item 0 = D

4 1 1 1
Same colour of item 0 = G X Y Z

4 1 1 1
Same colour of item 0 = A B C D

1 1 2 1
Not colour 0 for item 0 = A

1 1 1 1
Not color 0 for item 0 = A

1 3 1 1
Same colour of item 0 = A

3 3 1 1
Same colour of item 0 = A B C

3 1 3 3
Not colour 2 for item 0 = R W
Not colour 1 for item 0 = E R
Same colour of item 0 = E W

3 1 3 3
Not colour 2 for item 0 = A B
Not colour 1 for item 0 = B C
Same colour of item 0 = A C

3 1 3 4
Not colour 2 for item 0 = R W
Not colour 1 for item 0 = E R
Same colour of item 0 = E W
Colour 0 for item 0 = E

3 1 3 4
Not colour 2 for item 0 = A B
Not colour 1 for item 0 = B C
Same colour of item 0 = A C
Colour 9 for item 0 = C

1 1 2 1
Not colour 0 for item 0 = A B

1 1 2 2
Not colour 0 for item 0 = A
Not colour 0 for item 1 = A

3 1 2 3
Colour 0 for item 0 = A
Colour 1 for item 0 = B
Colour 2 for item 0 = C

3 2 2 1
Colour 0 for item 0 = A

1 1 1 1
Colour 0 for item 2 = A

1 1 1 1
Not colour 1 for item 0 = A

1 1 1 2
Not colour 1 for item 0 = A
Not colour 2 for item 0 = A

1 1 2 1
Colour 0 for item 1 = A

1 1 10 9
Not colour 9 for item 0 = A
Not colour 8 for item 0 = A
Not colour 7 for item 0 = A
Not colour 5 for item 0 = A
Not colour 4 for item 0 = A
Not colour 3 for item 0 = A
Not colour 2 for item 0 = A
Not colour 1 for item 0 = A
Not colour 0 for item 0 = A
Thanks for any help

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### Re: 10960 - The Party, Part II

I've got it AC. Now, I will answer my own questions (hopefully some of you will find them useful ).
angga888 wrote:May I assume that in the input, the persons will always be represented as consecutive letters starting from 'A'?
May I assume that in the input, the items will always be represented as consecutive integers starting from 0?
May I assume that in the input, the colors will always be represented as consecutive integers starting from 0?
Yes
Yes
Yes
For my input, there are several input cases that are invalid (sorry for the inconvinience ).
A 2 0
B 2 ?
C ? 0
D 2 0

<sorry, invalid input>

A 0
B 0
C 0
D 0

A 1

A 0 0 0

A 0 0 0
B 0 0 0
C 0 0 0

<sorry, invalid input>

A 0
B 0
C 0

<sorry, invalid input>

<sorry, invalid input>

<sorry, invalid input>

<sorry, invalid input>

<sorry, invalid input>

A 0 ?
B ? ?
C ? ?

<sorry, invalid input>

<sorry, invalid input>

<sorry, invalid input>

<sorry, invalid input>

A 6
Hope it helps

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
I get WA over and over...

My program gives correct output for all tests from the original olimpiad's site! I'am confused and frustrated...

I used disjoint sets (which is natural for this problem).
Also I implemented various features like trim() to correct
input (just in case).

But still WA

Maybe some "fresh sight" will help?

Here is my code:

Code: Select all

``````program kp10960;

// The Party, Part II

const
UNDEFINED = 255;

label finish;

var
t, n, c: integer;
p: array [0..100,0..25] of byte;
rank: array [0..100,0..25] of byte;
notc: array [0..25,0..100,0..100] of byte;
col: array [0..25,0..100] of byte;

procedure init;
begin
end;

function parent(man, item: integer): integer;
begin
if p[item,man]<>man then
p[item,man]:= parent(p[item,man],item);
result:= p[item,man];
end;

function color(man, item: integer): integer;
begin
result:= col[parent(man,item),item];
end;

procedure union(item, man1, man2: integer);
var
i: integer;
begin
man1:= parent(man1,item);
man2:= parent(man2,item);
if man1=man2 then exit;
if rank[item,man1]>rank[item,man2] then begin
p[item,man2]:= man1;
for i:=0 to c-1 do notc[man1,item,i]:= notc[man1,item,i] or notc[man2,item,i];
end else begin
p[item,man1]:= man2;
for i:=0 to c-1 do notc[man2,item,i]:= notc[man1,item,i] or notc[man2,item,i];
if rank[item,man2]=rank[item,man1] then
inc(rank[item,man2]);
end;
end;

procedure trim(var s: string);
var
i: integer;
begin
while (length(s)>1) and (not (s[1] in ['A'..'Z','a'..'z','0'..'9'])) do delete(s,1,1);
while (length(s)>1) and (not (s[length(s)] in ['A'..'Z','a'..'z','0'..'9'])) do delete(s,length(s),1);
i:= 2;
while i<=length(s) do begin
if (s[i]=' ') and (s[i-1]=' ') then
delete(s,i,1)
else inc(i);
end;
end;

procedure solve;
var
i, j, ii, u, ps, item, l, k, clr, vars: integer;
s, s1: string;
v: array [0..25] of byte;
found: boolean;
f: integer;
begin
for i:= 1 to t do begin

fillchar(notc,sizeof(notc),0);
fillchar(col,sizeof(col),UNDEFINED);

for j:=0 to n-1 do begin
for k:=0 to ii-1 do begin
rank[k,j]:= 0;
p[k,j]:= j;
end;
end;

found:= true;

for j:=1 to u do begin
trim(s);
ps:= pos('item',s);
s1:= copy(s,1,ps-1);

fillchar(v,sizeof(v),0);
item:= ord(s[ps+5])-ord('0');
if s[ps+6] in ['0'..'9'] then item:= item*10+(ord(s[ps+6])-ord('0'));
l:= length(s);
for k:=ps+4 to l do
if s[k] in ['A'..'Z'] then v[ord(s[k])-ord('A')]:= 1;

if pos('Same',s1) <> 0 then begin
k:=0;
while (k<n) and (v[k]=0) do inc(k);
if k=n then begin
found:= false;
break;
end;
f:= k; inc(k);
while k<n do begin
if v[k]=1 then begin
if color(f,item)=UNDEFINED then
if color(k,item)=UNDEFINED then
union(item,f,k)
else begin
clr:= color(k,item);
union(item,f,k);
if notc[parent(k,item),item,clr]=1 then begin
found:= false;
break;
end else col[parent(k,item),item]:= clr;
end
else
if color(k,item)=UNDEFINED then begin
clr:= color(f,item);
union(item,f,k);
if notc[parent(k,item),item,clr]=1 then begin
found:= false;
break;
end else col[parent(k,item),item]:= clr;
end else if color(k,item)<>color(f,item) then begin
found:= false;
break;
end;
end;
inc(k);
end;
end else if pos('Not',s1)<>0 then begin
clr:= ord(s[ps-6])-ord('0');
if s[ps-7] in ['0'..'9'] then inc(clr,10*(ord(s[ps-7])-ord('0')));
for k:=0 to n-1 do
if (v[k]=1) and (color(k,item)=clr) then begin
found:= false;
break;
end else if (v[k]=1) then begin
notc[parent(k,item),item,clr]:= 1;
end;
end else begin
clr:= ord(s[ps-6])-ord('0');
if s[ps-7] in ['0'..'9'] then inc(clr,10*(ord(s[ps-7])-ord('0')));
for k:=0 to n-1 do
if v[k]=1 then
if (color(k,item) = UNDEFINED) then
if notc[parent(k,item),item,clr]=1 then begin
found:= false;
break;
end else col[parent(k,item),item]:= clr
else if color(k,item) <> clr then begin
found:= false;
break;
end;
end;

end;

else begin

for j:=0 to n-1 do begin
for k:=0 to ii-1 do
if color(j,k) = UNDEFINED then begin
u:= parent(j,k);
vars:= 0; clr:= 0;
for f:=0 to c-1 do
if notc[u,k,f]=0 then begin
inc(vars);
clr:= f;
end;
if vars=0 then begin
found:= false;
break;
end;
if vars=1 then col[u,k]:= clr;
end;
end;

else begin
for j:=0 to n-1 do begin
write(chr(ord('A')+j),' ');
for k:=0 to ii-1 do
if color(j,k)=UNDEFINED then begin
write('?');
if k<>ii-1 then write(' ');
end else begin
write(color(j,k));
if k<>ii-1 then write(' ');
end;
writeln;
end;
end;
end;

if i<>t then writeln;
end;
end;

procedure print;
begin

end;

begin
{\$IFNDEF ONLINE_JUDGE}
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
{\$ENDIF}

init;
solve;
print;

finish:
{\$IFNDEF ONLINE_JUDGE}
close(input); close(output);
{\$ENDIF}
end.
``````
Any help is acceptable

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
I haven't looked at your code, but:
kp wrote:Also I implemented various features like trim() to correct
input (just in case).
I didn't check for the input validity, so I think the judge input should be correct (at least it works well with scanf() and gets() in C).

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
Can someone perhaps give me some more I/O datas ??
Thanks!