UVA Problem 10106 – Product Solution (Lattice Multiplication)

UVA Problem 10106 – Product Solution:


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

Solving Technique:

This problem is quite simple. Given two very large integers multiply them and print them. By large I mean almost 251 characters long for this problem. So string or character array must be used.

This problem can solved in many ways Big Integer, FFT, Grade School etc. But I have implemented lattice multiplication / Chinese multiplication to solve this problem.


Code Explanation:

The code below requires quite a bit of polish to understand easily ( A lot other post require the same. Maybe I will update this post sometimes in future or not. ).

This code is not quite space efficient. I have used several arrays to make it easy to understand but all of the tasks below can be done using the large array. Also the running time can further be improved to O(m*n) instead of O(n^2) . Where, m and n are length of two arrays and they may not be equal in size.


I have provided some graphical representations below to make it easier to understand.


lattice multiplication example
lattice multiplication example

This is an example of how the multiplication works in this code. As mentioned above the process can be sped up using rectangular matrix instead of square if the length is not equal.


lattice multiplication table fill
lattice multiplication table fill

This is a representation of how the table / square matrix is filled for further processing.

Multiplication starts with the last character of string 1 and proceeds to first character. For string 2 multiplication starts from the first character till last character. This way each character from string 1 and string 2 is first converted to a digit, then they are multiplied. If the result is two digits it is divided by 10.

The remainder is written as the lower left portion ( indicated by lower in the structure ) and the quotient is written as the upper left portion ( indicated by upper in the structure ).


lattice multiplication structure traversal
lattice multiplication structure traversal

This is graphical representation of how the structure is traversed. If you have trouble understanding how the recursive function traversing the structure, then take a look at UVA problem 264 – Count the Cantor Solution. The traversal is somewhat similar to that and I have provided explanation int that post.

Rest is explained in the code 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:

12
12
2
222222222222222222222222

 


Output:

144
444444444444444444444444

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Lattice Multiplication.
 * Technique: High precision large number multiplication.
 *            Structure array representing upper left and
 *            and lower right corner in single cell.
 */

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


#define M 260

int N;


// Assuming both strings are of same length.
struct multiplicationTable{
    int upper;
    int lower;
};
struct multiplicationTable node[M][M];



static char string1[M];
static char string2[M];



// stores the diagonal sums;
int sum;

// decides whether to get the upper or lower
// value based on even or odd.
int m;


// Add diagonals.
int recursiveAdder( int i, int j ){

    // Termination condition.
    if( j < 0 || i >= N )
        return sum;

    int val;


    // Whether to get the upper left corner or
    // the lower right corner.
    if( m % 2 ){
        val = node[i][j].upper;
        j = j - 1;
    }
    else{
        val = node[i][j].lower;
        i = i + 1;
    }
    ++m;


    // store the sum of the whole diagonal.
    sum = sum + val;


    // recursively visit all row ans column
    // diagonally ( at least on pen and paper format ).
    // actually moves more like the snake in the snakes game.
    recursiveAdder(i,j);

    return sum;
}


// Debug.
// Print the matrix showing the multiplications.
// Please note left and right directions may be different.
void printMultiplicationMatrix(){

    printf("\n\n");
    for( int i = 0; i < N; ++i ){
        for( int j = N - 1; j >= 0; --j )
            printf("%d,%d, ", node[i][j].upper, node[i][j].lower );
        printf("\n");
    }

}







int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    while( gets(string1) ){
        gets(string2);

        int len1 = strlen(string1);
        int len2 = strlen(string2);

        // Fix length if both string are not equal size.
        // Adding leading zeros to smaller string.
        if( len1 > len2 ){
            N = len1;

            int shiftWidth = len1 - len2;

            for( int i = len1 - 1; i >= 0; --i )
                string2[i + shiftWidth] = string2[i];

            for(int j = 0; j < shiftWidth; ++j)
                string2[j] = '0';

        }
        else if(len2 > len1){
            N = len2;

            int shiftWidth = len2 - len1;

            for( int i = len2 - 1; i >= 0; --i )
                string1[i + shiftWidth] = string1[i];

            for(int j = 0; j < shiftWidth; ++j)
                string1[j] = '0';

        }
        else N = len1;


        //printf("%s \n%s \n", string1, string2);


        int k = N - 1;


        // Multiply the numbers digit by digit and set in the lattice.
        for( int i = 0; string2[i]; ++i ){
            for( int j = 0; string2[j]; ++j ){

                int num1 = string1[k] - '0';
                int num2 = string2[j] - '0';

                int multiply = num1 * num2;

                node[j][k].upper = multiply / 10;
                node[j][k].lower = multiply % 10;

            }
            --k;
        }

        //printMultiplicationMatrix();


        // Lattice is divided into two parts upper left half and
        // lower right half.


        // result of upper half
        int upperHalfResult[N];

        // Add upper half
        int i = N - 1;
        for(; i >= 0; --i){
            sum = 0;
            m = 1;
            upperHalfResult[i] = recursiveAdder(0, i);
        }


        // result of upper half
        int lowerHalfResult[N];

        // Add upper half
        i = 0;
        for(; i < N; ++i){
            sum = 0;
            m = 0;
            lowerHalfResult[i] = recursiveAdder(i, N - 1);
        }



        // Combine upper and lower left half to a single array to fix addition
        // problems.
        int combinedRawResult[N + N];
        i = 0;
        for(; i < N; ++i )
            combinedRawResult[i] = upperHalfResult[i];
        for(k = 0; i < N + N; ++i, ++k )
            combinedRawResult[i] = lowerHalfResult[k];



        // If a cell has more than 9 then it should be added to the next cell.
        for( int i = N + N - 1; i >= 0; --i ){

            if( combinedRawResult[i] > 9 ){
                combinedRawResult[i - 1] = combinedRawResult[i - 1] + combinedRawResult[i] / 10;
                combinedRawResult[i] = combinedRawResult[i] % 10;
            }

        }


        // Discard leading zeros.
        for(i = 0; i < N + N; ++i)
            if(combinedRawResult[i]) break;


        // print if the result can be printed or its zero.
        bool zero = true;
        for(; i < N + N; ++i){
            printf("%d", combinedRawResult[i]);
            zero = false;
        }

        // If the result is zero.
        if( zero )
            printf("0");

        printf("\n");



    }

    return 0;
}
Advertisements

