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

Post by htl » Sun Jul 21, 2002 8:47 am

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

Post by Revenger » Fri Jul 26, 2002 6:04 pm

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]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Mar 13, 2003 5:36 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... :evil:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Mar 14, 2003 9:03 am

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:

Post by pc5971 » Wed Mar 26, 2003 1:31 pm

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

Post by tone4 » Tue Apr 15, 2003 2:39 pm

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 ?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Apr 15, 2003 2:57 pm

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

Post by WanBa » Tue Apr 29, 2003 6:04 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:

Post by Dominik Michniewski » Tue Apr 29, 2003 7:53 am

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

Post by tonyk » Mon May 05, 2003 5:16 pm

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

Why???
Who can give me some hints?

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim » Tue May 06, 2003 12:45 am

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue May 06, 2003 8:51 am

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:

Post by Larry » Tue Aug 26, 2003 12:32 am

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

Post by Cosmin.ro » Tue Aug 26, 2003 8:20 pm

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:

Post by Julien Cornebise » Sat Aug 30, 2003 5:29 pm

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 ?

Post Reply

Return to “Volume 5 (500-599)”