DNA Sorting

From Progteam

Revision as of 14:32, 28 March 2007 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.


DNA Sorting
Problem Number 1007
Sorter: Uncategorized
Source: East Central North America 1998
Link: 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;
    }
}
Personal tools