UVA Problem 713 – Adding Reversed Numbers Solution

UVA Problem 713 – Adding Reversed Numbers Solution:


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

Solving Technique:

The biggest problem in this problem is that there is no built in data type to hold 200 digit numbers. Although this problem is good in sense that it says that the number can be 200 characters long.

To handle this large number array is needed. while others may have solved using integer array and their methods may be faster. But mine addition is using character array.

The problem can be solved in a few ways. One which is reversing two string. Then added leading 0’s to the smaller string then adding and printing the result.

Another method is to add trailing 0’s to smaller string if their length differ. Then add them and print the result if starting from left most column. Other wise print result in reverse if calculating from right most column.


For example using first method,

when input is 24 and 1, their reversal is,

42
01
==
43

Since i am using right most column as 0 th index. So the result will be 34.

Again for input 4358 and 754,

8534
0457
====
8991

Result will be 1998. This is because i am starting calculation from rightmost column and moving carry to left.


Another method is adding as is then print result from left,
4358
7540
====
1998

I’ve implemented the first method only. The code is explained in comments.

 

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. Please compile with c++ compiler as some of my codes are in c and some in c++.


More Inputs of This Problem on uDebug.


Input:

3
24 1
4358 754
305 794

 


Output:

34
1998
1

Code:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 1225 - Digit Counting
 * Technique: Reverse string or character array,
 *            Add padding or add leading 0's to given string,
 *            Discard leading or trailing 0's in string,
 *            Shift characters in string by given number of spaces,
 *            add two character array or strings,
 *            Adding very large numbers.
 ***********************************************************************/


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


#define N 512


static char* firstNumber;
static char* secondNumber;


static char input[N];


/*********************************************************************
 * Pass a string and a Integer length greater than the String length.
 * The function will add leading 0's to the string. The length of the
 * new string will be equal to the passes integer.
 *********************************************************************/
char* fixLength(char* number, int maxlen){


    /**
     * Calculate padding or the amount positions to shift digits to the right.
     * If length of string is 5 and maxlen is 8 then each digit starting from
     * the end will be shifted 3 places to the right.
     *
     * Ex: Original String = "25634", Modified String = "00025634"
     */
    int numLength = strlen(number);
    int padding = maxlen - numLength;


    /**
     * Starting from the end of given string shift each character to the right
     * by calculated padding.
     *
     * Character are shifted from rear otherwise beginning from 0 index will
     * replace existing character in the string and output string will be garbage.
     */
    for(int i = numLength - 1; i >= 0; --i)
        number[i + padding] = number[i];


    /**
     * Add leading 0's to empty places in the string.
     */
    for(int i = 0; i < padding; ++i)
        number[i] = '0';


    /**
     * Mark end of String
     */
    number[maxlen] = '\0';


    return number;
}



/*********************************************************************
 * Given a string and its length this function reverses the string.
 * It first discards any leading 0's in the input string then reverses
 * the input string.
 *********************************************************************/
char* reverseString( char* number, int len ){

    /**
     * Initialize a new char array to keep the string after discarding
     * and leading zeros.
     */
    char* tempNumber = new char[N];
    int k = 0, i;


    /**
     * Only discards leading zeros and not any other internal zeros.
     */
    for(i = 0; i < len; ++i)
        if(number[i] - '0') break;
    for(; i < len; ++i)
        tempNumber[k++] = number[i];
    tempNumber[k] = '\0';


    /**
     * Reverse the new string without leading zeros.
     */
    int tmp = k / 2;
    for(int i = 0, j = k - 1; i < tmp; ++i, --j){
        int swap = tempNumber[i];
        tempNumber[i] = tempNumber[j];
        tempNumber[j] = swap;
    }


    return tempNumber;
}



/**********************************************************************************
 * Starting from the last column add two integers. Then add any carry to the left
 * column. This way calculate the addition. In the end if any carry left add it
 * to the output char array. For safety assume last carry can be bigger than one
 * digit.
 **********************************************************************************/