Grade School High Precision Floating Point Number Adder Implementation in C++

Warning: This program has not been thoroughly tested. So it may produce incorrect results.

How the Code Works:

Note this problem calculates the integer and fractional portion separately in array as opposed to techniques learned in numerical analysis. To test if outputs are correct check against other high precision calculator such as this calculator.

Similar to this problem or same techniques used in uva problem 424 integer inquiry solution, uva problem 10035 primary arithmetic solution, uva problem 713 adding reversed numbers solution. The technique from this problem can also be applied to the mentioned problems.


Solution Steps:
Example Input:
25.401
534.2914
710.84
9.7808
980.7223

Note here are two separate arrays with one for decimal part and other for fraction. The dot is not stored anywhere, it is just shown to make it easy to understand. First the numbers are aligned with padding functions to create this,

025 . 4010
534 . 2914
710 . 8400
009 . 7808
980 . 7223

Although not used in this problem below, this pic that shows how I calculated sum column-row (column major) wise which is not cache friendly.

uva 424 integer inquiry order of operation
uva 424 integer inquiry order of operation

As shown in the pic above the technique is almost same but this time row and columns are interchanged and kept in a separate array which looks like this,

New Decimal Array:
05709 
23108 
54090 
New Fraction Array:
42877
09482
11002
04083

Next the operation is carried out as shown below,

row wise addition of high precision floating point numbers
row wise addition of high precision floating point numbers

Sample Test Input:

3.6692156156
65652.6459156456415616561
33.54615616
1.1
9854949494968498.49684984444444444444444443213615312613216512331918565

Output:

Output: 9854949495034189.45813726568600610054444443213615312613216512331918565

Code:

/********************************************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Naive High Precision Floating Point Number Adder
 *
 * Warning:   This Code is mostly useless and hard to read. It is not represented in
 *            usual sign, exponent sign, exponent magnitude, mantissa magnitude format.
 *            The Program should produce correct output till given FRACTION_LIMIT after
 *            decimal point for unsigned numbers (Negative numbers not supported).
 *
 *            Also it may not necessary produce correct result as it is not throughly
 *            tested. Use it with caution.
 *
 *            Please follow input format. I have not handled any exception for incorrect
 *            input formats.
 *
 *******************************************************************************************/



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



// Increase the TEST_NUMBERS to calculate more float numbers.
#define TEST_NUMBERS  5

#define DECIMAL_SIZE  100
#define FRACTION_SIZE 100




// Function Prototypes
void sumDecimal(char **, int, int);
void sumFractions(char **, int);


// Array for holding decimal and fractional portion
static char decimal[TEST_NUMBERS][DECIMAL_SIZE];
static char fraction[TEST_NUMBERS][FRACTION_SIZE];


// Pointers reversed decimal and fractional result array.
char *resDec, *resFrac;
int resDecLen, resFracLen;



// Align decimal portion of the numbers and zeros.
void fixPaddingDecimal(int carry){

    // Holds calculated length of all strings.
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest decimal.
    int maxlength = memo[0] = strlen(decimal[0]);


    // Get the max length for padding or aligning.
    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(decimal[i]);
        if( len > maxlength )
            maxlength = len;
    }



    // Shift elements by appropriate positions or, create padding.
    // Look at my other linked pages from the post to understand this part.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            int padding = maxlength - len;

            for(int j = len - 1; j >= 0; --j)
                decimal[i][padding + j] = decimal[i][j];

            for(int j = 0; j < padding; ++j)
                decimal[i][j] = '0';
        }
    }



    // Create a new 2D array that will hold values in the new changed order.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Copy decimal portion to the mew changed order array.
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = decimal[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */


    // After fixing alignment add the decimal portion.
    sumDecimal( cacheFrindlyFloatOrganization, maxlength, carry);

}



// Add all the decimal numbers.
void sumDecimal(char **cacheFrindlyFloatOrganization, int maxlength, int carry){

    // Holds the output decimal part in reversed order.
    char *resultDecimal = new char[maxlength + 1];

    int z = 0;


    // Again look at the pages linked from this post.
    // I have explained this in uva 424, 10035, 713 etc.
    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultDecimal[z++] = sum % 10 + '0';
        carry = sum / 10;
    }

    // Stored in reversed order
    if(carry)
        resultDecimal[z++] = carry + '0';
    resultDecimal[z] = '\0';


    // Store the address and length of resultDecimal
    resDec = resultDecimal;
    resDecLen = z;


}



