531 - Compromise

[Julien Cornebise]

Well, err... Dumb I.
I got it AC PE (the PE still bothers me), I just missed one thing in the subject (multiple test cases, shame on me)
But I still don't understand the PE

[Larry]

Multi-input is always tricky (in terms of PE and AC), there are sometimes blank lines after the last cases, but usually there isn't, so you have to check for that..

[little joey]

Well, the problem isn't multi-input (no blue flag), but there are multiple cases in the input, just as given in the input description. I don't know how to get rid of the P.E.; adding a blank line after each case gets WA, leaving it out gets AC PE.

But more serious is that the input contains other characters besides lower-case letters, space-characters and '#', although the description explicitly states otherwise, and gives no clue about how to interpret them.

This problem s*x, from beginning to end...
(Although the sample input is quite funny; that's if you understand German )

[Julien Cornebise]

I agree with the PE trouble. But it's not worst than 10100 (this one REALLY s*ks).
Btw, could you please translate the example ? I don't speak german, so I missed the fun in the example (though guessing it must be astucious) ... Thanks

[little joey]

Well, only if you translate it into French for me . With the same twist of course. I'm neither German nor English, so I hope my translation is accurate.

Code: Select all

the income of the farmers
are a book with seven seals to the delegates
to remedy this
all subsidy laws should be urgently improved
#
the taxation on property and income 
should in opinion of the delegates
be seriously raised
in addion to that the controlling powers of the fiscal authorities
should be urgently improved
#

Gives

Code: Select all

the income of the delegates to should be urgently improved

I'm not sure about the word order of the last sentence. Could be "should urgently be improved", or "should be improved urgently". Both in German and in Dutch the correct order would be "should urgently improved be", but that makes no sense in English. These subtilities are the hardest to learn in a foreign language.

[Julien Cornebise]

Thanks
So here is the translatation in French

Code: Select all

les revenus des fermiers 
est un livre

[little joey]

Well, now I'm started off on the subject, I can't stop..., forgive me

Thanks for the French translation, I'd like to see translations in Potuguese, Spanish, Bangla(!), Swedish, Russian, Chinese, etc. too! Could provide some difficulties, because the tone of the two texts is very European-parliamentaly-burocratic, and the phrase "book with seven seals" is biblical and should be translated into their Islamic, Hindu, communistic or Taoistic, etc. equivalents.

I haven't read Discworld, but sure heard of it and will read it in the future, now you recommend it. My favourite in this genre is The Hitchhiker's Guide to the Galaxy, which I read simultaniously in English and Dutch to see how the 'untranslatable' puns were translated. IMO the translators did a good job on it by transposing the scene to a typical Dutch social setting.

My absolute hero on this subject is Douglas Hofstadter (well known from his 'untranslatable' Goedel, Esher, Bach). He wrote "Le Ton beau de Marot", a 500+ page (English) book about translating the untranslatable. It's deep, beautiful, scientific, humoristic, emotional, and gives a lot of 'translations' of one small 16th century French verse. A real recommendation for anybody (slightly) interested in the subject, and one of my all time favourite books. Look for a description on amazon.com.

Sorry for straying off topic,

-little joey

[medv]

What here wrong?


program p531;
const MAX = 100;
var
x,y:array[1..MAX] of string;
lenx,leny,i:integer;
s:string;
b,c:array[0..MAX,0..MAX] of integer;

function GetWord:string;
var
c:char;
s:string;
begin
read(c);
while not (c in ['a'..'z','#']) do
begin
read(c);
if eof then Exit;
end;
s := '';
while c in ['#','a'..'z'] do
begin
s := s + c;
if eoln then begin readln; break; end;
read(c);
end;

GetWord := s;
end;

procedure PrintLCS(i,j:integer);
begin
if ((i=0) or (j=0)) then Exit;
if b[i,j] = 1 then
begin
PrintLCS(i-1,j-1);
if c[i,j] > 1 then write(' ');
write(x[i]);
end else
if b[i,j] = 2 then PrintLCS(i-1,j)
else PrintLCS(i,j-1)
end;

procedure LCS;
var
i,j:integer;
begin
for i:=1 to lenx do
for j:=1 to leny do
if x[i] = y[j] then
begin
c[i,j] := c[i-1,j-1] + 1; b[i,j] := 1;
end else
if c[i-1,j] > c[i,j-1] then
begin
c[i,j] := c[i-1,j]; b[i,j] := 2;
end else
c[i,j] := c[i,j-1];
end;

begin
while not eof do
begin
i := 1; s:='';
while s <> '#' do
begin
s := GetWord; x[i] := s;
Inc(i);
end;
if eof then break;
lenx := i-2;
i := 1;s := '';
while s <> '#' do
begin
s := GetWord; y[i] := s;
Inc(i);
end;
leny := i-2;

FillChar(b,sizeof(b),0);
FillChar(c,sizeof(c),0);
LCS;
PrintLCS(lenx,leny);writeln;
end;
end.

[Raiyan Kamal]

little joey,
I know its very very late already, but i could not resist the temptation of posting a Bangla translation.

chashi der ay
jono-protinidhi der kachhe shat mohor bishishto pustok shorup
er protikarer jonno
shokol vortuki aain otishottor porimarjon korte hobe
#
ay ebong shompottir upor aropkrito kor
jono-protinidhider motanushare
gurutto shohokare briddhi korte hobe
er pashapashi ortho bebosthar kortripokkher niontron khomota
otishottor porimarjon korte hobe
#

the output from the program is :

ay er otishottor porimarjon korte hobe

meaning of this line is :

income should be inmproved urgently

However, the Bangla translation of the output line you posted here earlier is :

jono-protinidhi der ay er otishttor porimarjon korte hobe

This is a real life example of data loss in translation.

I did not change 'book with seven seals' in to something equivalent to that in my culture because i dont know anything of the book with seven seals. If someone ( may be you ) teaches me what is the book with seven seals, then i can find something equivalent to that in my culture.

Have fun with the translation. Waiting for Potuguese, Spanish, Swedish, Russian, Chinese, etc now.

[james299]

Hi! This problem bothers me ....

I use DP to solve this LCS question.
1. I read input interrupt by '#'.
2. Apply DP approach by use two table to store the length and the position of two equal string.
3. Then accord to the table to reconstruct the LCS string.

Although there are several issue on 531, but I still can't get rid of WA.
My questions as follow :
1. This problem is a mutiple input problem, should I print a blank line after each case(or without last one).
2. And some people suggest me use special approach to get the same output as their AC code did. But as the problem statement says

If there is more than one such sequence, any one is acceptable.

And there is a yellow flag before this problem, that is , they use special judger to judge the output. So I think it's ok for me to use any method to find LCS string.
My IO as follow :

Code: Select all

die einkommen der landwirte
sind fuer die abgeordneten wie ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#
men like cars and women
#
men like women and cars
#
a b c d e f g h i j k l m n o p q r s t u v w x y z
#
z y x w v u t s r q p o n m l k j i h g f e d c b a
#
a b c
#
c b a
#
a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a 
#
a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a 
#

Code: Select all

die einkommen der abgeordneten muessen dringend verbessert werden
men like cars
a
a
a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a

This is my code's output part :

Code: Select all

    
    for( i = Num - 1 ; i > 0 ; i -- )
    printf("%s ",ArrayOne[IndexReminder[i]]);
    if(Num!=0)
    printf("%s\n",ArrayOne[IndexReminder[0]]);

And my read part :

Code: Select all

while(scanf("%s",StringBuffer)!=EOF){
    i = 0 ;
    if(StringBuffer[0]!='#') {
    Add(StringBuffer,&ArrayOne[i++]);
    while(scanf("%s",StringBuffer)!=EOF&&StringBuffer[0]!='#')
    Add(StringBuffer,&ArrayOne[i++]);
    Lone = i ;
    }
    i = 0 ;
    while(scanf("%s",StringBuffer)!=EOF&&StringBuffer[0]!='#')
    Add(StringBuffer,&ArrayTwo[i++]);
    Ltwo = i ;
   ....

Thank you for your precious time.

[kp]

In my Pascal program I've changed code like:

Code: Select all

var
  s: string;

  ...
  if (s[i] in ['a'..'z']) then
  ...

to code lie:

Code: Select all

var
  s: string;

  ...
  if (s[i] <> ' ') then
  ...

And got AC instead of WA!
Problem statement is not correct.

[pipo]

For solving this problem, I used LCS algorithm..

but, I got WA..

Could anyone give me some sample input/output ??

thanks in advance..

[boshkash1986]

yes the problem is in your string order. I mean that you search for string1 in string2 and not the other way

In other words :
a b c
#
c b a
#

gives according to your code c while it is a


you reversed the strings

I hope that thie helps

[taskin]

i have tried many times but still wa. i need the ans of some question

1. what is the output if no common sequence found
2. what to do if empty text occure
3. is there any punctuation in input. i use isgraph() to parse different words but no other character other than a...z will be in the output
4. from previous posts, some suggested that search from last. what does it means? there may be multiple solution.
input:
a b c
#
c b a
#
output:
a or b or c, three should be acc

i use LCS algorithm to solve this.

[Jan]

I ignored all the 4 cases. So, the problem is elsewhere.

I just made two word sets and ran the LCS, and got acc. Word is a sequence of only lowercase letter(s) (Of course! for this problem only ).