10100 - Longest Match

[Maxim]

Please, anybody who got AC, help! It's killing me I can't get AC only because of silly input.

Maxim

[titid_gede]

i think the problem is on the gets function. since i think it retains the '\n' caracter, so if blank line then strlen = 1 since there is one caracter that is '\n'.

[Adrian Kuegel]

It is not a problem with gets. gets doesn't attach the '\n' in contrast to fgets.
But you should print blank also in cases where at least one of the lines contains only whitespace characters. Note that all characters but letters are considered as whitespace characters in this problem.

[Maxim]

Thank you, Adrian. I've tried with that blank stuff, but still getting WA.
Eventually, I've changed the way I read input. First, I read lines with gets() till end of file. Then I do calculation.

I know, it's DP problem. Is this procedure for searching white-space characters (as defined in text of problem) good one?

[c]cut out [/c]

Maxim

[Adrian Kuegel]

yes, I think so.
Do you consider something like
.test;,.test
as two words?
You can send me your whole program with private message if you want.

[Maxim]

Thanks again, Adrian. Finally got AC. The problem was in bad task description. White-space characters are all characters except for letters and digits.

Maxim

[neowarez]

Hi..

I dont understand why my code give me WA...


Can somenone who got AC tell me the output for this please..

Code: Select all


test test
test test
sdfasdf
(blank Line = (Length=0))
kgds
(Space charaters)
.....
asd 
The
the


My code output:

Code: Select all

 1. Length of longest match: 1
 2. Blank!
 3. Length of longest match: 0
 4. Length of longest match: 0
 5. Length of longest match: 1


Thanks!

[frehe]

Since the problem is very much under specified I wonder what the correct output is for:
...
xyz
The
the
a b c
d b c
b 3
b 3
b..a
b.a

I guessed:
1. Blank!
2. 1
3. 2
4. 2
5. 2

But I still don't solve the problem.

[Larry]

What assumptions can I make about this problem? I've read the boards, used the same code for many other LCS problems, and still WA.. are these case sensitives? Anyone have any more critical cases?

[Larry]

I tried everything and still WA.. grr.!

[Julien Cornebise]

Hello
I'm having WA for this problem, and after having rewrote it from scratch twice, and read the whole forum. So I'm now going to an extremity I never used before : posting my algorithm and my whole source here, hoping that someone we'll help me
The algo is simple : DP with a table l[i][j] where l[i][j] is the length of the longest matching sequence (run) of words ending exactly on word i of line 1 and word j of line 2 (included).
So if the word I of line1 and word J of line2 does not match, l[i][j] = 0, else
l[i][j]= 1+l[i-1][j-1].
Here's the corresponding source... It's driving me mad ! Any help will be really appreciated.
[cpp]
:: REMOVED 2 DAYS LATER::
[/cpp]
Thanks ![/c]

[Maxim]

Hello
I'm having WA for this problem, and after having rewrote it from scratch twice, and read the whole forum. So I'm now going to an extremity I never used before : posting my algorithm and my whole source here, hoping that someone we'll help me
The algo is simple : DP with a table l[i][j] where l[i][j] is the length of the longest matching sequence (run) of words ending exactly on word i of line 1 and word j of line 2 (included).
So if the word I of line1 and word J of line2 does not match, l[i][j] = 0, else
l[i][j]= 1+l[i-1][j-1].
Here's the corresponding source... It's driving me mad ! Any help will be really appreciated.

If i-th word of line 1 and j-th word of line 2 don't match, then l[i][j] shouldn't be 0. l[i][j] tells you the length of longest common subsequence (LCS) of first i words from line 1 and first j words from line 2. So, if they don't match, l[i][j] = max { l[i][j - 1], l[i - 1][j] }. In other words, set l[i][j] to larger from these two: LCS of first i words from line 1 and first j-1 words from line 2, or LCS of first i-1 words from line 1 and first j words from line 2.
Hope you understand it...

Maxim

[Julien Cornebise]

THANK YOU VERY MUCH Maxim !!
I finally got AC, thanks to your advice.
I perfectly understand what you mean, given that I already used that LCS algo some time ago for another problem.
The trouble was that I thought here that longest MATCH meant longest RUN, not longest SUBSEQUENCE : for me we were asked the length of the longest common RUN, not the longest common SUBSEQUENCE !!!!! The difference is in input like
a b c d e
a c e
Longest common run : 1
Longest common subsequence : 3
Somebody said that problem was too much under stated (different interpretations of blank line, non letter meaning non alpha NUMERIC, etc)... I guess it's true. But it might also be my english vocabulary that's too less developed :/
Well, THANKS once again for having clarified my mind, I remove my code from the forum...

[little joey]

Thanks!
I made exactly the same mistake four months ago when I tried to solve this problem for the first time. Now I finally got AC!

But the problem lies in the problem description and the lack of definition of "longest match". I read it as "longest match of consecutive words" in stead of "longest match of words in the same order".

They want to guess the intensions of other groups by checking the changed sections of messages. First they have to get the length of longest match.

I interpreted as finding the longest unchanged section, which would be in line with the story and would lead to my first definition of "longest match". Julien (and probably more people who got WA) must have read it the same way as I did.

To summarize:
The correct answer for

Code: Select all

This is a test.
This is not a test.

is 4, not 2.

[little joey]

Hi hi.
We were writing our postings at the same time! Julien and I said exactly the same thing.