// As explained above this ALMOST does the same thing as function decimal code.
void fixPaddingFraction(){

    // Holds calculated length of all strings
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest fraction
    int maxlength = memo[0] = strlen(fraction[0]);

    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(fraction[i]);
        if( len > maxlength )
            maxlength = len;
    }


    // Add zeros to empty positions.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            for(int j = len ; j < maxlength; ++j)
                fraction[i][j] = '0';
            fraction[i][maxlength] = '\0';
        }
    }


    // Explained above.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Interchanging row and columns
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = fraction[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */

    // Sum the fractional array part.
    sumFractions(cacheFrindlyFloatOrganization, maxlength);
}




// Does ALMOST the same thing for decimal function code.
void sumFractions(char **cacheFrindlyFloatOrganization, int maxlength){

    char *resultFraction = new char[maxlength + 1];

    int z = 0, carry = 0;

    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultFraction[z++] = sum % 10 + '0';
        carry = sum / 10;
    }


    // Stored in reversed order
    resultFraction[z] = '\0';


    // Hold the address and length resultFraction array.
    resFrac = resultFraction;
    resFracLen = z;


    // Call the padding function for by sending the carry from fraction part.
    fixPaddingDecimal(carry);
}



// The output decimal and fraction array are in reversed order.
// They need to be reversed before outputting.
void reverseString(char *tmpString, int tmpStringLen){

    for(int i = 0, j = tmpStringLen - 1; i < j; ++i, --j ){
        int temp = tmpString[i];
        tmpString[i] = tmpString[j];
        tmpString[j] = temp;
    }
}



int main(){


    // Comment freopen lines below to input and output from console.
    // In order to use freopen create a file named input_file.txt
    // in same directory as your cpp file. The output of the program
    // will be in output_file.txt file.

    /*
    freopen("input_file.txt", "r", stdin);
    freopen("output_file.txt", "w", stdout);
    */



    for(int i = 0; i < TEST_NUMBERS; ++i){
        //printf("Enter float:\n");
        scanf("%[0-9].%[0-9]", &decimal[i], &fraction[i]);
        getchar();
    }


    // This is where it all starts.
    fixPaddingFraction();



    reverseString(resDec, resDecLen);
    reverseString(resFrac, resFracLen);


    // Debug
    printf("Output: %s.%s\n", resDec, resFrac );



    return 0;
}

UVA Problem 264 – Count on Cantor Solution

UVA Problem 264 – Count on Cantor Solution:


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

Solving Technique:

Warning this is a terrible dynamic programming and memoization solution. If you want a fast and efficient solution then, this isn’t what you are looking for.

Problem Statement:

Given an input integer that represent a rational number sequence term shown by cantor, output the rational number for that term.


Solution Types:

I have given two solution, one of which uses a 2D array to store the rational number sequence as shown by cantor and using a traversal pattern memoize the series in another array. Although the first one can be improved to only traverse 1/4 th of the array but that’s still a lot.

The next solution discards the 2D array and using the traversal pattern with some optimization memoizes the series.

The time difference as of UVA submission running time is,

0.245 ms (1st technique)
0.072 ms (2nd technique)

Removing the recursion by replacing with iterative version ( A bit harder to do ) will make it even faster. I think this one can be further improved but have no idea how.

Figuring out the algorithm:


Note everything here is assuming indexing starts from 1 instead of 0. But in my code I start with index 0 instead of 1.

 

Sequence Traversal within Matrix:
cantor sequence matrix
cantor sequence matrix

Unraveling the Sequence:
cantor sequence chain
cantor sequence chain

Traversal Pattern and Sub structure/pattern:
cantor structure and substructure pattern
cantor structure and substructure pattern

Substructure and Movement within Matrix:
cantor movement within matrix
cantor movement within matrix

Points To Notice:

1. Moves right when row number is 0 and column number is even.
2. Moves down-left when row number is 0 and column number is odd.
3. Moves down when column number is 0 and column number is odd.
4. Moves up-right when column number is 0 and column number is even.
5. Diagonal traversal gets bigger by 1 unit for each down or right movements.


Traversing the Matrix:

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c - 1 times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r - 1 times)} & \forall : col = 0; row \in Even \\    \end{cases}

OR, In my code,

Traverse(r,c,index,diagonal) =     \begin{cases}      \rightarrow \text{(1 times)} & \forall : row = 0; col \in Even \\     \swarrow \text{(c + diagonal times)} & \forall : row = 0; col \in Odd \\     \downarrow \ \ \text{(1 times)} & \forall : col = 0; row \in Odd \\     \nearrow \text{(r + diagonal times)} & \forall : col = 0; row \in Even \\    \end{cases}

Note: Increment the index and diagonal also.


Filling the Matrix (1st code only):

CantorTable_{i,j} =     \begin{cases}      numerator = row, & \forall : Column, rows \\     denominator = column, & \forall : Column, rows \\    \end{cases}


