SPOJ Problem : Hint for MUTDNA
Actually, I think post a solution’s source code of an online judge problem is like spoiling movie. If you;re actually a coder, I think you don’t need to read this. But, if you’re a novice coder and look for a hint in this problem, I think I can help you XD.
First, read the problem properly.
Biologists have discovered a strange DNA molecule, best described as a sequence of N characters from the set {A, B}. An unlikely sequence of mutations has resulted in a DNA strand consisting only of A's.
Biologists found that very odd, so they began studying the mutations in greater detail.
They discovered two types of mutations. One type results in changing a single character of the sequence (A → B or B → A). The second type changes a whole prefix of the sequence, specifically replacing all characters in positions from 1 to K (for some K between 1 and N, inclusive) with the other character (A with B, B with A).
Compute the least possible number of mutations that could convert the starting molecule to its end state (containing only A characters). Mutations can occur in any order.
Did you get the idea?
You have a sequence of A and B string (for example, I just take AABB).
You can mutation the string either A to B or B to A in the following rule :
1. Just change 1 gen in the random position
2. Change a series of gen from start position until it reach flip position. For example, I can flip AABAB to BBBAB. Start position is A and I flip the series of A to B until it reach B position.
Your goal is to make all letter in this sequence A with a minimum mutation. Can’t you think a solution?
.
.
.
.
.
.
.
.
.
.
Ok, I have two solution for this problem.
First, is a Dynamic Programming Forward solution. I think this is too difficult to explain.
Second, is just an Ad-Hoc. Yeah...! I’ll explain this solution. Let’s make an example AAABBBABA.
First thing that I think of this problem’s solution is brute force.
With rule 1, we can change all of the B to the A. It take 4 mutations.
With rule 2, we can flip all the series with this order (AAABBBABA, BBBBBBABA, AAAAAAABA, BBBBBBBBA, AAAAAAAAA). It take same mutation, 4 mutations.
But, look at the 3rd order. It’s so ienefficient to mutate just 1 B with two times, we can directly flip it right? Okay, if we directly flip it, we have 3 mutation. It’s the minimum answer.
Did you get the idea? Okay. My algorithm is so simple, here it is.
1. From the start we count from 0
2. If there are a series of letter that contain more than 1 Bs, add 2 mutation
3. But, if there is just 1 B, add 1 mutation
However, there are a case that this algorithm didn’t work, do you know which case? Yeah, for example BBBAAABA
It took 2 mutation, but if you use the algorithm above, you got 3 mutation. We can’t just test the first letter is B or not, because there is also a case that it didn’t work. Now, how we can fix this?
Okay. Now, I have an idea. How about we have a variable named X that responsible for the changing series.
We set the X variable is ‘A’ and if there is a sequence of ‘B’ we change the X to ‘B’ and increment the answer. Except if we just detect a single letter that didn’t match the series we can just flip it directly.
For example :
X = A, ans = 0
Because the ‘BBBAAABA’ is start with B series, we add 1 to ans and change X to B so
X = B, ans = 1
And the next series is A in the 4th position so
X = A, ans = 2
And flip the random B appear in 7th position so
X = A, ans = 3
Still wrong? Okay, we change the initial value of X with ‘B’. Actually I know that I’m wrong because if we start with ‘B’ we can make sure that we just flip once if the first gen is B.
Example :
X = B, ans = 0
Series change in the 4th position
X = A, ans = 1
And flip random B in 7th position
X = A, ans = 2
So the algorithm is :
1. Let X = ‘B’ and ans = 0
2. Begin at the first, if we found a series of letter that different from X increment ans and change X with the series
3. Except if there is just 1 letter, we just increment ans and go ahead without change the X
But, you still get WA with that algorithm, why?
Because, with this algorithm we just guarantee that the DNA is mutate to a sequence of same letter. So it’s possible that the DNA is mutate to BBBBBB too. So, what’s the solution?
Of course, we can guarantee that the sequence is AAAAA by backward approach. Starting with X = ‘A’ and go backward with the same algorithm.
Hope this will help.