UVA Problem 357 – Let Me Count The Ways Solution

UVA Problem 357 – Let Me Count The Ways Solution:


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

Solving Technique:

At first have a look at UVA 674 – Coin Change. Both of these can be solved with dynamic programming and they are almost same with only minor differences. Again we are asked to count the number of ways we can distribute given amount of money with 1, 5, 10, 25, 50 Dollar coins.

One gotcha for this problem is that output is so large int can’t hold that value. Using long or long long can solve this problem. Rest just modify the while loop as the given output format.

Here the first code is almost the same as the coin change problem. In the previous code i split the loops in two ways. But here in the second code I combined all the loops into a single loop. Although this may be slower.

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:

17 
11
4

Output:

There are 6 ways to produce 17 cents change. 
There are 4 ways to produce 11 cents change. 
There is only 1 way to produce 4 cents change.

Split Loop Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 357 – Let Me Count The Ways Solution
 */

#include<stdio.h>
#define N 30002

static long long a[N];
static const long long coins[4] = {5, 10, 25, 50};

int main(){
    register unsigned long long i, j;
	long long n;

    for(i = 0; i < N; ++i)
        a[i] = 1;

    for(i = 0; i < 4; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[j - coins[i]];
    }

	while(scanf("%lld", &n) == 1){
        if(a[n] == 1)
            printf("There is only %lld way to produce %lld cents change.\n", a[n], n);
        else
            printf("There are %lld ways to produce %lld cents change.\n", a[n], n);
    }
	return 0;
}

Combined / Loop Fusion:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 357 – Let Me Count The Ways Solution
 */

#include<stdio.h>
#define N 30002

static long long a[N];
static const unsigned coins[5] = {1, 5, 10, 25, 50};

int main(){
    register unsigned int i, j;
	unsigned n;

    /**
     * This is a bit slower than split loop version
     * In problem 674 i split the loop in two different ways
     * We can apply this for both UVA problem 357 and 674
     */
    a[0] = 1;
    for(i = 0; i < 5; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[j - coins[i]];
    }

	while(scanf("%lld", &n) == 1){
        if(a[n] == 1)
            printf("There is only %lld way to produce %u cents change.\n", a[n], n);
        else
            printf("There are %lld ways to produce %u cents change.\n", a[n], n);
    }
	return 0;
}
Advertisements

UVA Problem 674 – Coin Change Solution

UVA Problem 674 – Coin Change Solution:


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

Solving Technique:

Given 5 types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. We are to calculate the number of ways the input amount can be distributed with this coins.

This problem is a bit harder. It can be solved with dynamic programming or using greedy technique. Use bottom up technique instead of top down to speed it up.

We can also replace this,

 for(i = 5; i < N; ++i)
        a[i] = a[i - 1];

with this since we know no matter what the input it is always possible to give 1 cents,

for(j = 0; j < N; ++j)
        a[j] = 1;

It is hard to visualize without drawing the recursion tree or the array. The first 20 indexes of the array looks like this,

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Coins: 1 1 1 1 1 2 2 2 2 2 4  4  4  4  4  6  6  6  6  6  9

Explanation:

/* TO DO */

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:

11
26
5
4

Output:

4
13
2
1

Code Bottom Up:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 674 Coin Change
 */

#include <stdio.h>
#define N 8000

static int a[N] = {1, 1, 1, 1, 1};
static const int coins[4] = {5, 10, 25, 50};

int main()
{
    register int i, j;

    for(i = 5; i < N; ++i)
        a[i] = a[i - 1];

    for(i = 0; i < 4; ++i){
        for(j = coins[i]; j < N; ++j)
            a[j] += a[ j - coins[i] ];
    }

    int n;
    while(scanf("%d", &n) == 1)
        printf("%d\n", a[n]);

    return 0;
}

Loop Fission Variant:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 674 Coin Change
 */

#include <stdio.h>

#define N 8000
#define M 5

static int a[N] = {1, 1, 1, 1, 1};

int main()
{
    register int i, j;

    for(j = M; j < N; ++j)
        a[j] += a[j - 1];

    for(j = 5; j < N; ++j)
        a[j] += a[j - 5];

    for(j = 10; j < N; ++j)
        a[j] += a[j - 10];

    for(j = 25; j < N; ++j)
        a[j] += a[j - 25];

    for(j = 50; j < N; ++j)
        a[j] += a[j - 50];

    int n;
    while(scanf("%d", &n) == 1)
        printf("%d\n", a[n]);

    return 0;
}

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

UVA Problem 10082 – WERTYU Solution

UVA Problem 10082 – WERTYU Solution:


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

Solving Technique:

Read the first paragraph and input section carefully. This is a simple mapping problem.

The problem is that the keyboard is broken and every key that was pressed its immediate right character was printed. So we have to reverse that procedure by mapping every input character to the character to its left based on the given keyboard.

