760 - DNA Sequencing

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky »

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

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 »

Thanks sidky, I get AC now. :D

Regards,
angga888

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie »

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Can anyony give me some difficult test cases?

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Finally got Accepted. :D

Thanks.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

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

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

760 WA

Post by pineapple »

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
Last edited by pineapple on Fri Aug 10, 2007 12:05 pm, edited 3 times in total.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian »


pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple »

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.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian »

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.

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple »

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?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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?

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re:

Post by jurajz »

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

magurmach
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

Re: 760 - DNA Sequencing

Post by magurmach »

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

amyth469
New poster
Posts: 2
Joined: Thu May 31, 2012 1:07 pm

Re: 760 - DNA Sequencing

Post by amyth469 »

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

Post Reply

Return to “Volume 7 (700-799)”