OJ Board

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

Maxim

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

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.

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

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.

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

Hi..

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


Can somenone who got AC tell me the output for this please..
My code output:
Thanks!

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.

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?

I tried everything and still WA.. grr.!

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[j] where l[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[j] = 0, else
l[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]

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

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 foris 4, not 2.

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