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

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 6:23 pm

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) :oops: :oops:
But I still don't understand the PE

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Aug 30, 2003 8:45 pm

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

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

Post by little joey » Sat Aug 30, 2003 9:41 pm

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... :evil:
(Although the sample input is quite funny; that's if you understand German :) )

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sun Aug 31, 2003 12:56 am

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 :wink:

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

Post by little joey » Sun Aug 31, 2003 9:46 am

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sun Aug 31, 2003 12:06 pm

Thanks :D
So here is the translatation in French :)

Code: Select all

les revenus des fermiers 
est un livre

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

Post by little joey » Sun Aug 31, 2003 1:29 pm

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
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

531 - WA. Help me please!

Post by medv » Sun Mar 07, 2004 11:59 am

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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

resopnse to little joey

Post by Raiyan Kamal » Sat Jul 16, 2005 12:23 am

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
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

531 WA ?!

Post by james299 » Fri Aug 05, 2005 4:13 pm

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

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp » Wed Oct 26, 2005 10:42 am

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
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » Thu Oct 27, 2005 9:53 am

For solving this problem, I used LCS algorithm..

but, I got WA..

Could anyone give me some sample input/output ??

thanks in advance..

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » Mon Jan 16, 2006 5:23 pm

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
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

531 - compromise WA

Post by taskin » Thu Jun 01, 2006 8:05 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Jun 06, 2006 2:12 am

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 :D ).
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 5 (500-599)”