online-judge.uva.es

by **sidky** » Mon Feb 09, 2004 5:23 pm

Actually, this is not a Longest Common Subsequence problem. Instead, you have to find the longest common substring of the given DNA strands.

the output for angga888's input:

Code: Select all: aa

not

Code: Select all: aaaa <---- Wrong

by **angga888** » Thu Feb 12, 2004 9:53 am

Thanks sidky, I get AC now.

Regards,
angga888

by **jackie** » Tue Jul 27, 2004 5:34 am

Yes. sidky is right. The problem isn't decribled clearly,.

I got AC using DP algorithm.

Pay attention to the blank line and two complete different strings in the input file which make the answer is "No common sequence.".

by **Jan** » Fri Sep 02, 2005 12:19 am

Can anyony give me some difficult test cases?

Thanks in advance.

by **Jan** » Fri Sep 02, 2005 12:19 pm

Finally got Accepted.

Thanks.

by **Jan** » Fri Sep 02, 2005 12:24 pm

Did you handle the blank lines correctly?

Just try the following input output set.

Input:

Code: Select all: atgc tga atgc gctg at gcc t tgc atc gggg actccccccc tcccccccccccccc aattggcc ttggggcc aattggcc ccggttaa a t a ata tat aaatttcccggg gggaaacccttt aaatttcc tttttttttatttttaattcc aaaggaaaaa aacaa

Output:

Code: Select all: tg gc tg No common sequence. No common sequence. No common sequence. No common sequence. tccccccc ggcc ttgg aa cc gg tt No common sequence. No common sequence. No common sequence. at ta aaa ccc ggg ttt aatt attt ttcc aa

Hope it helps.

by **pineapple** » Tue Jan 30, 2007 7:41 am

I always get WA at 0.07*s.Who can tell me what's wrong with my code?Thanks very much!

The following is my code:

Code: Select all: Cut after AC

by **Vexorian** » Tue Jan 30, 2007 4:59 pm

Try Jan's I/O at: http://online-judge.uva.es/board/viewtopic.php?t=2919

by **pineapple** » Fri Feb 09, 2007 9:45 am

OK!Thanks for your help.
But I also can handle the blank lines,and give the same output.
I have no idea why I always get WA.

by **Vexorian** » Sat Feb 10, 2007 1:58 pm

I can't think of anything besides that there shouldn't be a \n at the end of the output but just between different results, but that should be PE not WA.

For what is worth, dp was not needed in this problem.

by **pineapple** » Sun Feb 11, 2007 2:58 pm

Thanks for your help.It's my careless,I write:

Code: Select all: first==false;

instead of

Code: Select all: first=false;

But I have corrected it the day before yesterday.You can see my code above.Now I still get many WAs,maybe there is someting wrong in my algorithm?Please help me.
If you have get Accepted,could you show me some cases I can't handle?

by **rio** » Sun Feb 11, 2007 3:06 pm

Vexorian wrote:For what is worth, dp was not needed in this problem.

I agree. Using DP makes it complex.

How about using more simple approach?

by **jurajz** » Mon Oct 12, 2009 8:28 pm

rio wrote:How about using more simple approach?

I don't know, if my approach is more simple, but I solved this problem with trie.

by **magurmach** » Fri May 18, 2012 11:25 am

Used SA and then kept all the ans in a set so that it gets ordered in lexicographical way.

But getting WA!
Please help.

code link:
Removed after AC

by **amyth469** » Thu May 31, 2012 1:13 pm

@magurmach
What did you do to get AC ?
I also have the same problem as you had.
please help..

online-judge.uva.es

760 - DNA Sequencing

760 WA

Re:

Re: 760 - DNA Sequencing

Re: 760 - DNA Sequencing

Who is online