UVA Problem 10327 – Flip Sort Solution

UVA Problem 10327 – Flip Sort Solution:


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

Solving Technique:

Another sorting problem that requires us to “exchange two adjacent terms”. Use any stable sort to count the number of swaps. That is the output.

Here among three code the first one is a hybrid distribution between insertion sort and merge sort to count inversions / swaps. The next two codes are merge sort and bubble sort.

This merge sort also be made to work with selection sort. Please see Introduction to Algorithms book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein for more detail.

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:

3
1 2 3
3
2 3 1

Output:

Minimum exchange operations : 0
Minimum exchange operations : 2

Hybrid Merge Sort and Insertion Sort Distribution:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

#define INSERTION_SORT_THERSHOLD 20

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid - front + 1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void insertionSort(int front, int rear) {
    register int i, j;
    int key;

    for (i = front + 1; i <= rear; ++i) {
        key = A[i];
        j = i - 1;
        while (j >= front && A[j] > key) {
            A[j + 1] = A[j];
            ++c;
            --j;
        }
        A[j + 1] = key;
    }
}

/**
 * Hybrid distribution between insertion sort and merge sort
 * Performs slower than regular merge sort for this small input range
 * Such distribution also works with selection sort
 * Please refer to book introduction to algorithm for more
 */
void HybridMergesort(int front, int rear){
    if(rear - front < INSERTION_SORT_THERSHOLD)
        insertionSort(front, rear);
    if(front < rear){
       int mid = (rear + front) >> 1;
       HybridMergesort(front, mid);
       HybridMergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);

        HybridMergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Merge Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);
        Mergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Bubble Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<cstdio>
#include<iostream>

static unsigned a[1024];

int main(){
    register unsigned int i, j, k, n;
	while(scanf("%u", &n) == 1){
        for(i = 0; i < n; ++i)
            scanf("%u", &a[i]);

        /**
         * Bubble Sort
         */
        for(k = j = 0; j < n; ++j){
            for(i = 0; i < n - j - 1; ++i){
                if(a[i] > a[i + 1]){
                    std::swap(a[i], a[i + 1]);
                    ++k;
                }
            }
        }

        printf("Minimum exchange operations : %u\n", k);
	}
	return 0;
}
Advertisements

UVA Problem 299 – Train Swapping Solution

UVA Problem 299 – Train Swapping Solution:


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

Solving Technique:

The problem specifically asks to “find the least number of swaps of two adjacent carriages necessary to order the train”. That’s it.

It is a sorting problem and we have to count the number of swap between adjacent carriages. So a stable must be applied. Here I have provided three codes with insertion sort, bubble sort, merge sort.

Even though merge sort is O(n lg n) because input size is so small ( 0 <= L <= 50 ) it doesn’t make much difference. For Bubble sort though no need to perform swaps 🙂 just count it. A hybrid between insertion and merge sort me be a slight performance booster. I will try to include it later.

The problem UVA 11462 age sort is solved also with merge sort among other sort algorithms. A commented version merge sort can be found there.

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:

3
3
1 3 2
4
4 3 2 1
2
2 1

Output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Code ( Bubble Sort No Swap ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Bubble Sort No Swap)
 */

#include<stdio.h>

/**
 * c is swap count
 */
static int A[64], c;

