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

Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore


Post by junjieliang »

Isn't this problem LCS? Then why is it for the first input the output is "tg", instead of "tgc"?

Thanx :smile:.
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am


Post by necropower »

hey guys , i noticed that the input and the output for the first case is kind of odd.
it shows "atgc","tgc"
but the output is "tg"
isnt it "tgc"???
can u explain that?

[[]]'s Necropower
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

In the problem description:

So, the longest common sequence in the two strands atgc and tga is tg.

Is the sample input have typo??
My accetped program will output "tgc "for "atgc" and "tgc".........
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am

Post by necropower »

(i am using @ instead of interrogation, my keyboard is broken)

did u get accepted@
can u tell me your main idea of searching in strings@ my program is too slow and i didnt find a better way to search on the strings...

A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

I think my algorithm is quite "brute force"

let's say there is string A, B

First check if the last char of B is a substring of A,
if yes, copy the last 2 chars and check again
if no, copy the last 2nd char to check......

just run like this......
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany

Post by Stefan Pochmann »

Hmm... I'm confused... is it the longest common subsequence problem or the longest common substring problem? Of course there's no real definition in the problem, but it sounds like the subsequence problem. On the other hand, your approach sounds more like the substring problem? What is it?
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Yes, this question is to find sub-string...
Den Raskovalov
New poster
Posts: 2
Joined: Tue Apr 09, 2002 4:32 pm
Location: Russia, Ekaterinburg

Post by Den Raskovalov »

Note: Sequence should be continious!
Also there is error in sample output.
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK

Post by Caesum »

The question says:
If there are more than one test cases, it must be a blank line between two consecutive, both in input and output files.
So I use 3 gets's to read the two strings and the next blank, however the next 'blank' line is not always a blank line ? Can anyone confirm the input format for me please ?
Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

I've used

Code: Select all

while(scanf("%s %s\n", s1, s2) == 2) ...
and it was enough to get PE.
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am

Post by gvcormac »

It is a common *substring* problem (I agree that the problem is ill-specified.)

The fastest possible algorithm (linear time) is to build a suffix tree. If you search the web you'll find references and code.
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm


Post by Eric3k »

Prog 760, DNA sequencing, http://acm.uva.es/p/v7/760.html, in the first input, it has atgc and tgc and the corresponging output tg. However, shouldn't it be tgc?
New poster
Posts: 6
Joined: Tue Sep 24, 2002 8:00 pm
Location: Iasi, Romania

Post by negue »

Yes. They probably meant atgc and tga as input.

Can someone give me some clues or i/o samples, because I guess I'm doing it right but I get wa.

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

760 - DNA Sequencing

Post by angga888 »

I got lot of WA for this problem.
Could someone please tell me the output of this input:
Any tricky I/O for this problem?

Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York


Post by sohel »

I am also getting WA for this problem.

Isn't simply LCS;

I applied LCS and sorted all the answers lexicographically and avoided repetition. Shouldn't it be enough.
Post Reply

Return to “Volume 7 (700-799)”