UVA Problem 11462 – Age Sort Solution

UVA Problem 11462 – Age Sort Solution:


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

Solving Technique:

First of all a warning. This is going to be a very very very long post. For this problem i will use various divide and conquer algorithms ( Ex: quick sort, merge sort etc ) & techniques to solve.

The best Solution here takes 0.502 s ( 502 ms ) . If you are looking for a very fast solution this is not the right place. But these code can be optimized to create a very fast solution.  Also sorts such as bubble sort, selection sort, insertion sort, replacement sort won’t be able to sort in time. So you’ll get TLE if you use these sort.

Lets begin:

This is a sorting problem. The only trouble here is the huge count of test cases. But there’s very important line most miss including me. That is ” no individual in that country lives for 100 or more years “. So we may have many many test cases but no input age is more than 100. 🙂

Now lets look at our solution menu,

1. Counting sort ( Just count occurrence of each values, then print them 0 to 100 for ascending order).

2. Binary Merge sort ( 2 partition ).

3. Ternary Merge sort ( 3 partition ).

4. Quick sort ( 2 partition ).

5. Quick sort ( 3 partition ).


The first solution code here ( counting sort ) runs the fastest since it just count elements at each index and prints them. This solution may be made faster by using combination of fread, fwrite, strtok, atoi, stringstream ( <sstream> ) . Although i haven’t used them. If i get time I will try to implement them in future.

I used the other sorts here just demonstrate implementation of merge sort and quick sort algorithms. I may include more sorting algorithms for this problem in future. All codes are well commented take a look below and try to understand their logic.

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:

5
3 4 2 1 5
5
2 3 2 3 1
0

Output:

1 2 3 4 5
1 2 2 3 3

Counting Sort Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Counting Sort
 */

#include<stdio.h>
#include<string.h>

static unsigned A[128];

