DNA Sorting

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by hjfreyer.

 Sorter: Uncategorized East Central North America 1998 http://acm.pku.edu.cn/JudgeOnline/problem?id=1007

DNA Sorting is problem number 1007 on the Peking University ACM site. The idea of the problem is to find the "unsortedness" of a given string, in this particular example, it happens to be a string of DNA, but the solution applies to any string.

The unsortedness of a string is defined to be the number of pairs of entries that are out of order with respect to each other. More concretely: for every letter in the string, how many letters are there to the right of it, which should be to the left. After finding this figure, sort the strings by their disorder, and print them out.

(Note: I believe the same figure is achieved when you reverse the words "left" and "right" but I have not proven this)

Algorithm

The obvious n^2 solution is in fact the correct one (n^2 is fine because each string has at most 50 letters). For each letter in the string, count through all the letters to it's right. Keep a count of all such letters that come before it lexicographically. After looping through each letter, the total count you have represents the disorder of the string. Find out the disorder for each entry, sort them though however means you like, and print them.

Solution

```import java.util.*;

public class Main{

public static Scanner in;
public static StringBuilder out;

public static int STRLEN;

public static Entry[] ents;

public static void main(String[] args){
in=new Scanner(System.in);
out=new StringBuilder();

doStuff();

System.out.println(out);
}

public static void doStuff(){
//Read in the length of the string and how many there are
STRLEN=in.nextInt();
int N=in.nextInt();

//ents is an array of pairs of Strings and Disorder
ents=new Entry[N];

for(int i=0;i<N;i++){
ents[i]=new Entry();
//Solve the problem
solve(i);
}

//They want the output sorted
Arrays.sort(ents);

//Prinnit!
for(Entry e:ents){
System.out.println(e);
}
}

public static void solve(int k){
ents[k].str=in.next();
ents[k].disorder=0;

String tmp=ents[k].str;

//n^2 is fine because the number of letters is small

//For each letter in the string
for(int i=0;i<tmp.length();i++)
//Check each letter to its right
for(int j=i+1;j<tmp.length();j++)
//If it belongs on its left
if(tmp.charAt(j)<tmp.charAt(i))
//Increase the counter
++ents[k].disorder;
}
}

class Entry implements Comparable{

String str;
int disorder;

public int compareTo(Object o){

if(!(o instanceof Entry))
throw new AssertionError();

Entry e=(Entry) o;

if(disorder==e.disorder)
return 0;
return (disorder>e.disorder)?1:-1;
}

public String toString(){
return str;
}
}
```