void add( char* firstNumber, char* secondNumber, int lengthFirst, int lengthSecond){

    /**
     * Initialize a new array to keep sum of two number strings.
     */
    char* tempNumber = new char[N];
    int k = 0;
    int sum = 0;
    int carry = 0;


    /**
     * Starting from last column move left to 0th index. Add the numbers and if there
     * is carry add it to left column.
     */
    for(int j = lengthFirst - 1; j >= 0; --j){

        // Add two number
        sum = firstNumber[j] - '0' + secondNumber[j] - '0';

        // Add if any previous carry
        sum = sum + carry;

        // place the part of output number
        tempNumber[k++] = (sum % 10) + '0';

        // calculate the the carry
        carry = sum / 10;
    }

    /**
     * Assuming last carry can be more than one digit. Add carry digits to output array.
     */
    while(carry){
        tempNumber[k++] = (carry % 10) + '0';
        carry /= 10;
    }
    tempNumber[k] = '\0';


    /**
     * Discard any leading 0's before printing. Only discards leading 0's and nothing else.
     */
    int p = 0;
    for(; p < k; ++p)
        if(tempNumber[p] - '0') break;

    for(; p < k; ++p)
        printf("%c", tempNumber[p]);
    printf("\n");

}


int main() {

    /**
     * Important allocate memory for the numbers.
     */
    firstNumber = new char[N];
    secondNumber = new char[N];


    int n;

    scanf("%d", &n);
    getchar();


    while(n--){

        int j = 0, k = 0;

        /**
         * Take input of two numbers as strings.
         */
        scanf("%s%s", firstNumber, secondNumber);


        /**
         * Get each of their length.
         */
        int firstNumberLength = strlen(firstNumber);
        int secondNumberLength = strlen(secondNumber);


        /**
         * Initial guess the first number string is bigger.
         */
        int maxlen = firstNumberLength;


        /**
         * Reverse both of the number string.
         */
        firstNumber = reverseString(firstNumber, firstNumberLength);
        secondNumber = reverseString(secondNumber, secondNumberLength);


        /**
         * Add padding to the strings calling fixlength function.
         * Pass in the smaller number string and bigger number string size.
         *
         * If initial guess of first number is bigger is wrong then update
         * the max length with second number length.
         */
        if( firstNumberLength < secondNumberLength ){
            firstNumber = fixLength(firstNumber, secondNumberLength);
            maxlen = secondNumberLength;
        }
        else
            secondNumber = fixLength(secondNumber, firstNumberLength);


        /**
         * Now pass in the two numbers and max length to add them and print answer.
         * Notice here i pass the same argument twice this need to be fixed and also
         * there are many more improvements needed in other functions.
         */
        add(firstNumber, secondNumber, maxlen, maxlen);

    }

	return 0;
}

UVA Problem 10405 – Longest Common Subsequence Solution

UVA Problem 10405 – Longest Common Subsequence Solution:


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

Solving Technique:

This one is a fun problem. For this problem we need to find Longest Common Sub Sequence length of two given strings. We can solve this using LCS Algorithm discussed in Introduction to Algorithms book. This algorithm is explained in Wikipedia and other programming language implementations can be found here.

I have provided two dynamic programming implementations below with one top down memoized ( *Slower ) and a bottom up ( *Faster ) solution.

Take the string inputs carefully there may be empty lines in between.

Overview:

Simple explanation for solution technique is we apply Dynamic Programming techniques. There are overlapping sub problems that we can combine to get original solutions.

Starting from the end of both strings. If both of the characters in string are same then we can reduce both string size by 1 length. So now if do the reverse meaning add 1 we get original solution.

In case both characters are not same keeping one string same we reduce the other one by 1 length and try to match the last characters again.

This way if two characters are  same we increase LCS length count. Among the sub problem we choose the one with longest length.

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:

bcacbcabbaccbab
bccabccbbabacbc

a1b2c3d4e
zz1yy2xx3ww4vv

abcdgh
aedfhr

abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0

abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

 


Output:

11
4
3
26
14

Bottom Up Memoized Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10405 Longest Common Subsequence ( LCS )
 * Method:  Memorized Recursive / Top Down Solution
 */

#include<stdio.h>;
#include<string.h>;
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
    return a > b ? a : b;
}

/*
 * If the value is not -1 then it means the value of that sub problem is
 * already calculated. Just return that calculated value
 * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
 * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
 */
