mit-dna
You have been given a sequence of DNA strands D1, D2, ... DN from animals 1,2,..., n. The strand D1 is from some ancient animal that no longer roams the Earth today, and Di is the DNA of a child of animal i-1 for i > 1. All strands are the same length. Unfortunately, some of the strand samples are in bad shape, so the researchers who gave you this DNA were unable to figure out all of the bases for all of the strands. Thus, each DNA strand is a sequence of characters from the {A,T,C,G,*} , where * means that the researchers were unable to figure out the base at that location, and {A,T,C,G} represent real bases.
As a computer scientist, you have come up with an idea of
automatically figuring out what bases the *'s should be. As evolution is a slow process, you figure that *'s should be filled
in so that there is not too much change between any two adjacent DNA strands. Thus, you want to replace each * with one of the
characters A, T, [], or G so as to minimize the maximum Hamming distance between the DNA of any parent and their immediate child (the Hamming distance between two strings is the number of locations in which they differ).
(1 <= N <= 2000) and K (1 <= K <= 2000), followed by a newline. K is the length of each DNA strand. What follows are N lines, where the ith line is K characters long and represents the DNA strand Di. The DNA strands will only consist of characters A, T, C, G, or *.
[c]2 2
A*
*T
Output:
0Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.