TAP2015G - Generating alien DNA II

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

There is a fundamental and unchanging characteristic shared by all life on Earth, from the tiniest microbe to whales, dinosaurs and human beings: DNA. This is the only known mechanism for the transmission and replication of genetic information, which poses one of the most important questions in modern biology: is DNA the only way to encode this information, or are there other possible mechanisms?

Professor Gould is a theoretical exobiologist whose research considers the possibility of the existence of extra-terrestrial life not having its genetic information encoded as DNA. Presently, he is developing a model based on the encoding of genetic information in the form of a chain of pseudo-nucleotides, which we will represent with the characters 'b', 'd', 'o', 'p', 'q', 'v', 'w' and 'x'. Each pseudo-nucleotide has a conjugate: 'o', 'v', 'w' and 'x' are each its own conjugate, whereas 'b' is the conjugate of 'd', 'p' is the conjugate of 'q', and conversely 'd' is the conjugate of 'b' and 'q' is the conjugate of 'p'.

In the model developed by professor Gould, an organism can suffer a mutation starting from a given position in its pseudo-nucleotide chain, resulting in the inversion and conjugation of the second part of said chain. Specifically, if the original pseudo-nucleotide chain is a1 a2 ... aN and the mutation occurs starting from position i, the resulting pseudo-nucleotide chain is a1 a2 ... ai-1 ãN ãN-1 ... ãi+1 ãi, where ãk represents the conjugate of the pseudo-nucleotide originally at position k.

As it evolves, an organism may suffer many mutations in this manner, the only restriction being that successive mutations should occur starting from positions which are ever closer to the end of the pseudo-nucleotide chain. For example, the chain "bdopqvwx" can suffer a mutation starting from position 3 resulting in the chain "bdxwvpqo", and after that another mutation starting from position  7 giving thus the chain "bdxwvpop", but these two mutations couldn't have occurred the other way around.

At this point in his research, professor Gould has two pseudo-nucleotide chains which are particularly interesting, and he would like to know the minimum number of mutations the first of them must suffer in order to become the second one. Can you help him?



There are multiple test cases in the input file. For each test case, the first line contains an integer N, representing the length of both pseudo-nucleotide chains to be analyzed (1 ≤ N ≤ 1000). Each of the following two lines contains a string of N characters 'b', 'd', 'o', 'p', 'q', 'v', 'w' and 'x', representing a pseudo-nucleotide chain.



For each test case, print one line containing an integer representing the minimum number of mutations the first chain in the input should suffer in order to become the second one. If this is not possible, print the number -1.





hide comments
rajat_kumar: 2016-08-31 22:12:52

my code is passing all the random generated test cases but getting WA on spoj,anybody any sugestion

Added by:Fidel Schaposnik
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Argentinian Programming Tournament 2015