Generating the keyboard layout is easy. We can use an array and lay them sequentially so when we find a character we print the character that is to its left.

If we only use array to layout keyboard then for every input we will need to search the whole array. We can fix this by mapping the layout array to another array beforehand only once. Then just access that index and print.

Here the first code below is mapping from predefined lookup table. The second one does brute force to find its match. Here I have used stringstream but c++ string or c char array can also be used.

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:

O S, GOMR YPFSU/

Output:

I AM FINE TODAY.

Code (Mapping from predefined Lookup table):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10082 WERTYU ( using c++ string stream )
 */

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

#define N 256

/**
 * Predefined keyboard layout
 */
static const char kb[64] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
static char s[N], A[N];

void createTable(){
    /**
     * space character does not change
     */
    A[' '] = ' ';

    /**
     * Create keyboard layout from broken keyboard
     */
    register int i = 0;
    for(; kb[i]; ++i)
        A[kb[i+1]] = kb[i];
}

int main(){
    std::ios_base::sync_with_stdio(NULL);
    std::cin.tie(0);
    register int i, j;

    /**
     * Create the keyboard layout beforehand
     */
    createTable();

	while(gets(s)){
        /**
         * Create a string stream from table to print all together
         * We can also use string and add each character then print
         */
        std::stringstream ss;

        /**
         * Lookup characters from predefined table
         */
        for(i = 0; s[i]; ++i)
            ss << A[s[i]];

        std::cout << ss.str() << "\n";
	}
	return 0;
}

Code (Using Lookup Table):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10082 WERTYU ( using c++ string stream )
 */

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

static const char kb[64] = "`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
static char s[256];

int main(){
    std::ios_base::sync_with_stdio(NULL);
    std::cin.tie(0);
    register int i, j;

	while(gets(s)){
        std::stringstream ss;

        for(i = 0; s[i]; ++i){
            if(s[i] == ' ')
                ss << ' ';
            else{
                /**
                 * Each character maps to a character in its left as defined
                 */
                for(j = 0; kb[j]; ++j){
                    if(s[i] == kb[j])
                        ss << kb[j - 1];
                }
            }
        }
        std::cout << ss.str() << "\n";
	}
	return 0;
}

UVA Problem 10079 – Pizza Cutting Solution

UVA Problem 10079 – Pizza Cutting Solution:


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

Solving Technique:

This is a very simple mathematics problem. It can be solved with Gauss‘es arithmetic series formula. Which is the sum 1 to nth number. The formula is,

n * ( n + 1 )/2

The problem just requires us find the number of maximum possible pieces for given the number of cuts. At first the pattern may not be visible. Use pencil and paper draw and verify outputs.

We need add 1 since doing 1 cut in pizza makes two pieces. So the arithmetic series formula is 1 less. Again if we make two cuts using arithmetic progression formula it is 1 less again. It happens for all inputs. So we can add 1 with result of this formula and that is the answer.

This problem can also be solved using simple loop and sum from 1 to n.

A corner case may be that the number may not fit int range.

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
10
-100

Output:

16
56

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10079 Pizza Cutting
 */

#include<stdio.h>

int main(){
    long long n;
    while(scanf("%lld", &n)){
        if(n < 0)
            return 0;

        /**
         * Arithmetic series 1 to n with extra 1
         */
        printf("%lld\n", 1 + n * (n + 1) / 2);
    }
    return 0;
}

UVA Problem 1586 – Molar mass Solution

UVA Problem 1586 – Molar mass Solution:


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

Solving Technique:

Formula to solve this problem is given in the description. Also i have explained in the comments. The only corner case may be two atom numbers. 

Our formula is to multiply element with its atom count to get the total weight. Since there are two digits. The first one is in 10’s position so it must be multiplied by 10. Then add the next digit to it. Since we took the input as string. So this method converts the string digits to integer.

Now just multiply that value with the weight of the corresponding molecule to get the result.

Here i have provided to two codes. The first code follows the formula given in the problem. The second one is slightly modified and strength reduced pre-calculated version based on the first code.

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:

4 
C 
C6H5OH 
NH2CH2COOH 
C12H22O11

Output:

12.010 
94.108 
75.070 
342.296

Code ( Commented):

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

#include<stdio.h>

#define C 12.01
#define N 14.01
#define O 16.00
#define H 1.008

