UVA Problem 612 – DNA Sorting Solution

UVA Problem 612 – DNA Sorting Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The best solution for this problem took 0.020 s. Mine took 0.142 s. There is an efficient algorithm to solve this problem. My approach is brute force, check all possible combination and count. Besides solving the problem another goal was implement some less used techniques/concepts.

So the problem basically requires us to sort and print strings based on sortedness. The way to calculate this is,

  1. The way to calculate this sortness is to take a string and compare each characters to its right.
  2. If the character on the right are smaller than the current character we increase the inversion count.
  3. The greater the count the less sorted ( confused!! ) a string is. ( Please do this with pen and paper )

Another thing to note is that if inversion count for multiple string is same then we should print the string that was given to us first. Last thing is print a blank line after each test case.

Now this code may look confusing,

char **s = new char*[t+1];

It is a way to declare an array of strings in C. The [t+1] initializes the string count. We need use a for loop to initialize string size for each strings. That is,

s[i] = new char[w+1];

Here s[i] is a string. We allocate memory for it using new char[w+1].

Here I used bubble sort to sort the strings. At first i tried selection sort and failed miserably because it doesn’t maintain the relative ordering of the strings. So using the sort I am sorting in ascending order. Also sort the inversion count array since it is mapped to strings array. Swap is a built-in function.

std::swap(inv[j], inv[j+1]); /* Swap the inversion count */
std::swap(s[j], s[j+1]);

Now that you understand the problem time to go write a better solution :).

Update (Added Insertion Sort):

I have added insertion sort for this code. Any stable sort such as insertion, merge sort etc should also work.
Just copy the code below and replace the bubble sort marked portion of code with this insertion sort code. It runs a bit faster than bubble sort. Also don’t forget to add include cstring header file.

/*
 * Insertion Sort
 */
unsigned key;
int q;
char *strkey = new char[w + 1];
for(i = 1; i < t; ++i){
    key = inv[i];
    strcpy(strkey, s[i]);
    q = i - 1;
    while(q >= 0 && inv[q] > key){
        inv[q + 1] = inv[q];
        strcpy(s[q + 1], s[q]);
        --q;
    }
    inv[q + 1] = key;
    strcpy(s[q + 1], strkey);
}

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

1

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

Output:

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

Code ( Using Bubble Sort ):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 * Problem UVA 612 (DNA Sorting)
 */

#include<cstdio>
#include<iostream>

int main(){
    register unsigned n,i,j,k;
    unsigned blank = 0;

    scanf("%u", &n);
    while (n--){
        unsigned w,t;
        scanf("%u%u", &w, &t);

        /* Array of strings, initialize element count */
        char **s = new char *[t + 1];
        /* Mapping array for sortedness count */
        unsigned *inv = new unsigned[t + 1];

        for (i = 0; i < t; ++i){
            /* Initialize size of each string in array */
            s[i] = new char[w + 1];
            scanf("%s", s[i]);
            inv[i] = j = 0;
            for (; j < w; ++j){
                for (k = j + 1; k < w; ++k){
                    if (s[i][j] > s[i][k])
                        /* Count sortedness, number of inversions */
                        ++inv[i];
                }
            }
        }

        /*
         * Bubble sort
         * Any stable sort should be able to sort it correctly e.g. insertion sort, merge sort
         */
        for (i = 0; i < t - 1; ++i){
            for (j = 0; j < t - i - 1; ++j){
                if (inv[j] > inv[j+1]){
                    /* Swap the inversion count */
                    std::swap(inv[j], inv[j+1]);
                    /* Swap the strings */
                    std::swap(s[j], s[j+1]);
                }
            }
        }

        /* Print a blank line for consecutive test cases */
        if (blank) printf("\n");
        blank = 1;

        for (i = 0; i < t; ++i)
            printf("%s\n", s[i]);
    }
    return 0;
}
Advertisements

2 thoughts on “UVA Problem 612 – DNA Sorting Solution

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s