GCPC11B - Genetic Fraud

no tags 

Computer Scientists have a rough life. Due to the shortage of bright young minds like yourself, good programmers are mostly like famous movie stars. It's just like everyone wants to get their hands on your hard earned cash. The situation got so out of hand that you are faced by a lawsuit nearly every day of the year. Each lawsuit is filed by someone claiming alimonies for your alleged child. Luckily for you, you know pretty much about genetic sequences. You know that the human DNA sequence can be represented by a possibly N characters long string, containing only characters 'a' to 'z'. And you know that a similarity test of the DNA strings of the alleged child to your own can prove your innocence.

The only problem is that this does not only happen to you. As all labs are busy, testing needs at least a year. Still, not all hope is lost. You managed to get the information from one of the DNA labs on how to compute the probability of a genetic relationship between two DNA strings. If you could only help the DNA labs to test two DNA strings for a genetic relationship really fast, you could get the evidence you need for your own lawsuits.

A genetic relationship test, or GRT, requires some heavy computation on the DNA strings. They first acquire all similar regions within two DNA strings. We understand a region within a DNA string to be a consecutive interval within the DNA string. Regions a[i..i+l] (0 ≤ i < N-l) and b[j..j+l] (0 ≤ j < N-l) of DNA strings a, b are similar to each other, if |a[i+k] - b[j+k]| ≤ 1 for 0 ≤ k ≤ l. A GRT between two DNA sequences is positive, whenever the two DNA sequences have a similar region of at least one half the length of the DNA sequences.


The first line of the input gives the number of test cases C (0 < C ≤ 1000). The first line of each such test case holds an integer N (1 ≤ N ≤ 1000), denoting the length of the two DNA strings to be tested. The following two lines contain a string of N lower-case letters each, giving the two DNA substrings of the two persons to test.


For each test case print one line. If the GRT is positive, print out POSITIVE. Print NEGATIVE, if the test fails.




hide comments
Goldie: 2011-12-21 12:24:53

Give some more TCs for positive result.

Jose Luis Castrillon Garrido: 2011-08-30 14:49:03

Thank you very much

Adrian Kuegel: 2011-08-30 10:05:53

I just took a look at your solution. I think KMP does not work, because we allow not only exact matches, but also ones with character difference 1. Example: search for pattern bcd in the text cdbd. KMP will match up to position 2 in the text, then shift the pattern by one position and claim that letter b matches letter d and continue with matching the second character of the pattern with the third character in the string.

Last edit: 2011-08-30 10:17:00
Jose Luis Castrillon Garrido: 2011-08-29 21:56:06

Does binSearch+KMP work here??

Adrian Kuegel: 2011-08-10 13:43:13

yes, for all k

যোবায়ের: 2011-08-08 16:17:13

"DNA strings a, b are similar to each other, if |a[i+k] - b[j+k]| ≤ 1 for 0 ≤ k ≤ l"
does it mean for all k ?

Adrian Kuegel: 2011-08-08 10:30:19

it is 25

biQar: 2011-08-08 08:39:47

what is the difference between 'a' & 'z' ?

abhijith reddy d: 2011-07-30 06:51:47

Be careful when N is odd.

Added by:Adrian Kuegel
Time limit:2.989s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Moritz Kobitzsch)