Page 1 of 1

10960 - The Party, Part II

Posted: Sat Nov 12, 2005 7:48 pm
by angga888
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 :D

Re: 10960 - The Party, Part II

Posted: Sat Nov 12, 2005 10:19 pm
by angga888
I've got it AC. Now, I will answer my own questions (hopefully some of you will find them useful :D ).
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?
The answer:
Yes
Yes
Yes
For my input, there are several input cases that are invalid (sorry for the inconvinience :oops: ).
A 2 0
B 2 ?
C ? 0
D 2 0

Contradiction

<sorry, invalid input>

A 0
B 0
C 0
D 0

A 1

Contradiction

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 :D

Posted: Sun Nov 13, 2005 1:30 am
by kp
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 :evil:

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
  readln(t);
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
    readln;

    readln(n, ii, c, u);

    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
      readln(s);
      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;

      if not found then break;
    end;

    if not found then writeln('Contradiction')
    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;
        if not found then break;
      end;

      if not found then writeln('Contradiction')
      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 :)

Posted: Sun Nov 13, 2005 8:49 am
by angga888
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).

Posted: Tue May 02, 2006 5:03 pm
by C
Can someone perhaps give me some more I/O datas ??
Thanks!