Base case:

Note when row or the column is equal to 0 then there is a turn. If row or column becomes less than 0 then it should stop.

Also the amount values to memoize is N which is the maximum cantor sequence value for this problem. So if N values are memoized then the process should stop.

if (r < 0 || c < 0 || index > M)
    return;

Storing the fractions in 2D Struct Array:

Instead of storing the values in string it is better to store the fraction in a struct. There are 3 things in the fraction the numerator, a division sign , the denominator. There is no need to store the division sign since all elements within matrix are fraction.

struct CantorSequence{
    int numerator;
    int denominator;
};

About Space:

The first solution requires a total of O( M + \frac{N(N+1)}{2} ) space including storing the cantor sequence in another array and pre calculating the 2D cantor table and traversing.

The second solution requires a total of O( M ) space including storing the cantor sequence in another array.

Here, M is 10000000 and N is 4500. N can be adjusted but 4500 is a safe value.


Please point out if the post contains mistakes.

 

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
14
7
10000000 

 


Output:

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4
TERM 10000000 IS 2844/1629

Code Recursive DP 2D struct Traversal and Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            2D struct array,
 *            2D half diagonal fill,
 *            Recursive Dynamic Programming
 ***********************************************************************/


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

// N * N should be almost twice greater than or equal to M.
// Or, N should be such that N*(N+1)/2 is greater than M.
#define N 4500


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
} CT[N][N];


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];


/**
 * Fill in the cantor table.
 */
void CantorFill(){

    for(int row = 0; row < N; ++row){

        int cutoff = N - row;

        for(int col = 0; col < cutoff; ++col){
            CT[row][col].numerator   = row + 1;
            CT[row][col].denominator = col + 1;
        }

    }

}


void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    OrderedCantor[index].numerator = CT[r][c].numerator;
    OrderedCantor[index].denominator = CT[r][c].denominator;



    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {


    // Initialize Cantor table
    CantorFill();


    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}


Code Recursive DP Sequence Memoize:

/***********************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 264 - Count on Cantor
 *
 * Technique: Zig Zag / Spiral Diagonal traversal,
 *            Recursive Dynamic Programming
 ***********************************************************************/


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


#define M 10000000


/**
 * Table to construct the sequence
 */
struct CantorTable{
    int numerator;
    int denominator;
};


// Holds cantor values from 1 to M by index
CantorTable OrderedCantor[M];




