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

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

Re: 760 - DNA Sequencing

Post by amyth469 »

magurmach wrote: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
I also have the same problem magurmach..
What did you do to get AC ?
mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 760 - DNA Sequencing

Post by mostafiz93 »

In problem statement it is said that "prints as output the longest common sequence(s) in lexicographical order.", but i got WA submitting the common Sub-sequences. I changed my dp function to print the continuous sequences and got accepted.

So, don't think "common sequence" as sub-sequence. :)
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 760 - DNA Sequencing

Post by brianfry713 »

Input:

Code: Select all

tgtgcattcgcggcacaagagtcccgggtccctgtagctttgatcagctcgaatccatttagatctttagctcgcagcgaacaaggcgaaaagacccggcccgttctaaatactttagatgttgtgtggattctcggaagatggcaagatagctcgtggaaatctacaacgagggtgaagtaggctcgttgtcaggataaggtccaacaatttaagcgcgatactgcctccatggaagcaggcaacgctttcctaaacctaaccatcaaaaggcagtgtctcag
gtgagttacgccaacaacagtagcgaaagtaccgcttatgggtaggagtagcacaactatcaaaacttcgacctccacttgaagcagttacgacgatttgattccgacccatcaataaccaatagttaccgcatacattcgtgttactaagattaactaaagcaacctgggcagatgcgggcgaggattattggtacgttgaaggatccattcatcatgtttctagtcccatcatcacacccaactccgcgagttgaccgacagcttcgtatgacccaatcatttgt

gtctttggctcgtagccta
cttttccgtgtgcctggcccagtgttcggggttacccttaacggaacactccagttaaagggtagggcaactgtagtcgggctatctccctctcctctgcctgtcgagcactcgtgtgtatgcctaggcccagtttttagtcagtcggtagcgtattaagccgcaagtcaagcagaccggcctcgcgacgaacgccacgccgtagaaccgtttggatctgttggactaaaccgacgagtgccaatg
AC output:

Code: Select all

atcaaaa
atccatt
ccaacaa
ccatcaa
gaagcag

cgtag
ctcgt
gccta
gtagc
tttgg
?????, on my machine, your code at http://ideone.com/ZEtUF is printing:

Code: Select all

atcaaaa
atccatt
ccaacaa
ccatcaa
gaagcag

cgtagaa
ctcgttt
gcctaaa
gtagcaa
tttggag
Check input and AC output for thousands of problems on uDebug!
Bidhan
New poster
Posts: 6
Joined: Mon May 17, 2010 5:07 pm
Location: University Of Dhaka, Bangladesh.
Contact:

Re: 760 - DNA Sequencing

Post by Bidhan »

If you don't know the reason of getting wrong answer.
1. Given strings can be empty.
2. Same longest common sequences can be found twice, in which case you should print that only once.

Input

Code: Select all

a


bidbi
bi
Output

Code: Select all

No common sequence.

bi
Post Reply

Return to “Volume 7 (700-799)”