531 - Compromise

[htl]

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[px-1][py])
px--;
else if(table[px][py]==table[px][py-1])
py--;
else
{
ans[count++]=py-1;
px--,py--;
}
}
for(y=count-1;y>=0;y--)
{
if(y!=count-1)
printf(" ");
printf("%s",text1[ans[y]]);
}
printf("\n");
}
}
[/c]

[Revenger]

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[i-1,j-1]<>-1 then
for k:=Inf[i-1,j-1]+1 to N2 do
if T2[k]=T1 then begin
Inf[i,j]:=k;
Break;
end;
if (Inf[i-1,j]<>-1)and((Inf[i-1,j]<Inf[i,j])or(Inf[i,j]=-1))then
Inf[i,j]:=Inf[i-1,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:=N1-1;
N1:=N1-1;
k:=k-1;
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]

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...

[Dominik Michniewski]

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

[pc5971]

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:

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;

[tone4]

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 ?

[Dominik Michniewski]

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

[WanBa]

How to reduce the running time?
can some one lend me a hand!^_^

[Dominik Michniewski]

I think that minimum time complexity of this problem is N^2, so you must think about Longest Increasng Sequence (LCS)

DM

[tonyk]

I have tried every method I can think of.
But still get wrong answer??

Why???
Who can give me some hints?

[Maxim]

Lapsus linguae by Dominik, as he wrote Longest Increasing Sequence. What he meant (I guess ) was Longest Common Sequence. It's Dynamic Programming. Look for it in books with topics about DP. If it still makes the problem, let me know. I'll be glad to help.

Maxim

[Dominik Michniewski]

Maxim, you have right ))
When I wrote it, I must think about other things

DM

[Larry]

Can someone post more cases?

I handled everything mentioned, including LCS of no words..

[Cosmin.ro]

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[i-1][j-1]+1) and (t[1].x[i]=t[2].x[j]) then rec(i-1,j-1)
    else if a[i][j]=a[i][j-1] then rec(i,j-1)
      else if a[i][j]=a[i-1][j] then rec(i-1,j)
         else rec(i-1,j-1);
  if (a[i][j]=a[i-1][j-1]+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[i-1][j-1]+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[i-1][j-1]+1
           else a[i][j]:=max(max(a[i][j-1],a[i-1][j]),a[i-1,j-1]);
      end;
    end;
    rec(t[1].n,t[2].n);
    writeln;
  end;
end.

[Julien Cornebise]

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...

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, I'm struggling with this one : what was the tricky input you encountered please ?