void RecursiveCantor(int r, int c, int index, int diagonal){

    // base case
    if( r < 0 || c < 0 || index > M ){
        return;
    }


    // change from table traversed DP
    OrderedCantor[index].numerator = r + 1;
    OrderedCantor[index].denominator = c + 1;


    // Amount of times to travel in diagonal
    ++diagonal;



    if(r == 0){

        // when odd move down left
        if(c % 2){
            for(int i = 0; i < c + diagonal; ++i){
                ++index;
                r = r + 1;
                c = c - 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

        // when even Move right
        else{
            ++index;
            c = c + 1;
            RecursiveCantor( r, c, index, diagonal );
        }
    }

    else if(c == 0){

        // when odd move down
        if(r % 2){
            ++index;
            r = r + 1;
            RecursiveCantor( r, c, index, diagonal );
        }

        // when even Move up right
        else{
            for(int i = 0; i < r + diagonal; ++i){
                ++index;
                r = r - 1;
                c = c + 1;
                RecursiveCantor( r, c, index, diagonal );
            }
        }

    }

}



int main() {

    // Pass in row, column, index, diagonal traversal size
    RecursiveCantor(0, 0, 1, 0);


    int n;


    while( scanf("%d", &n) == 1 ){
        printf("TERM %d IS %d/%d\n", n, OrderedCantor[n].numerator, OrderedCantor[n].denominator );
    }

    return 0;
}

UVA Problem 10035 – Primary Arithmetic Solution

UVA Problem 10035 – Primary Arithmetic Solution:


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

Solving Technique:

For this problem two integers less than 10 digits are given. The task is to find how many carry operations occur when adding.

This problem may be solved using strings since input integer is less than 10 digits. It can be solved with out using array. My implementation is using character array to add and count carry operations.

Similar to this UVA 713 – Adding Reversed Numbers Solution and UVA PROBLEM 1225 – DIGIT COUNTING

 

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:

123 456
555 555
123 594
0 0

 


Output:

No carry operation.
3 carry operations.
1 carry operation.

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10035 - Primary Arithmetic
 * Technique: Adding leading 0's integer string,
 *            Making two strings of same length,
 *            Adding String Integers.
 */

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

#define N 128

static char s[N];
static char t[N];

static char output[N];


int main(){

    while( scanf("%s", s) && scanf("%s", t) ){

        // Although a major flaw input beginning with 0 and
        // two strings matching. But for this problem it doesn't matter.
        if( strcmp(s,t) == 0 && s[0] == '0' )
            break;


        int lens = strlen(s);
        int lent = strlen(t);


        // Add leading 0's to smaller string (May not be necessary).
        // Shift each characters in string right by padding length.
        if( lens > lent ){

            int padding = lens - lent;

            for(int i = lent - 1; i >= 0; --i)
                t[i + padding] = t[i];

            for(int i = 0; i < padding; ++i)
                t[i] = '0';
        }

        else if( lens < lent ){

            int padding = lent - lens;

            for(int i = lens - 1; i >= 0; --i)
                s[i + padding] = s[i];

            for(int i = 0; i < padding; ++i)
                s[i] = '0';
        }



        int maxlen;
        if(lens > lent)
            maxlen = lens;
        else maxlen = lent;


        int carry = 0;
        int c = 0;
        int sum = 0;


        // Add two Strings, if a carry operation occurs
        // then add that to the count.
        for(int i = maxlen - 1; i >= 0; --i){

            sum += s[i] - '0' + t[i] - '0';

            sum = sum + carry;

            carry = sum / 10;

            if(carry)
                ++c;

            sum = 0;

        }


        if(!c)
            printf("No carry operation.\n");
        else if( c > 1 )
            printf("%d carry operations.\n", c);
        else
            printf("%d carry operation.\n", c);

    }

    return 0;
}

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 10699 – Count the factors Solution

UVA Problem 10699 – Count the factors Solution:


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

Solving Technique:

The problem requirement is to find the prime factors of a given number. If the input number is divisible by a prime number then that prime number is a prime factor of input.

Similarly do this with all prime numbers less than the input if it is divisible then increase prime factor count. It seems like there is a way to cut down running time in this very code, but I am not able find it.

 

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:

289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0

 


Output:

289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10699 - count the factors
 * Technique: Efficient Prime Generation, Sieve of Eratosthenes.
 */

#include<stdio.h>
#include<math.h>


/**
 * Since value can be up to 1000000
 */

#define N 1000000


int primesTable[N];
int onlyPrimesTable[N];


int k = 0;


void SieveOfEratosthenes(){

    int i = 2;

    /**
     * Set Every index in the table to be prime.
     */
    for(; i <= N; ++i)
        primesTable[i] = 1;

    /**
     * Base case 0 and 1 are not primes.
     */
    primesTable[0] = primesTable[1] = 0;

    int len = sqrt(N);

    /**
     * Set all multiples of a number to 0 since primes can't divisible by other than itself.
     */
    for(i = 2; i <= len; ++i){
        if(primesTable[i]){
            for( int k = i << 1; k <= N; k += i )
                primesTable[k] = 0;
        }
    }


    /**
     * This is not really a part of Sieve of Eratosthenes.
     * It checks if a number is prime then it moves primes
     * to another array which only contain primes and this
     * reduces the number of lookups.
     */
    for(i = 0; i <= N; ++i){
        if(primesTable[i])
            onlyPrimesTable[k++] = i;
    }
}

int main() {

    /**
     * Pre generate primes and isolate them to another array.
     */
    SieveOfEratosthenes();


    int n;

    /**
     * Input the number and check if its 0.
     */
    while(scanf("%d", &n) && n){

        int c = 0;

        /**
         * If the number is divisible by a prime then,
         * increase prime factor count.
         */

        for(int i = 0; i < k; ++i){
            if( n % onlyPrimesTable[i] == 0)
                ++c;
        }

        printf("%d : %d\n", n, c);

    }


    return 0;
}

UVA Problem 12592 – Slogan Learning of Princess Solution KMP Algorithm Implementation and Explanation

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

Solving Technique:

Dissecting the problem statement:

The problem is straight forward. Given an input n, there will be 2n lines of input. Since each line also has accompanying next line. They are divided in first and second line. Here only first line is required for calculation. The second line is the output of the program.

Then we will be given say m lines. For each lines we are to match the first lines from previous 2n lines and output the second line.

Solution:

There are easier ways to solve this, but this mainly a KMP ( Knuth Morris Pratt ) algorithm tutorial.

Here the input is “jalo re jalo” which is one the inputs from the problem. The state diagrams are first drawn without following the algorithm. After that DFA table from hand tracing and code output is matched.


 

State Machine diagram without transition to initial state:

Explanation:

Why most states transition back to state 1 on ‘j’ input? Reaching state 1 means ‘j’ is already matched so going back to 0 will produce wrong output. Because that’d mean two j matched or “jj”. Since ‘a’ is after ‘j’ the next task is to match ‘a’ so we go back to state 1 and try to match further inputs.

Notice on state 8 on input of ‘j’ it goes to 9 instead of 1. Because that ‘j’ is also a part of the seqence and the seqence hasn’t broken yet. Finally on state 12 or on the length of the pattern string the input gets is accepted.

kmp dfa without initial transitions
kmp dfa without initial transitions

 

State Machine diagram with transition to initial state:

kmp dfa with initial transitions.png
kmp dfa with initial transitions.png

Calculated DFA table:

DFA table is generated with pattern being one of the input from the problem.
“jalo re jalo”

After generating the DFA table from tracing the algorithm and the DFA table state after running the algorithms both match. Also the states and transitions of the DFA table exactly match the state machine above.

Empty cells means it contains 0 which transitions to initial or start state. Transitions to start state not shown to keep it simple.
kmp calculated dfa table
kmp calculated dfa table

DFA table state after running of KMP algorithm:

Input is the same string as above.

kmp dfa table print
kmp dfa table print

Step by step table fill and explanation: (CreateDFA function)

Note empty cells in the matrix contains zero. They are not shown to keep it simple here but they are there and they transition to start or beginning state which is 0.

Call to createDFA Function:

This is the initial state of the DFA matrix.

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}  \hline  & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline  & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline  {\bf ' '} & & & & & & & & & & & & \\ \hline  {\bf a} & & & & & & & & & & & & \\ \hline  {\bf e} & & & & & & & & & & & & \\ \hline  {\bf j} & & & & & & & & & & & & \\ \hline  {\bf l} & & & & & & & & & & & & \\ \hline  {\bf o} & & & & & & & & & & & & \\ \hline  {\bf r} & & & & & & & & & & & & \\ \hline  \end{tabular}


Setting up the next state:

This is execution of line 53 in code below.

DFA[pattern[0]][0] = 1;

Here the pattern is,


pattern = "jalo re jalo";

So, pattern[0] is character ‘j’.


DFA['j'][0] = 1;

This essentially means in the j-th row and 0-th column set 1.


Understanding the transitions:

To understand the how the transitions work column wise lay the pattern. So if the length of pattern is m then there are m columns in the matrix. In row wise layout the set of character in the pattern. So even if there are multiple occurrence of the same character it is only represented as a row once.

By careful inspection of the DFA matrix it can be observed that state change occur when the character in that row matches the column representation of that character.

The row index is represented by the ASCII value of the set of characters in pattern. The column are represented from 0 to m where m is length of the pattern.

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}  \hline  & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline  & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline  {\bf ' '} & & & & & & & & & & & & \\ \hline  {\bf a} & & & & & & & & & & & & \\ \hline  {\bf e} & & & & & & & & & & & & \\ \hline  {\bf j} & 1 & & & & & & & & & & & \\ \hline  {\bf l} & & & & & & & & & & & & \\ \hline  {\bf o} & & & & & & & & & & & & \\ \hline  {\bf r} & & & & & & & & & & & & \\ \hline  \end{tabular}