int LCS(int i, int j){
    if(lcs[i][j] != -1)
        return lcs[i][j];

    if(x[i-1] == y[j-1])
        lcs[i][j] = LCS(i-1, j-1) + 1;
    else
        lcs[i][j] = maxval( LCS(i-1, j), LCS(i, j-1) );

    return lcs[i][j];
}

int main(){
    register unsigned i, j;
	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * Set -1 to all positions to indicate there are no calculated value
         */
        for(i = 1; i <= xlen; ++i)
            for(j = 1; j <= ylen; ++j)
                lcs[i][j] = -1;

        printf("%d\n", LCS(xlen,ylen) );

	}
	return 0;
}

Top Down DP Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10405 Longest Common Subsequence ( LCS )
 * Method:  Top Down Dynamic Programming Solution
 */

#include<stdio.h>
#include<string.h>
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
    return a > b ? a : b;
}

int main(){
    register int i, j;

	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
         * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
         */
        for(i = 1; i <= xlen; ++i){
            for(j = 1; j <= ylen; ++j){
                if(x[i-1] == y[j-1])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = maxval(lcs[i-1][j], lcs[i][j-1]);
            }
        }

        /*
         * The max length is at the bottom right corner of the table
         */
        printf("%d\n", lcs[xlen][ylen] );

	}
	return 0;
}

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

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 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 */

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print

Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print:

Code Explanation:

This code is bit complex and will require knowledge on:

  1. Struct
  2. Linked list
  3. Queue
  4. Stack
  5. Binary Tree ( check this and this too  )

Input Format:

Level Order tree input style
Level Order tree input style
binary Tree Graph sample Input for the console picture shown above
binary Tree Graph sample Input for the console picture shown above

Code:

/*
 * Author: Quickgrid
 * Code: Tree creation, traversal in array & linked list ( inorder/preorder/postorder/levelorder )
 * Description:
 */

#include <stdio.h>

#define size 1000   /* used this for queue array */

struct tree{    /* binary tree structure */
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree node;

struct stack{   /* linear/singly linked list stack to hold tree type data */
    node *nodedata;
    struct stack *next;
};
typedef struct stack vertex;

node* q[size];  /* here our array is node data type that we defined above */
int f = 0, r = 0;
vertex *front = NULL, *rear = NULL;
node *root = NULL;

void enq(node *root){   /* circular queue array modular arithmetic */
    int s = (r+1) % (size+1); /* +1 means we don't use 1 box of the array */
    if(f == s){
        printf("Queue Full.\n");
        return;
    }
    q[s] = root; /* root is node type we put it in our node array */
    r = s;  /* s is temporary variable */
}

node *deq(){
    if(f==r){
        printf("Queue Empty.\n");
        return NULL;
    }
    f = (f+1)%(size+1);
    node *temp = q[f]; /* get the last element of the queue to return for further operations */
    q[f] = 0;
    return temp;
}

void levelOrderArray(node *root){
    enq(root);  /* here we enqueue the root or the node that we want to star from */
    while(f!=r){ /* check if our queue is not empty */
        node *v = deq(); /* dequeue one item */
        printf("%c ", v->data);
        if(v->left!=NULL){ /* check if left branch of tree exists */
           enq(v->left); /* send the left node to queue */
        }
        if(v->right!=NULL){ /* check if right branch of tree exists */
            enq(v->right); /* send the right node to queue */
        }
    }
}

void enqueue(node *root){   /* enqueue function for our stack in linked list */
    if(front == NULL){
        front = new vertex();
        front->nodedata = root;
        front->next = NULL;
        rear = front;
    }else{
        vertex *temp = new vertex();
        temp->nodedata = root;
        temp->next = NULL;
        rear->next = temp;
        rear = temp;
    }
}

vertex *dequeue(){
    if(front == NULL){
        printf("queue empty.\n");
        return front;
    }
    vertex *temp,*tmp = front;
    front = front->next;
    delete temp;
    return tmp;
}

void levelorder (node *root){
    enqueue(root);
    while ( front != NULL ){
        vertex *v = dequeue();  /* we dequeue one vertex type data from our vertex stack */
        if(v!=NULL){
            printf("%c",v->nodedata->data);

            if (v->nodedata->left != NULL){ /* nodedata is our data part which holds node type data */
                enqueue(v->nodedata->left);
            }
            if (v->nodedata->right != NULL){
                enqueue(v->nodedata->right);
            }
        }
    }
}

int treeHeight(node *root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight){
        return leftHeight+1;
    }else{
        return rightHeight+1;
    }
}

