UVa 612

From Algorithmist
Jump to: navigation, search

612 - DNA Sorting[edit]

Summary[edit]

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

Explanation[edit]

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^{2}) 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.

Optimizations[edit]

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.

Implementation[edit]

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

Input[edit]

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Output[edit]

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Solutions[edit]