int main(){
    int n, i, j, m;
    scanf("%d", &n);

    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Bubble Sort
         */
        for(i = 0; i < m - 1; ++i){
            for(j = i + 1; j < m; ++j){
                /**
                 * No need to swap elements
                 * This code may be moved input loop
                 */
                if(A[i] > A[j])
                    ++c;
            }
        }

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Code ( Insertion Sort ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Insertion Sort)
 */

#include<stdio.h>

static int A[64], c;

int main(){
    register int n, i, j;
    int m, key;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Insertion sort using inner for loop
         */
        for(i = 1; i < m; ++i){
            key = A[i];
            for(j = i - 1; j >= 0 && A[j] > key; --j){
                A[j + 1] = A[j];
                ++c;
            }
            A[j + 1] = key;
        }

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Code ( Merge Sort Swap Count ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Merge Sort)
 */

#include<stdio.h>
#include<limits.h>

static int A[64], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    int n, i, j, m;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * To understand Merge sort see my UVA solution age sort 11462
         */
        Mergesort(0, m - 1);

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Insertion Sort Best Case Time Complexity Analysis

Insertion Sort Best Case Time Complexity Analysis:

Insertion Sort Code:

for (/*c1*/ i = 1; /*c2*/ i < n; /*c3*/ ++i){
     /*c4*/ key = A[i];
     /*c5*/ j = i - 1;
     /*c6*/ while (j >= 0 && key < A[j]){
        /*c7*/ A[j+1] = A[j];
        /*c8*/ --j;
    }
    /*c9*/ A[j+1] = key;
}

Analysis:

Let, c1, c2, c3… be micro instructions for a particular command. Let input size, n = 6. Now setting n = 6 in the code above we find this relation below.

Micro Instructions    Times (Number of times it was executed)
==================    =======================================
              c1 -----> 1
              c2 -----> 6 -----> ( n )
              c3 -----> 5 -----> ( n - 1 )
              c4 -----> 5 -----> ( n - 1 )
              c5 -----> 5 -----> ( n - 1 )
              c6 -----> 5 -----> ( n - 1 )
              c7 -----> 0
              c8 -----> 0
              c9 -----> 5 -----> ( n - 1 )

Explanation:

Our input instance size was 6. Here (c1) always executes only once. But the for loop condition (c3) executes 6 times since our for loop counter is initialized to 1 instead of 0.

For 1 its checks condition once. Finds 1 < 6 true continues loop.
For 2 its checks condition once. Finds 2 < 6 true continues loop.
For 3 its checks condition once. Finds 3 < 6 true continues loop.
For 4 its checks condition once. Finds 4 < 6 true continues loop.
For 5 its checks condition once. Finds 5 < 6 true continues loop.
For 6 its checks condition once. Finds 6 < 6 false exits the loop.

Since the loop counter begins at 1 so condition is checked from 1 to n times. For the nth time even though it results in false but condition is executed to get that false result. The loop condition (c2) is checked 6 times (n) but it enters the loop 5 times (n-1). So for this algorithm if the input size is (n) the condition will be checked (n) times. The last check 6 < 6 is false. So it breaks the loop.

Inside the loop in any case (c4, c5, c6, c9) is always executed in the best case. But in the event of best case the while loop condition becomes false. So instructions inside while loop ( c7, c8 ) are never executed. For this reason we have a faster runtime.

For insertion sort the best case is input is already sorted in the desired order. So it never enters the while loop since key is never less/greater ( depending on ascending or descending order sort ) than its previous elements.

The loop increment is executed (n – 1) times because when it enters the loop for the first time the increment is not executed.


So we can write,

T(n) = summation of micro instructions * number of times executed

T(6) = c1 + n*c2 + (n-1)*c3 + (n-1)*c4 + (n-1)*c5 + (n-1)*c6 + 0*c7 + 0*c8 + (n-1)*c9

     = (c1 - c2 - c3 - c4 - c5 - c6 - c9) + n * (c2 + c3 + c4 +c5 + c6 + c9)  [multiplying and rearranging constants]

     = b + n * a  [ Let, sum of constants, c1 - c2 - c3 - c4 - c5 - c6 - c9 = b, c2 + c3 + c4 +c5 + c6 + c9 = a ]

     = an + b

     = Ω(n)

Lower Bound,

We represent asymptotic lower bounds with big – Ω ( Big Omega ) notation. So the lower bound for insertion sort is Big Omega of n.

Ω(n)


Now,

T(n) = an + b

we know,
y = mx + c
f(x) = mx + c

From this we can see these equations are similar and our equation matches linear equation. If we plot the graph of an+b for different values of n we will see that it is a straight line. So for any value of n it will give us linear time. Even as input size gets very large our time complexity will always be linear. So, we can write this as Ω(n). Also known as Big Omega.

UVA Problem 10041 – Vito’s Family Solution

UVA Problem 10041 – Vito’s Family Solution:


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

Solving Technique:

This is a sorting problem. It requires us minimize the distance from Vito’s to every other house. That distance must be median because median value minimizes the distance from every side. So the median is the position of Vito’s house.

The problem requires us to find, “minimal sum of distances from the optimal Vito’s house to each one of his relatives”. So this means we calculate distance from Vito’s house ( Median ) to every other house and sum them. Meaning subtract position of every house from Vito’s house and sum their distance.

I have provided Three commented codes below. First one uses STL Sort and doesn’t calculate absolute value for distance. Second one shows the use of Insertion Sort and calculates absolute value to find their distance. The last one uses vector to store data and STL algorithm to find nth element in an array. Here ( for this code ) the calculated nth element is the median.

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:

2
2 2 4
3 2 4 6

 


Output:

2
4

Code ( Without Calculating Absolute Value ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<cstdio>
#include<algorithm>

static int A[512];

int main(){
	register int n, m, i, j;
	scanf("%d", &n);

	while (n--){
        scanf("%d", &m);

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            int dist = 0, median, key;

            for (i = 0; i < m; ++i)
                scanf("%d", &A[i]);

            /**
             * Sort the input using stl sort
             * Instead of using sorting algorithm, Try to implement Selection Algorithm to find Median in O(n) time
             */
            std::sort(A, A + m);

            /**
             * Find median dividing by two or shifting bit to left once
             * here, key is the value of median
             */
            median = m >> 1;
            key = A[median];

            /**
             * here, dist is the summation of distance of every house
             * Any value less than Median can subtracted from median will result in a positive value
             */
            for (i = 0; i< median; ++i)
                dist += key - A[i];

            /**
             * No need calculate for the median so start from (median + 1)
             * In case of value greater than Median, the Median must be subtracted from that value for positive number
             * Also by removing duplicates of median we may speed up the code
             */
            for (i = median + 1; i < m; ++i)
                dist += A[i] - key;

            printf("%d\n", dist);
        }
	}
	return 0;
}

 

Code ( Insertion Sort ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<stdio.h>
#include<stdlib.h>

static int A[512];

int main(){
	register int n,m,i,j;
	scanf("%d", &n);

	while (n--){
        scanf("%d", &m);
        int dist = 0, median, key;

        for (i = 0; i < m; ++i){
            scanf("%d", &A[i]);
        }

        /**
         * Insertion Sort:
         * Two portions sorted and unsorted
         */
        for (i = 1; i < m; ++i){
            key = A[i];
            j = i - 1;

            /**
             * Compare every element with sorted portion ( elements to its left )
             */
            while (j >= 0 && A[j] > key){

                /**
                 * While comparing shift items to right until the comparison is false
                 */
                A[j + 1] = A[j];
                --j;
            }

            /**
             * When comparison is False or done, we found the sorted position for that element so we insert it in that position
             */
            A[j + 1] = key;
        }

        /**
         * Find Median value, left shift once is divided by Two
         */
        key = A[m >> 1];

        /**
         * Since elements after Median is bigger than Median So, we need to find absolute value of them
         */
        for (i = 0; i < m; ++i){
            dist += abs(key - A[i]);
        }

        printf("%d\n", dist);
	}
	return 0;
}

 

Code ( using vector & n-th element to find median ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>

using namespace std;

int main(){
    register int n, m, i, j;
    int key, num;
    vector<int> v;

    scanf("%d", &n);
    while (n--){
        scanf("%d", &m);

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            /**
             * Input an a value and push it to vector
             */
            v.clear();
            for (i = 0; i < m; ++i){
                scanf("%d", &num);
                v.push_back(num);
            }

            /**
             * sort for median
             */
            nth_element(v.begin(), v.begin() + v.size()/2, v.end());

            /**
             * Get the value of median
             */
            key = v[v.size()/2];

            /**
             * Get distance of every value from median
             */
            int dist = 0;
            for (j = 0; j < i; ++j)
                dist += abs(key - v[j]);

            printf("%d\n", dist);

        }
    }
    return 0;
}

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;
}