int main(){
    register unsigned n, i, c;
    unsigned num;
    while(scanf("%u", &n) && n){             /* Test cases */
        memset(A, 0, sizeof A);              /* Clear memory for each test case */
        for(i = n; i; --i){                  /* Exits Loop when i is 0 */
            scanf("%u", &num);
            ++A[num];                        /* Since input is never greater than 100, we can use that as index and count occurrence of that index */
        }
        c = i = 1;                           /* i starts from 1 since i is never 0  */
        for(; i<100; ++i){
            while(A[i]--){                   /* Decrease number count at that index */
                if(c == n) printf("%u", i);  /* For the last item in sorted output there is no space */
                else{
                    printf("%u ", i);        /* Just print the index since that was our original input */
                    ++c;                     /* Counter to check if the last element is reached */
                }
            }
        }
        printf("\n");                        /* Print a new line for each test case */
    }
    return 0;
}

 Counting Sort Code ( Usage of stringstream, *slower ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Description: stringstream demo
 */

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>

using namespace std;

static unsigned A[128];

int main(){
    register unsigned n, c, i;
    unsigned num;
    string B;
    while(1){
        scanf("%u", &n); getchar();
        if(!n) return 0;

        memset(A, 0, sizeof A);
        getline(cin, B);

        stringstream ss;
        ss << B;
        while(ss >> num)
            ++A[num];


        c = i = 1;
        for(; i < 100; ++i){
            while(A[i]--){
                if(c == n) printf("%u", i);
                else{
                    printf("%u ", i);
                    ++c;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

 Binary Merge Sort Code ( 2 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Binary Merge Sort ( 2 Partition )
 */

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

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid, register unsigned rear){
    register unsigned n1 = mid-front+1;         /* Calculate size of left half of the array */
    register unsigned n2 = rear - mid;          /* Calculate size of right half of the array */

    unsigned *L = new unsigned[n1 + 1];     /* Dynamically create and allocate calculated amount of memory */
    unsigned *R = new unsigned[n2 + 1];     /* plus 1 to hold Infinity or A Very large value for which any input can't be larger than */

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front+i];                          /* Copy elements from given original array to left sub array */

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];                          /* Copy elements from given original array to right sub array */


    L[n1] = INT_MAX;                                /* In the last position of sub array set a very large value */
    R[n2] = INT_MAX;
    i = j = 0;

    register unsigned k = front;                /* Instead of wasting space creating a new array, we can use the original large array since we have already copied all items to sub arrays */
    for(; k <= rear; ++k){
        if(L[i] <= R[j])
            A[k] = L[i++];             /* Compare and copy smaller elements of sub arrays onto original array */
        else
            A[k] = R[j++];
    }
}

void Mergesort(register unsigned front, register unsigned rear){
    if(front < rear){
       register unsigned mid = (rear+front) >> 1;  /* Find the mid point of the array */
                                                    /* Shift bits to right once, equivalent of divided by TWO */

       Mergesort(front, mid);                       /* Recursively divide array in left portion */
       Mergesort(mid+1, rear);                      /* Recursively divide array in right portion */

       Merge(front, mid, rear);                     /* Merge the divided array back again in sorted order */
    }
}

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

        Mergesort(0, n-1);                          /* Call merge sort function for each test case */

        for(i = 0; i<n; ++i){
            printf("%u", A[i]);
            if(i != n - 1)
                printf(" ");                 /* Do not print a space after last sorted item */
        }
        printf("\n");
    }
    return 0;
}

 Ternary Merge Sort Code ( 3 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Ternary Merge Sort ( 3 Partition )
 */

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

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid1, register unsigned mid2, register unsigned rear){
    /*
     * Calculate size for creating sub array
     * In this case calculate size for three sub arrays
     */
    unsigned n1 = mid1 - front + 1;
    unsigned n2 = mid2 - mid1;
    unsigned n3 = rear - mid2;

    /*
     * Dynamically allocate memory for three sub arrays
     * Here Plus One because we will set a very large value for last position of the array
     */
    unsigned *L = new unsigned[n1 + 1];
    unsigned *R = new unsigned[n2 + 1];
    unsigned *X = new unsigned[n3 + 1];

    /*
     * Copy 1/3 of original array to sub arrays
     * First 1/3 to L array, next 1/3 to R array, last 1/3 to X array
     */
    register  int i = 0;
    for(; i<n1; ++i)
        L[i] = A[front + i];

    for(i=0; i<n2; ++i)
        R[i] = A[mid1 + 1 + i];

    for(i = 0; i < n3; ++i)
        X[i] = A[mid2 + 1 + i];

    /*
     * INT_MAX is found in <limits.h>
     * Instead of traversing the whole array increasing runtime
     * We can compare every element again a very large value which will always be grater than or equal to any input
     */
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    X[n3] = INT_MAX;

    /*
     * Reset index counter for sorting
     */
    i = 0;
    register unsigned p = 0, j = 0, k = front;

    /*
     * Sort:
     * Compare items of each array against each other
     * Copy back the smaller item from the comparison to original array
     */
    for(; k <= rear; ++k){
        if(L[i] <= R[j] && L[i] <= X[p]){
            A[k] = L[i];
            ++i;
        }else if(R[j] <= X[p]){
            A[k] = R[j];
            ++j;
        }else{
            A[k] = X[p];
            ++p;
        }
    }
}

void Mergesort(register int front, register int rear){
    /*
     * Check if there is only One element in array
     */
    if(front < rear){
        /*
         * calculate the size of 1/3 of array
         * Now calculate two mid points since it is 3 way partition
         */
        register int dist = (rear - front + 1) / 3;
        int mid1 = front + dist;
        int mid2 = mid1 + dist;

        /*
         * Recursively call this array cutting down original array by 1/3 ( One Third )
         */
        Mergesort(front, mid1);
        Mergesort(mid1 + 1, mid2);
        Mergesort(mid2 + 1, rear);

        /*
         * Merge divided elements back into original array
         */
        Merge(front, mid1, mid2, rear);
    }
}

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

        /*
         * Merge sort from index 0 to index n-1
         */
        Mergesort(0, n - 1);

        for(i = 0; i < n; ++i){
            printf("%u", A[i]);
            /*
             * For the last sorted element do not print a space
             */
            if(i != n-1)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

 Quick Sort Code ( 2 Partition ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 11462 ( Age sort )
 * Solution Method: Quick Sort ( 2 Partition )
 */
#include<cstdio>
#include<iostream>

#define SIZE 2000002

static int A[SIZE];

void quicksort (int *a, register int n) {
    register int i, j, mid;
    if (n < 2) return;

    mid = a[n >> 1];

    for (i = 0, j = n - 1; ; i++, j--) {
        while (a[i] < mid)
            i++;
        while (mid < a[j])
            j--;

        if (i >= j) break;
        std::swap(a[i], a[j]);
    }
    quicksort(a, i);
    quicksort(a + i, n - i);
}

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

        quicksort(A, n);

        for (i = 0; i < n; i++)
            printf("%d%s", A[i], i == n - 1 ? "\n" : " ");

    }
    return 0;
}

 Quick Sort Code ( 3 Partition ):

/* To Do */
Advertisements

One thought on “UVA Problem 11462 – Age Sort 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