Copying values from x-th column:

Execution of line 60 and 61 in code below.


for(k = 0; k < r; ++k)
DFA[k][j] = DFA[k][x];

This code basically copies values in x-th column to j-th column. Initially x = 0 and j = 1, So values from 0-th column( 0-th index ) are copied into 1-st column ( 1-st index ).

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}  \hline  & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline  & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline  {\bf ' '} & & & & & & & & & & & & \\ \hline  {\bf a} & & & & & & & & & & & & \\ \hline  {\bf e} & & & & & & & & & & & & \\ \hline  {\bf j} & 1 & 1 & & & & & & & & & & \\ \hline  {\bf l} & & & & & & & & & & & & \\ \hline  {\bf o} & & & & & & & & & & & & \\ \hline  {\bf r} & & & & & & & & & & & & \\ \hline  \end{tabular}


Updating the next state and Column to to copy from:

Execution of line 66.

DFA[pattern[j]][j] = j + 1;

when, j = 1


DFA[pattern[1]][1] = 1 + 1;

since pattern[1] = ‘a’


DFA['a'][1] = 2;

This replaces the matching row and column matching character cell with value of next state which is the next column number.

Execution of line 71.


x = DFA[pattern[j]][x];

Update x the column number where to copy values from. This means if in the pattern recognition we go back in a previous state then we don’t need to recalculate. Since the transitions in that state are already calculated use those same transitions.

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}  \hline  & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline  & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline  {\bf ' '} & & & & & & & & & & & & \\ \hline  {\bf a} & & 2 & & & & & & & & & & \\ \hline  {\bf e} & & & & & & & & & & & & \\ \hline  {\bf j} & 1 & 1 & & & & & & & & & & \\ \hline  {\bf l} & & & & & & & & & & & & \\ \hline  {\bf o} & & & & & & & & & & & & \\ \hline  {\bf r} & & & & & & & & & & & & \\ \hline  \end{tabular}


Skipping Some Steps:

After skipping some steps now value of j counter is 8.
So pattern[8] = j. Note here I’ve used two single quotes to represent the space character.

Here again values from 0-Th column are copied into the 8-Th column.
DFA[‘j’][8] is set to j + 1 = 9.
There was already a value there and it’ll be replaced.

Now the interesting part when updating x ( the column to copy values from )


x = DFA[pattern[j]][x]
x = DFA['j'][0]
x = 1

It already stated there which state to go for on which input.
So x becomes 1. Now in the next iteration values from 1-st column will be copied.

\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}  \hline  & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline  & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline  {\bf ' '} & & & & & 5 & & & 8 & & & & \\ \hline  {\bf a} & & 2 & & & & & & & & & & \\ \hline  {\bf e} & & & & & & & 7 & & & & & \\ \hline  {\bf j} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 9 & & & \\ \hline  {\bf l} & & & 3 & & & & & & & & & \\ \hline  {\bf o} & & & & 4 & & & & & & & & \\ \hline  {\bf r} & & & & & & 6 & & & & & & \\ \hline  \end{tabular}


Final State of the DFA table or Matrix:

