UVa 612

From Algorithmist

Contents 1 612 - DNA Sorting 2 Summary 3 Explanation 4 Optimizations 5 Implementation 6 Input 7 Output

[edit] 612 - DNA Sorting

• http://acm.uva.es/p/v6/612.html

[edit] Summary

A straight forward problem where we are required to sort strings by how many inversions they contain.

[edit] Explanation

We have to sort a group of equal length strings by their inversion count. An inversion is an out of order pair, or more formally, the inversion set of an array is the set of pairs {(i,j):i < j and A_i > A_j}. Since the strings are relatively short, a simple check all pairs O(n²) solution will suffice to count the number of inversions in each string. Remember that we need to break ties by keeping things in order, so a stable sort is required.

[edit] Optimizations

Since the string alphabet is so small, consisting of only 4 symbols, A, C, G, and T, we can do the inversion count in 4n = O(n) time with a dynamic programming algorithm. We maintain a 4 by n array that keeps track of at index i how many occurances of each character there are after the ith character in the string.

[edit] Implementation

In C++, the STL's stable_sort can be used to considerably improve coding time.

[edit] Input

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

[edit] Output

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA