531  Compromise
Moderator: Board moderators
531  Compromise
Why does this code get WA?
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int n,x,n1,n2,table[101][101],y,z,ans[101],count,px,py;
char text1[101][31],text2[101][31],c;
scanf("%d",&n);
for(x=0;x<n;x++)
{
c=getchar();
if(c==EOF)
break;
for(n1=0;;)
{
scanf("%s",text1[n1]);
if(strcmp(text1[n1],"#")==0)
break;
n1++;
}
for(n2=0;;)
{
scanf("%s",text2[n2]);
if(strcmp(text2[n2],"#")==0)
break;
n2++;
}
for(y=0;y<n1+1;y++)
table[0][y]=0;
for(y=0;y<n2+1;y++)
table[y][0]=0;
for(y=0;y<n2;y++)
for(z=0;z<n1;z++)
if(strcmp(text1[z],text2[y])==0)
table[y+1][z+1]=table[y][z]+1;
else
{
if(table[y+1][z]>=table[y][z+1])
table[y+1][z+1]=table[y+1][z];
else
table[y+1][z+1]=table[y][z+1];
}
if(table[n2][n1]==0)
{
printf("\n");
continue;
}
for(px=n2,py=n1,count=0;;)
{
if(px==0  py==0)
break;
if(table[px][py]==table[px1][py])
px;
else if(table[px][py]==table[px][py1])
py;
else
{
ans[count++]=py1;
px,py;
}
}
for(y=count1;y>=0;y)
{
if(y!=count1)
printf(" ");
printf("%s",text1[ans[y]]);
}
printf("\n");
}
}
[/c]
[c]
#include<stdio.h>
#include<string.h>
void main(void)
{
int n,x,n1,n2,table[101][101],y,z,ans[101],count,px,py;
char text1[101][31],text2[101][31],c;
scanf("%d",&n);
for(x=0;x<n;x++)
{
c=getchar();
if(c==EOF)
break;
for(n1=0;;)
{
scanf("%s",text1[n1]);
if(strcmp(text1[n1],"#")==0)
break;
n1++;
}
for(n2=0;;)
{
scanf("%s",text2[n2]);
if(strcmp(text2[n2],"#")==0)
break;
n2++;
}
for(y=0;y<n1+1;y++)
table[0][y]=0;
for(y=0;y<n2+1;y++)
table[y][0]=0;
for(y=0;y<n2;y++)
for(z=0;z<n1;z++)
if(strcmp(text1[z],text2[y])==0)
table[y+1][z+1]=table[y][z]+1;
else
{
if(table[y+1][z]>=table[y][z+1])
table[y+1][z+1]=table[y+1][z];
else
table[y+1][z+1]=table[y][z+1];
}
if(table[n2][n1]==0)
{
printf("\n");
continue;
}
for(px=n2,py=n1,count=0;;)
{
if(px==0  py==0)
break;
if(table[px][py]==table[px1][py])
px;
else if(table[px][py]==table[px][py1])
py;
else
{
ans[count++]=py1;
px,py;
}
}
for(y=count1;y>=0;y)
{
if(y!=count1)
printf(" ");
printf("%s",text1[ans[y]]);
}
printf("\n");
}
}
[/c]
531 WA
I use DP but get WA Help me !!!
[pascal]Program p531;
Const MaxN = 100;
Var N1,N2 : Integer;
i,j,k : Integer;
T1,T2,P : Array[1..MaxN]of String[50];
Inf : Array[1..MaxN,0..MaxN]of Integer;
Function ReadString : String;
Var Ch : Char;
S : String;
begin
S:='';
While True do begin
While Eoln do begin
Readln;
if S<>'' then begin ReadString:=S; Exit; end;
end;
Read(Ch);
if Ch in ['a'..'z','#'] then S:=S+Ch else if S<>'' then Break;
if S='#' then Break;
end;
ReadString:=S;
end;
begin
While Not Eof do begin
N1:=0;
While True do begin
T1[N1+1]:=ReadString;
if T1[N1+1]='#' then Break;
N1:=N1+1;
end;
N2:=0;
While True do begin
T2[N2+1]:=ReadString;
if T2[N2+1]='#' then Break;
N2:=N2+1;
end;
While Eoln do Readln;
for i:=1 to MaxN do
for j:=0 to MaxN do
Inf[i,j]:=1;
for i:=1 to N2 do
if T2=T1[1] then begin
Inf[1,1]:=i;
Break;
end;
for i:=2 to N1 do
for j:=1 to i do begin
if Inf[i1,j1]<>1 then
for k:=Inf[i1,j1]+1 to N2 do
if T2[k]=T1 then begin
Inf[i,j]:=k;
Break;
end;
if (Inf[i1,j]<>1)and((Inf[i1,j]<Inf[i,j])or(Inf[i,j]=1))then
Inf[i,j]:=Inf[i1,j]
end;
k:=0;
for j:=1 to MaxN do
if Inf[N1,j]<>1 then
k:=j;
i:=0;
if k>0 then
While True do begin
i:=i+1;
P:=T2[Inf[N1,k]];
While Not (P=T1[N1]) Do N1:=N11;
N1:=N11;
k:=k1;
if k=0 then Break;
end;
for j:=i downto 2 do Write(P[j],' ');
if i>=1 then Writeln(P[1]) else Writeln;
end;
end.[/pascal]
[pascal]Program p531;
Const MaxN = 100;
Var N1,N2 : Integer;
i,j,k : Integer;
T1,T2,P : Array[1..MaxN]of String[50];
Inf : Array[1..MaxN,0..MaxN]of Integer;
Function ReadString : String;
Var Ch : Char;
S : String;
begin
S:='';
While True do begin
While Eoln do begin
Readln;
if S<>'' then begin ReadString:=S; Exit; end;
end;
Read(Ch);
if Ch in ['a'..'z','#'] then S:=S+Ch else if S<>'' then Break;
if S='#' then Break;
end;
ReadString:=S;
end;
begin
While Not Eof do begin
N1:=0;
While True do begin
T1[N1+1]:=ReadString;
if T1[N1+1]='#' then Break;
N1:=N1+1;
end;
N2:=0;
While True do begin
T2[N2+1]:=ReadString;
if T2[N2+1]='#' then Break;
N2:=N2+1;
end;
While Eoln do Readln;
for i:=1 to MaxN do
for j:=0 to MaxN do
Inf[i,j]:=1;
for i:=1 to N2 do
if T2=T1[1] then begin
Inf[1,1]:=i;
Break;
end;
for i:=2 to N1 do
for j:=1 to i do begin
if Inf[i1,j1]<>1 then
for k:=Inf[i1,j1]+1 to N2 do
if T2[k]=T1 then begin
Inf[i,j]:=k;
Break;
end;
if (Inf[i1,j]<>1)and((Inf[i1,j]<Inf[i,j])or(Inf[i,j]=1))then
Inf[i,j]:=Inf[i1,j]
end;
k:=0;
for j:=1 to MaxN do
if Inf[N1,j]<>1 then
k:=j;
i:=0;
if k>0 then
While True do begin
i:=i+1;
P:=T2[Inf[N1,k]];
While Not (P=T1[N1]) Do N1:=N11;
N1:=N11;
k:=k1;
if k=0 then Break;
end;
for j:=i downto 2 do Write(P[j],' ');
if i>=1 then Writeln(P[1]) else Writeln;
end;
end.[/pascal]
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
try to search solution not from start to end of speech, but from end to start ....
in my case it give me Acc ... ))
Dominik Michniewski
in my case it give me Acc ... ))
Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
Can you give me more input (and of course output) sample for this problem? I tried an DP algorithm but I received WA. I think that it's something tricky.
How long must be the arrays because maybe this is an other problem...
Is is ok with:
How long must be the arrays because maybe this is an other problem...
Is is ok with:
Code: Select all
type vect=array[1.100] of string[30];
var x,y,z:vect;
j,i,n,m:integer;
b:array[1..100,1..100] of 0..3;
c:array[1..100,1..100] of integer;
k:integer;
531 compromise
1. is there anything to do with the order of output ?
i mean :
if there is a input like:
a b c d e
#
b c d e a
#
then the following 2 generated outputs will be both correct?
b c d e a
or
a b c d e
?
2. if the input is:
a b a a
#
a a
#
c d e
#
d e c
#
#
ff
#
g
#
#
#
#
=======EOF=======
?