void printGivenLevel(node *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%c ", root->data);
    }else if(level > 1){
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void createBinaryTree (node *root)
{
    char ans;

    fflush(stdout);
    printf("%c has any left child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create left side of a tree node */
    {
        root->left = new node ();
        root->left->left = NULL;
        root->left->right = NULL;
        fflush(stdout);
        printf("Enter left data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->left->data);
        createBinaryTree (root->left);  /* recursive call with created node as root to check if it has left and right */
    }

    fflush(stdout);
    printf("%c has any right child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create right side of a tree node */
    {
        root->right = new node ();
        root->right->left = NULL;
        root->right->right = NULL;
        fflush(stdout);
        printf("Enter right data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->right->data);
        createBinaryTree (root->right);
    }
}

void postOrder(node *root){
    if(root->left!=NULL){
        postOrder(root->left);
    }
    if(root->right!=NULL){
        postOrder(root->right);
    }
    printf("%c ", root->data);
}

void preOrder(node *root){
    printf("%c ", root->data);
    if(root->left!=NULL){   /* check if left side of that node exist */
        preOrder(root->left);   /* recursive call of preorder using this node as the root */
    }
    if(root->right!=NULL){
        preOrder(root->right);
    }
}

void inOrder(node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%c ", root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
}

int main ()
{
    char ans;
    fflush(stdout);
    printf("Do u want to create a tree: ");
    fflush(stdin);
    ans = getchar();

    root = new node ();
    fflush(stdout);
    printf("Enter root of tree: ");
    fflush(stdin);
    scanf("%c",&root->data);
    createBinaryTree(root);

    int height = treeHeight(root);
    printf("\nTree Height: %d", height);

    printf("\nLevel order Linked List: ");
    levelorder(root);   /* Instead of sending root we can send another node to level order from that node */
    printf("\nLevel order Array: ");
    levelOrderArray(root);
    printf("\nPre order : ");
    preOrder(root);
    printf("\nIn order : ");
    inOrder(root);
    printf("\nPost order : ");
    postOrder(root);

    printf("\nEnter level to print:");
    int level;
    scanf("%d", &level);
    if(level >= height || level < 1){
        printf("\nGiven level doesn't exist.");
    }else{
        printf("Level %d: ", level);
        printGivenLevel(root, level);
        printf("\n");
    }
    return 0;
}

UVA Problem 12541 ( Birthdates ) Solution

UVA Problem 12541 ( Birthdates ) Solution:


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

Solving Technique:

Rank 363, Run time 9 ms ( 0.009 s ).

This problem seems easy at first glance but requires some thinking. There will be only two output.

First one will be the name of the youngest person ( The person whose was born after everyone ). Meaning his/her birth year, month, date is greater than others. Ex, a person born on 1991 is younger than person born on 1990.

Second one will be the name of the oldest person ( The person whose was born before everyone ). Meaning his/her birth year, month, date is less than others. Ex, a person born on 1990 is older than person born on 1991.

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


Code Explanation:

Since the name doesn’t exceed 15 letter so an array of size 16 ( i use 1 more for safety ) will suffice. Next there are 4 inputs each time. One is name string, the rest are integers such as date, month and year respectively.

Since the inputs are all related I used a struct to keep all data in a structure named person.

Now I use two more struct variable named young and old. By default I set both of them to first value of our structure. Now I compare if year is greater I set young to that struct variable in that loop. If less than I set old to the struct variable in that loop. If both of these are not true then I follow the same logic for month and date.

In the and the young and old struct variable get set to youngest and oldest struct variable based on logic.

Since I only need to print the youngest and oldest person name so, I just access our young and old structure with name property using dot operator and print them each on a new line.


Input:

10
Machel 31 12 4999
Amar 27 9 1991
Conrad 1 1 1999
Kara 18 9 5001
Tom 29 1 1991
Priyanka 1 12 5001
Melissa 25 10 1991
Ping 16 10 5001
Amidala 10 1 1991
Xena 17 10 5001

Output:

Priyanka
Amidala

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12541 ( Birth dates  )
 */
 
#include<stdio.h>

struct person{
    char name[16];
    unsigned int date, month, year;
};

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

    scanf("%u", &n);

    struct person p[n], maxp, minp;

    for(; i<n; ++i){
        scanf("%s%u%u%u", &p[i].name, &p[i].date, &p[i].month, &p[i].year);
    }

    maxp = p[0];    /*younger person*/
    minp = p[0];    /*older person*/

    for(i=0; i<n; ++i){
        if(p[i].year > maxp.year)
            maxp = p[i];

        else if(p[i].year < minp.year)
            minp = p[i];

        else{
            if(p[i].month > maxp.month && p[i].year >= maxp.year)
                maxp = p[i];

            else if(p[i].month < minp.month && p[i].year <= minp.year)
                minp = p[i];

            else{
                if(p[i].date > maxp.date && p[i].month >= maxp.month && p[i].year >= maxp.year)
                    maxp = p[i];
                else if(p[i].date < minp.date && p[i].month <= minp.month && p[i].year <= minp.year)
                    minp = p[i];
            }
        }

    }

    printf("%s\n%s\n", maxp.name, minp.name);

    return 0;
}

UVA Problem 12289 ( One Two Three ) Solution

UVA Problem 12289 ( One Two Three ) Solution:


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

Solving Technique:

Very very easy problem. It requires us to only print 1 or 2 or 3 based on input.

There are only 3 types of string (one, two, three) input and among them only one character is changed for each input. Also Their length is always the same.

So the very basic idea that comes to mind is any input with length of five must be three ( since length doesn’t change ). Now if that is not true it can either be one or two.


Code Explanation:

I took a different approach for my code. Instead of including another header file and calling a function to get the string length, I simply checked if the third position in the array ( array starts from zero ) is not a NULL character. If there is no NULL character in that position then I simply outputted 3. Why? because the string three does not contain a NULL character in position 3.

Now above is not true then I check if the string is one or two. If i only check for sub-strings ( part of strings ) in one and find any two characters of ‘o’, ‘n’, ‘e’ then it is definitely one. Then print 1. Else simply print 2.


Input:

3
owe
too
theee

Output:

1
2
3

Code:

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

#include<stdio.h>

#define O 111
#define N 110
#define E 101

static char s[8];

int main(){
    register unsigned n;
    scanf("%u", &n);

    while (n--){
        scanf("%s", s);
        if (s[3]){
            printf("3\n");
        }else{
            unsigned s0 = s[0];
            unsigned s1 = s[1];
            unsigned s2 = s[2];
            if ((s0 == O && s1 == N) || (s1 == N && s2 == E) || (s0 == O && s2 == E))
                printf("1\n");
            else
                printf("2\n");
        }
    }
    return 0;
}

UVA Problem 591 ( Box of Bricks ) Solution

UVA Problem 591 ( Box of Bricks ) Solution:


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

Solving Technique:

If we read this problem carefully then there are a some very important clues,

  1. make all stacks the same height (line 2)
  2. he sets out to rearrange the bricks, one by one (line 3)
  3. The total number of bricks will be divisible by the number of stacks (line 7)

From the above points and problems description it is clear that Little Bob can only move the blocks one by one. Also the first line of input will be less or equal to 50 and the block heights will be less than or equal to 100. So we can use integer ( also unsigned integer ) for them.

Another thing it is said that dividing sum of stack heights with stack count is always possible. Meaning that gives us the height of the wall ( total stacks height sum, h[i] / stack count, n ).

The technique is there can be three types of box stack. That is equal to, less than or greater than height of the wall( total stacks height sum, h[i] / stack count, n ).

Since Bob can move boxes one by one it doesn’t matter which stack to start from. We can find the number of blocks to move from by only subtracting those stack that are greater in height than the max wall height. No need to perform this action on stacks that are equal or less high than max wall height.

So the result is the sum of subtraction of each stacks that are greater than from ( all stack sum / stack count ). Also since blocks are moved one by one this is the final result.

Important:   We normally print a new line after each output line but for this problem asks us to Output a blank line after each set. Meaning with our normal line break we need to add another line break. Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

  1. First I take the stack count and loop that many times. [ also reset moves, and c ( count ) variable each time ]
  2. Now for each loop I take the height of stack in an array and sum it.
  3. Next I find the wall height by dividing the sum with stack count.
  4. Now I use another loop to loop through the array. In it subtract elements greater than stack height and also sum up this value to moves ( number of box movement needed ).
  5. Lastly I print in the exact format the problem asked.
  6. One more thing I printed an extra newline because the problem asked for a blank line after each set.

Input:

6
5 2 4 1 7 5
0

Output:

Set #1
The minimum number of moves is 5.

Code:

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

#include<stdio.h>

static int a[128];

int main(){
    register int i, c = 1;
    int n, sum, maxHeight, moves, temp;

    while (scanf("%d", &n) && n){
        moves = sum = 0;

        for (i = 0; i < n; ++i){
            scanf("%d", &a[i]);
            sum += a[i];
        }

        maxHeight = sum / n;

        for (i = 0; i < n; ++i){
            if(a[i] > maxHeight)
                moves += a[i] - maxHeight;
        }

        printf("Set #%d\nThe minimum number of moves is %d.\n\n", c++, moves);
    }
    return 0;
}

UVA Problem 10324 ( Zeros and Ones ) Solution

UVA Problem 10324 ( Zeros and Ones ) Solution:


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

Solving Technique:

Here I have provided naive solution for this problem which is very slow. This code can be solved much much faster. I’ll update to it later.

This One was painful. Got Runtime Error a few times before solving this. Still my best time for this so far is 1.899 sec. My main problem was that it said the problem could end with both an EOF or a new line character. The main problem was new line. So I used getchar() ( found it here one of the best sites for contest programming ) and checked for EOF and string length in the string input while condition.

The problem is quite descriptive. It says our string or character array size can be 1000000The string will contain only ‘0’ and ‘1’ characters. Basically we are to find if the characters between the given interval min(i,j)  and max(i,j)Meaning check for the characters from the minimum number between i or j to the maximum number of i or j.

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


Code Explanation:

Here the input format is first take a string or character array ( of size 1000000 ) and next take an integer which is the number if inputs to come. Now loop that many times and take two integers ( i and j ) every loop.

I used a flag named works which is set to 1 by default and use this to check condition if the characters match or not.

Now i loop thorough the given interval ( i and jto check if the character in the given interval are same.

In the loop i check every character of the interval string with the first character of that given interval. Since all character need to be same to output is this code is valid.

Now in the loop if any character doesn’t match I set the flag ( works ) to 0, print No since all characters don’t match and break from loop immediately. 

Next thing I check if flag is 1 then I print Yes.

Lastly the getchar()


Input:

0000011111
3
0 5
4 2
5 9
01010101010101010101010101111111111111111111111111111111111110000000000000000
5
4 4
25 60
1 3
62 76
24 62
1
1
0 0

Output:

Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
No
Yes
No
Case 3:
Yes

Code Naive Solution ( Slow ):

/**
 * Author:  Quickgrid ( Asif Ahmed )
 * Site:    https://quickgrid.wordpress.com
 * Problem: UVA 10324 - Zeros and Ones
 */

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

#define N 1000000

static char s[N];


int main(){

    int i;
    int works, c = 1;
    int n, a, b;


    while(gets(s)){

        scanf("%d", &n);
        printf("Case %d:\n", c++);

        while( n-- ){

            works = 1;

            scanf("%d%d",&a,&b);

            if(a == b){
                printf("Yes\n");
                continue;
            }

            if(a > b){
                for(i = b; i <= a; ++i){
                    if(s[i] != s[a]){
                        works = 0;
                        printf("No\n");
                        break;
                    }
                }
            }else{
                for(i = a; i <= b; ++i){
                    if(s[i] != s[a]){
                        works = 0;
                        printf("No\n");
                        break;
                    }
                }
            }

            if(works)
                printf("Yes\n");

        }
        getchar();
    }
    return 0;
}