static char s[128];

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

    while(n--){
        scanf("%s", &s);
        float sum = 0;

        for(i = 0; s[i]; ++i){
            /**
             * Check if it is a compound identifier
             */
            unsigned compoundCheck = s[i] == 'C' || s[i] == 'N' || s[i] == 'O' || s[i] == 'H';

            /**
             * Has only two digit next to it
             * Check if it is a compound identifier and next two digits are atom count
             */
            if(compoundCheck && (s[i + 1] >= '0' && s[i + 1] <= '9') && (s[i + 2] >= '0' && s[i + 2] <= '9')){

                /**
                 * calculate the weight with first digit in 10's position so multiply with 10
                 * Add that to the next atom count ( digit )
                 * Minus 48 convert char to its integer equivalent
                 */
                unsigned dualDigitAtom = (s[i + 1] - 48) * 10 + s[i + 2] - 48;

                switch(s[i]){
                case 'C':
                    sum += C * dualDigitAtom;
                    break;
                case 'N':
                    sum += N * dualDigitAtom;
                    break;
                case 'O':
                    sum += O * dualDigitAtom;
                    break;
                case 'H':
                    sum += H * dualDigitAtom;
                    break;
                }
            }

            /**
             * Has only one digit next to it
             * Check if it is a compound identifier and next digit is atom count
             */
            else if(compoundCheck && (s[i + 1] >= '0' && s[i + 1] <= '9')){

                unsigned singleDigitAtom = s[i + 1] - 48;

                switch(s[i]){
                case 'C':
                    sum += C * singleDigitAtom;
                    break;
                case 'N':
                    sum += N * singleDigitAtom;
                    break;
                case 'O':
                    sum += O * singleDigitAtom;
                    break;
                case 'H':
                    sum += H * singleDigitAtom;
                    break;
                }
            }

            /**
             * Single atom compound meaning no digit next to it
             */
            else if(compoundCheck && (s[i+1]!='C' || s[i+1]!='N' || s[i+1]!='O' ||s[i+1]!='H')){
                switch(s[i]){
                case 'C':
                    sum += C;
                    break;
                case 'N':
                    sum += N;
                    break;
                case 'O':
                    sum += O;
                    break;
                case 'H':
                    sum += H;
                    break;
                }
            }
        }
        printf("%.3f\n", sum);
    }
    return 0;
}

Code ( Precomputed Strength Reduction Faster ):

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

#include<stdio.h>

static char s[128];

#define H 1.008
#define C 12.01
#define O 16.0
#define N 14.01

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

    while(n--){
        scanf("%s", &s);
        float sum = 0;

        for(i = 0; s[i]; ++i){
            i1 = s[i + 1];
            i2 = s[i + 2];
            unsigned i1check = i1 >= '0' && i1 <= '9';

            switch(s[i]){
            case 67:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 120.1 * i1 + C * i2 - 6341.28;
                    break;
                }else if(i1check){
                    sum += C * i1 - 576.48;
                    break;
                }else{
                    sum += C;
                    break;
                }
            case 72:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 10.08 * i1 + H * i2 - 532.224;
                    break;
                }else if(i1check){
                    sum += H * i1 - 48.384;
                    break;
                }else{
                    sum += H;
                    break;
                }
            case 78:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 140.1 * i1 + N * i2 - 7397.28;
                    break;
                }else if(i1check){
                    sum += N * i1 - 196.14;
                    break;
                }else{
                    sum += N;
                    break;
                }
            case 79:
                if(i1check && (i2 >= '0' && i2 <= '9')){
                    sum += 160.0 * i1 + O * i2 - 8448.0;
                    break;
                }else if(i1check){
                    sum += O * i1 - 768.0;
                    break;
                }else{
                    sum += O;
                    break;
                }
            }
        }
        printf("%.3f\n", sum);
    }
    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;
}

Lower Bound of Fibonacci Big Omega Time Complexity

Lower Bound of Fibonacci Big Omega Time Complexity:


 Code for Recursive Fibonacci Algorithm:

int fib(int n){
	if (n < 2)
		return n;
	else
		return fib(n - 1) + fib(n - 2);
}

Time Complexity Lower Bound ( Big Omega ):

Detailed explanation for calculating the upper and lower bound can be found here.

T(n) =  T(n-1) + T(n-2) + c
	 =  T(n-2) + T(n-3) + c + T(n-2) + c
	 =  2T(n-2) + T(n-3) + 2c
	 >= 2T(n-2) + 2c
	 =  2T(n-3) + T(n-4) + c) + 2c
	 =  2T(n-3) + 2T(n-4) + 2c + 2c
	 =  2T(n-3) + 2T(n-4) + 4c
	 =  2T(n-4) + 2T(n-5) + 2c + 2T(n-4) + 4c
	 =  4T(n-4) + 2T(n-5) + 6c
	 >= 4T(n-4) + 6c
	 =  4T(n-5) + 4T(n-6) + 10c
	 =  4T(n-6) + 4T(n-7) + 4c + 4T(n-6) + 10c
	 =  8T(n-6) + 4T(n-7) + 14c
	 >= 8T(n-6) + 14c
	 =  .......................
	 =  .......................
	 =  2^k T(n - 2k) + (2^(k+1)-2)c



