Page **1** of **5**

### 531 - Compromise

Posted: **Sun Jul 21, 2002 8:47 am**

by **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]

### 531 WA

Posted: **Fri Jul 26, 2002 6:04 pm**

by **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]

Posted: **Thu Mar 13, 2003 5:36 pm**

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

Posted: **Fri Mar 14, 2003 9:03 am**

by **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

Posted: **Wed Mar 26, 2003 1:31 pm**

by **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;
```

### 531 compromise

Posted: **Tue Apr 15, 2003 2:39 pm**

by **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 ?

Posted: **Tue Apr 15, 2003 2:57 pm**

by **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

Posted: **Tue Apr 29, 2003 6:04 am**

by **WanBa**

How to reduce the running time?

can some one lend me a hand!^_^

Posted: **Tue Apr 29, 2003 7:53 am**

by **Dominik Michniewski**

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

DM

### Why I still get Wrong Answer???

Posted: **Mon May 05, 2003 5:16 pm**

by **tonyk**

I have tried every method I can think of.

But still get wrong answer??

Why???

Who can give me some hints?

Posted: **Tue May 06, 2003 12:45 am**

by **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

Posted: **Tue May 06, 2003 8:51 am**

by **Dominik Michniewski**

Maxim, you have right

))

When I wrote it, I must think about other things

DM

Posted: **Tue Aug 26, 2003 12:32 am**

by **Larry**

Can someone post more cases?

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

Posted: **Tue Aug 26, 2003 8:20 pm**

by **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.
```

Posted: **Sat Aug 30, 2003 5:29 pm**

by **Julien Cornebise**

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

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 ?