Brute Force Approach

The basic idea is to take the two parents and produce both possible children for each pair of crossover points using the method described in the question. You will need nested loops for this, and the number of children produced this way will be proportional to ~n^2~ where ~n~ is the length of the parents. Then for each possible child, you compare it to the target child that was given and count the number of differences. This count represents the number of mutations that would have had to happen to result in the given child. The smallest number you get is the one you use to compute mutation rate.

Because the counting that happens at each step of the algorithm runs in time proportional to ~n~, the total amount of time to compare all children is proportional to ~n^3~. This is feasible for small problems but bogs down when ~n~ gets close to ~10\,000~. If you use this method you will not have time to complete all the test cases.

A Better Approach

You might notice that in the above you are duplicating a lot of work. There are at least two better approaches that run in time proportional to ~n^2~. Can you figure out an efficient solution? If you have an idea, post it to the appropriate discussion forum at compsci.ca.

If two children differ only by one place in one of their crossover points, they can only differ in mutation count by ~1~ at the most. So a better solution than the default described in the solutions document would be to take advantage of the similarity between children. One way to do this is to start with a "base mutation count" for each parent (i.e. the number of differences between that parent and the target child) and then increase or decrease these counts if necessary as you change the crossover points, keeping track of the minimum as you go.

This approach is a little tricky to get exactly right, but it is much faster – it runs in time proportional to ~n^2~ instead of ~n^3~, and that's a big difference when ~n = 10\,000~!