for, k steps, n - 2k = 0 or, 1 the recursion stops
			  => n = 2k
			  => k = n / 2



	so, from the recurrence relation
	= 2^(n/2) * T(0) + (2^((n/2) +1) -2) * c
	= 2^(n/2) * c + (2^((n/2) +1) -2) * c
	= Ω(2^(n/2))

So, the lower bound of for this recursive Fibonacci algorithm implementation is Big Omega of 2n / 2.

Lower Bound:  Ω ( 2n / 2  )

7 Segment Decoder Implementation, Truth Table, Logisim Diagram

7 Segment Decoder Implementation, Truth Table, Logisim Diagram:

7 Segment Decoder:

For reference check this Wikipedia link.


Pictures:

(Wikipedia CC BY-SA 2.5)

7 Segement Display
7 Segment Display with pins shown
Individual segments 7 Segment Display marked
Individual segments 7 Segment Display marked

Explanation:

Before we start implementing we first need to check if it is common anode or common cathode. If it is common anode then 3rd pin in both top and bottom are VCC. But if it is we should connect 3rd pin in both top and bottom to ground.

Pins:

show top pins then bottom pins ( Dot side is down ).

        Pin1   Pin2   Pin3   Pin4   Pin5
Top:     g      f    vcc/GND   a     b
Bottom:  e      d    vcc/GND   c     dp

Truth Table:

DLD 7-segment Display Truth Table
DLD 7-segment Display Truth Table

From here we can get minimized expressions for a, b, c, d, e, f, g using K-MAP. Here we only need value 0 though 9 rest are don’t care terms. Using those don’t care terms we will try to maximum ones first.

K-Map (Karnaugh map) for ‘a’:

We can follow similar procedure for the rest. K map for ‘a’ can be created by taking the ‘a’ column from the table above and setting the value 0 / 1 to corresponding location in the table. For example to display 0 ( 0000 )  ‘a’ is always 1. Similarly to display 1 ‘a’ is always 0. For value ( 10 – 16 ) we don’t care about them so they are used as don’t care term in k map.

k-map-a-output-7-segment
k-map a output 7 segment

Using Logisim to generate circuit diagram:

1
Go to Window -> Computational Analysis
  • Go to Window -> Computational Analysis

 

2
Now input D, C, B, A as in which case D is MSB and A is LSB. Otherwise A, B, C, D can also be inputs and MSB, LSB will be opposite.
  • Now input D, C, B, A as in which case D is MSB and A is LSB. Otherwise A, B, C, D can also be inputs and MSB, LSB will be opposite.

 

3
Now input the table given above in the table tab. We can just input values by single or double clicks.
  • Now input the table given above in the table tab. We can just input values by single or double clicks.

 

4
finished table

 

5
expressions for each of the output variables

 

6
k map for each of the variables / outputs can be seen here

 

7
name the circuit and tick use two input gates, if you use two input gates otherwise its not needed.

 

8
Finished circuit diagram
  • Now just drag the 7 segment display from input / output folder and connect the ports according to given table above.

 

Logisim Diagram For Decoder Table:

7 segment display diagram
7 segment display diagram

 

Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative )

Fibonacci Memoization Top Down ( Recursive ) and Bottom Up ( Iterative ) Dynamic Programming:


Top Down Fibonacci Memoization Code:

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

#include<stdio.h>

#define N 64
long long F[N];

/**
 * Top Down Recursive Fibonacci Memoization
 */
long long topDownMemFib(long long n){
    /**
     * If its not 1 then it means there is already a calculated value
     * So no more need to compute, just return that value
     */
    if(F[n] != -1)
        return F[n];

    F[n] = topDownMemFib(n - 1) + topDownMemFib(n - 2);
    return F[n];
}

int main(){
    register unsigned i;

    unsigned n;
    printf("Enter a number:\n");
    scanf("%u", &n);

    /**
     * Terminating condition values
     */
    F[0] = 0;
    F[1] = 1;

    /**
     * First set the whole array to -1, means there are no calculated value
     */
    for(i = 2; i <= n; ++i)
        F[i] = -1;

    printf("%lld\n", topDownMemFib(n));

    return 0;
}

 

Bottom Up Iterative Fibonacci Implementation:

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

#include<stdio.h>

/**
 * Increase this value for numbers more than 64
 */
#define N 64
long long F[N];

/**
 * Top Down Fibonacci Memoization
 */
long long bottomUpMemFib(long long n){
    /**
     * Terminating Condition
     */
    F[0] = 0;
    F[1] = 1;

    register unsigned i;
    for(i = 2; i <= n; ++i)
        F[i] = F[i - 1] + F[i - 2];

    return F[n];
}

int main(){
    register unsigned i;

    unsigned n;
    printf("Enter a number:\n");
    scanf("%u", &n);

    printf("%lld\n", bottomUpMemFib(n));

    return 0;
}