I try to use second text to build a tree which consists of every string of second text. (one string appears in only one node)
For every string of first text, i trace it in the tree.
if (the string is in the tree AND the string appears at the first time)
print it.
But i got WA.
can you tell me what's wrong ?
i mean :
if there is a input like:
a b c d e
#
b c d e a
#
then the following 2 generated outputs will be both correct?
b c d e a
or
a b c d e
?
2. if the input is:
a b a a
#
a a
#
c d e
#
d e c
#
#
ff
#
g
#
#
#
#
=======EOF=======
?

I try to use second text to build a tree which consists of every string of second text. (one string appears in only one node)
For every string of first text, i trace it in the tree.
if (the string is in the tree AND the string appears at the first time)
print it.
But i got WA.
can you tell me what's wrong ?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
This problem is involved with LCS algorithm, and I solve it with DP.
Answers to your tests (without formatting):
1. b c d e
2. a a
and so on ....
DM
Answers to your tests (without formatting):
1. b c d e
2. a a
and so on ....
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I think that minimum time complexity of this problem is N^2, so you must think about Longest Increasng Sequence (LCS)
DM
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
Why I still get Wrong Answer???
I have tried every method I can think of.
But still get wrong answer??
Why???
Who can give me some hints?
But still get wrong answer??
Why???
Who can give me some hints?

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
What's wrong with my code? I keep getting wa.
Code: Select all
type txt = record
x:array[1..200] of string;
n:integer;
end;
var a:array[0..200,0..200] of integer;
t:array[1..2] of txt;
i,j,ind:integer;
ch:char;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
procedure citestecuv;
begin
if eoln then readln;
read(ch);
if ch='#' then exit;
while (ch<'a') or (ch>'z') do begin
if eoln then readln;
read(ch);
if ch='#' then exit;
end;
inc(t[ind].n);
t[ind].x[t[ind].n]:='';
while (ch>='a') and (ch<='z') do begin
t[ind].x[t[ind].n]:=t[ind].x[t[ind].n]+ch;
if eoln then begin
ch:='*';
readln;
end else read(ch);
end;
end;
procedure rec(i,j:integer);
begin
if a[i][j]=0 then exit;
if (a[i][j]=a[i1][j1]+1) and (t[1].x[i]=t[2].x[j]) then rec(i1,j1)
else if a[i][j]=a[i][j1] then rec(i,j1)
else if a[i][j]=a[i1][j] then rec(i1,j)
else rec(i1,j1);
if (a[i][j]=a[i1][j1]+1) and
(t[1].x[i]=t[2].x[j]) and (a[i][j]<>1) then write(' ',t[1].x[i]);
if (a[i][j]=a[i1][j1]+1) and
(t[1].x[i]=t[2].x[j]) and (a[i][j]=1) then write(t[1].x[i]);
end;
begin
while not eof do begin
ch:='*';
fillchar(a,sizeof(a),0);
fillchar(t,sizeof(t),0);
ind:=1;t[1].n:=0;
while ch<>'#' do citestecuv;
if eoln then readln;
ch:='*';
ind:=2;t[2].n:=0;
while ch<>'#' do citestecuv;
if eoln then readln;
for i:=1 to t[1].n do begin
for j:=1 to t[2].n do begin
if t[1].x[i]=t[2].x[j] then a[i][j]:=a[i1][j1]+1
else a[i][j]:=max(max(a[i][j1],a[i1][j]),a[i1,j1]);
end;
end;
rec(t[1].n,t[2].n);
writeln;
end;
end.

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
I'm more and more disapointed by tricky inputs. Where's the interest ? What's important (in my opnion) is more the algorithm skills than the ability to think about all the silly tricky inputs one might think of...little joey wrote:Well, it's been a while, but I've just been struggling with this one and finaly got AC(P.E.).
Never trust the judges in following the problem description. They are more concerned in stabbing you from behind then testing your programming skills...
Little joey, I'm struggling with this one : what was the tricky input you encountered please ?