## 531 - Compromise

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 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[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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 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[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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
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
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)

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:
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
New poster
Posts: 4
Joined: Sat Mar 29, 2003 2:44 pm

### 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 ?

Dominik Michniewski
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
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)

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am
How to reduce the running time?
can some one lend me a hand!^_^
destiny conditioned by past

Dominik Michniewski
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
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)

tonyk
New poster
Posts: 7
Joined: Mon May 05, 2003 5:11 pm

### 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?

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Maxim, you have right ))
When I wrote it, I must think about other things

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)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post more cases?

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

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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 ?