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 :cry: 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... :evil:

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. :cry:
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 8)) 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. :wink:

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... :evil:
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 ?