Similarly follwoing the procedure of copying x-th column, then updating matching character cell to next to next state or index and finally updating x to be the value at current character row and x th column we get this DFA table.
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|l|l|}  \hline  & j & a & l & o & ' ' & r & e & ' ' & j & a & l & o \\ \hline  & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline  {\bf ' '} & & & & & 5 & & & 8 & & & & \\ \hline  {\bf a} & & 2 & & & & & & & & 10 & & \\ \hline  {\bf e} & & & & & & & 7 & & & & & \\ \hline  {\bf j} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 9 & 1 & 1 & 1 \\ \hline  {\bf l} & & & 3 & & & & & & & & 11 & \\ \hline  {\bf o} & & & & 4 & & & & & & & & 12 \\ \hline  {\bf r} & & & & & & 6 & & & & & & \\ \hline  \end{tabular}


DFAStringMatching Function:

Execution of line 34, 35. Here i seem to have calculated length of pattern twice. This not a problem but doing extra work.

After the DFA matrix is generated. Next apply the given query string to the matrix and see if by transition it is able reach the last state which is length of the DFA string.


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++.


Input:

3
My name is
Asif
what is kmp
string matching algorithm
jalo re jalo
agun jalo
2
jalo re jalo
what is kmp

 


Output:

agun jalo
string matching algorithm

Code:

/*
 * Author:   Quickgrid ( Asif Ahmed )
 * Site:     https://quickgrid.wordpress.com
 * Problem:  UVA 12592 Slogan Learning Princess
 * Solution: Knuth Morris Pratt ( KMP ) algorithm implementation
 */

#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

static string slogan[100];
static string query;

#define r 160

/**
 * Space may be further minimized at the cost of running time
 */
static unsigned DFA[r][100];

unsigned DFAStringMatching(string text, string pattern){
    unsigned m = pattern.length();
    unsigned n = query.length();

    /**
     * i is incrementing by 1, meaning using text[i] whole input string can be traversed.
     * text[i] is a character. DFA[text[i]][j] means text[i] character column and j th row.
     * This position or cell contains the column for next transition.
     */
    unsigned i, j;
    for(i = 0, j = 0; i < n && j < m; ++i)
        j = DFA[text[i]][j];

    /**
     * If j equals m then all transition completed successfully
     * meaning the string are a match.
     */
    if(j == m)
        return 1;
    else
        return 0;
}

void CreateDFA(string pattern){
    unsigned m = pattern.length();

    /**
     * Set the first state to 1
     */
    DFA[pattern[0]][0] = 1;

    unsigned x, j, k;
    for(x = 0, j = 1; j < m; ++j){
        /**
         * Copy all values from x column to j column.
         */
        for(k = 0; k < r; ++k)
            DFA[k][j] = DFA[k][x];

        /**
         * Update position in table to the next transition.
         */
        DFA[pattern[j]][j] = j + 1;

        /**
         * Update the column from which to copy values.
         */
        x = DFA[pattern[j]][x];
    }


    /**
     * Uncomment code below to see transitions to states in DFA table
     * For printing transitions in DFA
     * Delete this before submitting to UVA
     * Empty or Zero in DFA means transition to initial state
     */

    /*
    int val = 0;
    for(j = 0; j < m; ++j){
        for(k = 0; k < r; ++k){
            val = DFA[k][j];
            if(val)
                printf("Transition from state (%d) to state (%d) for input: %c\n", j, DFA[k][j], k);
        }
        printf("\n");
    }
    */

}

int main()
{
    static unsigned n, i, q;

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

    /**
     * Since each input has two lines
     */
    static unsigned limit = 2 * n;

    for(i = 0; i < limit; i += 2){
        getline(cin, slogan[i]);
        getline(cin, slogan[i+1]);
    }

    scanf("%u", &q);
    getchar();

    while(q--){
        getline(cin, query);

        /**
         * Create the DFA table from input
         */
        CreateDFA(query);

        for(i = 0; i < limit; i += 2){
            /**
             * If the first line matches a String stored in memory
             * then print the next one
             */
            if(DFAStringMatching(slogan[i], query))
                cout << slogan[i+1] << "\n";
        }
    }

    return 0;
}

UVA Problem 10696 – f91 Solution

UVA Problem 10696 – f91 Solution:


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

Solving Technique:

This is a simple DP problem (OR, so it looks but there’s a better way). It can be solved both iteratively and recursively with or without memoization. Still it will get accepted. But still the runtime is slow due huge input. So using a faster io may help it get accepted with a better rank.

For the matter of practice i will show all four methods i know of to solve this problem. Codes are given in this order,

  1. dynamic programming solution.
  2. Recursive solution without Memoization.
  3. Recursive solution with Memoization.
  4. Shortcut Trickery.
  5. Maybe extend the shortcut Trickery with memoization or other technique by yourself ? try it !!
Before starting to look below take look at this codes ( Fibonacci DP, Memoization ) with explanation.

Solution explanation:

Here the formula is given, we just need rearrange it and get the recurrence relation,

If N ≤ 100, then f91(N) = f91(f91(N+11));
If N ≥ 101, then f91(N) = N-10.

So from the given statement generating recurrence relation will be,

f(n) = { f(f(n+11)), if n <= 100
       { n - 10,     if n >= 101

Here base case is for any n greater than or equal to 101 is return n – 10. No more recursive call on that.
This can be simplified but i won’t go into that. The codes below will give a better idea.

Now, just create a function named f and use if else or ternary to implement the given relation and it’ll work.

Memoization:

Since we’ve found out the recurrence relation it won’t be hard to memoize the code. We can use a memo array to store the already calculated results. We need not change much from the previous recursive solution to memoize it.

Add an if condition in the beginning if the value is already calculated and stored in memo array just return. Other wise when returning just store the return values in memo.

That’s it.

Dynamic Programming ( bottom up method ):

Our recurrence relation will never change. Since there is no other function needed we just calculate and store values in memo array. I started from 1,000,000 because the problem statement said an integer may be at most 1,000,000. Just loop through that many times and store results in memo array.

Last Solution Trick:

It come to me when i was testing my own inputs. Anything less or equal 100 result in 91. Any greater value results in that value minus 10. Take a look at the code below to get the idea.

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++.


Input:

500
91
1
5
190
100
101
0

 


Output:

490
91
91
91
180
91
91

Code Bottom Up (Iterative) Dynamic Programming:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    Bottom Up (Iterative) Dynamic Programming
 */

#include<cstdio>
#include<sstream>

using namespace std;

#define N 1000000

static int F[N];

int main(){
    int n, i;

    for(i = N; i >= 0; --i){
        if(i >= 101)
            F[i] = i - 10;
        else
            F[i] = F[F[i + 11]];
    }

    while(scanf("%d", &n) && n)
        printf("f91(%d) = %d\n", n, F[n]);

    return 0;
}

Code Top Down (Recursive) Without Memoization:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    Top Down (Recursive) without Memoization
 */

#include<stdio.h>

int f(int n){
    return (n >= 101) ? n - 10 : f(f(n + 11));
}

int main(){
    int n;

    while(scanf("%d",&n) && n)
        printf("f91(%d) = %d\n", n, f(n));

    return 0;
}

Code Top Down (Recursive) with Memoization:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    Top Down (Recursive) with Memoization
 */

#include<stdio.h>

static unsigned F[1000000];

unsigned f(unsigned n){
    if(F[n])
        return F[n];

    if(n >= 101)
        return F[n] = n - 10;
    else
        return F[n] = f(f(n+11));
}

int main(){
    unsigned n;

    while(scanf("%u",&n) && n)
        printf("f91(%u) = %u\n", n, f(n));

    return 0;
}

Shortcut Technique:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10696 - f91
 * Type:    shortcut technique
 */

#include<stdio.h>

int main(){
    unsigned n;

    while(scanf("%u", &n) && n){
        if(n <= 100)
            printf("f91(%d) = 91\n", n);
        else
            printf("f91(%d) = %d\n", n, n - 10);
    }

    return 0;
}

Ternary Heap Sort Code in C++ using Heap Data structure

Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

Ternary Heap Sort Code Cpp:

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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
    int largest;

    /**
     * Find right child index
     */
    int l = 3 * i + 1;

    /**
     * Compare left child against the current node
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * find mid child index
     */
    int m = 3 * i + 2;

    /**
     * Compare mid child against the calculated largest value node
     */
    if(m < heapsize && A[m] > A[largest])
        largest = m;

    /**
     * Find right child index
     */
    int r = 3 * i + 3;

    /**
     * Compare right child against the calculated largest value node
     */
    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /*
     * If child nodes have larger value then current node
     */
    if(largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    int j;
    /**
     * operate on third of array
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    int i;
    for(i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);

        /**
         * Decrease the heap size as right of heap is already sorted
         */
        --heapsize;

        /**
         * Again max heapify the rest of the heap
         */
        maxHeapify(0);
    }
}

int main(){
    int i;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for(i=0; i<SIZE; ++i){
        A[i] = rand() % SIZE;
        printf("%d ", A[i]);
    }
    printf("\n");

    printf("Sorting Now....\n");
    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i=0; i<SIZE; ++i)
        printf("%d ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

UVA Problem 10684 – The jackpot Solution

UVA Problem 10684 – The jackpot Solution:


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

Solving Technique:

This is an maximum sub array sum problem. Here we need find maximum subarray sum in 1D array. It can be solved easily with Kadane’s algorithm in O(n) time.

One thing to keep in mind the sample input isn’t properly aligned. So input format may be a bit confusing.

Explanation:

If the sum of array elements become 0 then we should set the sum to zero. Meaning we didn’t take any previous elements. Otherwise if we keep sum negative then we’ll never have the correct answer. Since we could get a bigger sum by discarding negative sum subset.

For example,

5
12  -4  -10  4  9

Here from first element to -10 we have a sum of -2. If we then add 4, 9 to the current sum -2 the max value is 11. But we could get a better result by discarding all previous sum since 12, -4, -10 produces a negative sum. There is no meaning taking a negative value. So discarding all previous sums till -10 then adding 4, 9 we get a max value of 13.

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
12  -4  -10  4  9
3
-2 -1 -2
0

 


Output:

The maximum winning streak is 13.
Losing streak.

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10684 - The jackpot
 */

#include<stdio.h>

static int subset[10002];

int main(){
	static unsigned n, i;
	static int sum, max;

	while(scanf("%u", &n) && n){

        sum = max = i = 0;

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

            if(sum < 0)
                sum = 0;

            if(sum > max)
                max = sum;
        }

        if(max > 0)
            printf("The maximum winning streak is %d.\n", max);
        else
            printf("Losing streak.\n");
	}
	return 0;
}