UVA Problem 10432 – Polygon Inside A Circle Solution

UVA Problem 10432 – Polygon Inside A Circle Solution:


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

Solving Technique:

This is a rather easy geometry / computational geometry problem. Given the radius of a Circumscribed circle and count of sides of a polygon the task is to find the area of the polygon. A Circumscribed circle is a circle that passes through all vertices of a plane figure and contains the entire figure in its interior.

The formula below can be written into a single formula by combining all the formulas. More information and the combined formula can be found here.

Learn more about regular polygon here including the formula.


Visual Explanation:

I have tried to explain the concept below using figures. They are not drawn to scale. The small circles represent intersection point between polygon vertices and the circumscribed circle.


Circumcircle figure 1
Circumcircle figure 1

Circumcircle figure 2
Circumcircle figure 2

Circumcircle figure 3
Circumcircle figure 3

Example:

It is an example with radius, r = 2 and sides, n = 8.

Circumcircle figure 4 example
Circumcircle figure 4 example

 

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:

2 2000
10 3000

 


Output:

12.566
314.159

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10432 - Polygon Inside A Circle
 * Technique: circumcircle Or, Isocele Area calculation.
 */

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


int main(){

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


    double r;
    int n;

    while( scanf( "%lf%d", &r, &n ) == 2 ){

        // Angle between each two points for every point.
        double PHI = ( double ) 360 / n ;

        // For each Isosceles in the polygon the angle between the base and radius.
        double THETA = (double) 90 - ( PHI / 2 );


        // Convert Degree angle to Radian to use in code.
        double THETA_RADIAN = THETA * M_PI / 180;


        //  a is base.
        double a = 2 * r * cos( THETA_RADIAN );

        // H is the height.
        double h = r * sin( THETA_RADIAN );

        // S represent Area of a single segment.
        double S = (a * h) / 2;


        // S * n is the are of complete polygon.
        printf("%.3lf\n",  S * n );


    }

    return 0;
}
Advertisements

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

UVA Problem 11988 – Broken Keyboard (a.k.a. Beiju Text) Solution

UVA Problem 11988 – Broken Keyboard (a.k.a. Beiju Text) Solution:


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

Solving Technique:

The input may be classified into three things. One is append to beginning represented with ‘[‘, another is append to end represented with ‘]’ and the other types any other character except above mentioned. The other character are appended to the next position of last inserted character.

So task is move all characters following ‘[‘ to beginning until ‘]’ is found or end of string is reached. Similar logic applies to ‘]’ character. Also it is a recursive definition, keep applying this logic for all the following third brackets.


Other ideas:

Some other ideas to solve this problem can be, formatting the input to remove useless brackets then create a tree from inputs and perform in-order traversal to get the result. Another idea is create a linked list of strings.


Code Explanation:

I may later ( takes quite bit of time to create graphics ) provide a graphical representation of inserting in the doubly linked list ( 2nd code ). Meanwhile I provided a commented version ( 2nd code ) to make it a little easier to understand.

Here I have provided two codes. Both are linked list implementations. First one is singly linked list with no tail pointer( rather inefficient although I try to reduce some complexity by Boolean flag checking to reduce traversing the list to find tail pointer ). It is not able to keep track of tail pointer efficiently. Need to do some traversing ( some times almost the whole linked list ) to find the tail pointer.

The second implementation is doubly linked list with tail node as the tail pointer. The tail pointer has character has 0 which is ASCII decimal code for NULL character. I use this to stop printing otherwise a space character is printed at the end of output.

 

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:

This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

 


Output:

BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

Code Singly Linked list Without Tail:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11988 - broken keyboard
 * Technique: Singly Linked List with no
 *            tail Pointer(slow).
 */

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


#define N 100000

static char input[N];


struct vertex{
    char c;
    struct vertex* next;
};

typedef struct vertex node;


node* insertNode(node* n, char c){

    node* temp = new node();
    temp->c = c;
    temp->next = n->next;
    n->next = temp;

    return temp;
}


void printList( node* dummy ){

    node* tmp = dummy;

    while( tmp = tmp->next )
        putchar( tmp->c );

    printf("\n");
}


int main(){

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


    while( gets(input) ){

        node* dummy = new node();
        dummy->next = NULL;
        node* cur = dummy;


        node* tail = dummy;

        bool rightopen = false;

        for(int i = 0; input[i]; ++i){

            if( input[i] == '[' ){
                cur = dummy;
                rightopen = true;
                continue;
            }
            if( input[i] == ']' ){
                rightopen = false;

                node *tmp = tail;

                while( tmp->next != NULL )
                    tmp = tmp->next;

                tail = cur = tmp;
                continue;
            }

            cur = insertNode(cur, input[i] );
            if( !rightopen )
                tail = cur;
        }

        printList( dummy );

    }


    return 0;
}

Code Doubly Linked list With Tail Pointer:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11988 - broken keyboard
 * Technique: Doubly Linked List with
 *            dummy tail node as Pointer.
 */

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


#define N 100000


static char input[N];



// Doubly linked list.
struct vertex{
    char c;
    struct vertex* next;
    struct vertex* prev;
};
typedef struct vertex node;



node* insertNode(node* n, char c){

    // Create the new node to hold current character.
    node* temp = new node();
    temp->c = c;


    // Create forward connection from this created node
    // to the next node of passed in node (n).
    // Also create backward connection from the passed
    // in node to current node.
    temp->next = n->next;
    n->next->prev = temp;


    // Create forward connection from passed in node (n) to the
    // newly created node (temp).
    // Also create backward connection from created node to the
    // passed in node.
    n->next = temp;
    temp->prev = n;


    // return the pointer to the current node.
    return temp;
}



void printList( node* dummy ){

    // Dummy (head) is not a part of output.
    node* tmp = dummy->next;


    // Since I use tail pointer, check if its tail.
    while( tmp->c ){
        putchar( tmp->c );
        tmp = tmp->next;
    }

    printf("\n");
}



int main(){

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


    while( gets(input) ){

        // Dummy node is just to keep track of beginning.
        // It does not contain any input character.
        // Tail is used to insert before the last node.
        // Tail is also another dummy node keeps track of
        // the end.
        node* dummy = new node();
        node* tail = new node();


        // NULL may not be necessary since I use tail character
        // checking to stop printing.
        tail->prev = dummy;
        dummy->next = tail;
        tail->next = NULL;
        dummy->prev = NULL;


        // Set current node to dummy (beginning). Set tail
        // to NULL character equivalent ASCII value.
        node* cur = dummy;
        tail->c = 0;


        for(int i = 0; input[i]; ++i){

            // Update node pointer to beginning based on bracket.
            // If not bracket use previous pointer location.
            if( input[i] == '[' ){
                cur = dummy;
                continue;
            }
            if( input[i] == ']' ){
                cur = tail->prev;
                continue;
            }

            cur = insertNode(cur, input[i] );
        }


        // Print output characters one by one.
        printList( dummy );

    }


    return 0;
}

UVA Problem 12646 – Zero or One Solution

UVA Problem 12646 – Zero or One Solution:


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

Solving Technique:

The input is all possible combination of 3 bits. If A, B, C are thought as bits then possible binary combination are,

000 \rightarrow * \\  001 \rightarrow C \\  010 \rightarrow B \\  011 \rightarrow A \\  ---- \\  100 \rightarrow A \\  101 \rightarrow B \\  110 \rightarrow C \\  111\rightarrow * \\

This problem can be solved in multiple ways such as using string, checking equality, performing xor equality etc. My code below is exactly same as equality checking but it perform xor operation between them.

XOR Table,

\begin{tabular}{l*{6}{c}r}  X & Y & X XOR Y \\ \hline  0 & 0 & 0 \\  0 & 1 & 1 \\  1 & 0 & 1 \\  1 & 1 & 0 \\  \end{tabular}
 

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:

1 1 0
0 0 0
1 0 0

 


Output:

C
*
A

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 12646 - zero or one
 * Technique: XOR Bits to check equality.
 */

#include<stdio.h>


int main(){

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


    int A, B, C;
    while( scanf("%d%d%d", &A, &B, &C) == 3 ){

        if( !( A ^ B ) && !( A ^ C ) )
            putchar('*');
        else{
            if( A ^ B ){
                if( B ^ C )
                    putchar('B');
                else
                    putchar('A');
            }
            else
                putchar('C');
        }
        putchar('\n');
    }


    return 0;
}

UVA Problem 10189 – Minesweeper Solution

UVA Problem 10189 – Minesweeper Solution:


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

Solving Technique:

Given a mine field that is a matrix / 2D array, produce an output that contains count of adjacent mines for each squares.

In a 2D array for each squares there are at most adjacent 8 squares. If the current position is i and j then,

\begin{bmatrix}  (i-1,j-1) & (i-1,j) & (i-1,j+1) \\  (i+0,j-1) &  (i,j)  & (i+0,j+1) \\  (i+1,j-1) & (i-1,j) & (i+1,j+1) \\   \end{bmatrix}

Just traverse the matrix row-column wise and check its adjacent squares for getting mine count for current position. The adjacent squares check can be implemented with 8 if conditions for each one.

Another technique is to store the co-ordinates of adjacent squares and using a for loop to check them. The illustration below shows how the 2nd code is implemented using arrays and for loops,
uva 10189 matrix adjacent squares check with saved co-ordinates and for loop
uva 10189 matrix adjacent squares check with saved co-ordinates and for loop

Here the arrow from the center shows where checking starts. The 1D arrays drow and dcol hold the row and column values the way shown above. It can be changed by modifying drow and dcol arrays.

 

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:

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

 


Output:

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

Code Using Multiple if Conditions:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10189 - Minesweeper
 * Technique: 2D Array / Matrix Boundary checking using
 *            if conditions.
 */

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


#define MAXSIZE 101


static char MineField[MAXSIZE][MAXSIZE];



int main(){

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


    int n, m;

    int FieldNumber = 0;

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

        getchar();

        for(int i = 0; i < n; ++i)
            scanf("%s", &MineField[i]);


        if( FieldNumber )
            printf("\n");


        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){

                if( MineField[i][j] == '*' )
                    continue;

                int temp = 0;

                if( i + 1 < n && MineField[i + 1][j] == '*' )
                    ++temp;
                if( i + 1 < n && j + 1 < m && MineField[i + 1][j + 1] == '*' )
                    ++temp;
                if( j + 1 < m && MineField[i][j + 1] == '*' )
                    ++temp;
                if( i - 1 >= 0 && j + 1 < m && MineField[i - 1][j + 1] == '*' )
                    ++temp;
                if( i - 1 >= 0 && MineField[i - 1][j] == '*' )
                    ++temp;
                if( i - 1 >= 0 && j - 1 >= 0 && MineField[i - 1][j - 1] == '*' )
                    ++temp;
                if( j - 1 >= 0 && MineField[i][j - 1] == '*' )
                    ++temp;
                if( i + 1 < n && j - 1 >= 0 && MineField[i + 1][j - 1] == '*' )
                    ++temp;


            MineField[i][j] = temp + '0';

            }
        }


        printf("Field #%d:\n", ++FieldNumber);


       for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                putchar(MineField[i][j]);
            printf("\n");
       }

    }

    return 0;
}

Code Bound checking using Array & for Loop:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10189 - Minesweeper
 * Technique: 2D Array / Matrix Boundary checking using
 *            co-ordinate array and for loop.
 */

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


#define MAXSIZE 101


static char MineField[MAXSIZE][MAXSIZE];


// Co-ordinates / directions of adjacent 8 squares.
// W, SW, S, SE, E, NE, N, NW
static const int drow[] = {0, 1, 1, 1, 0, -1, -1, -1};
static const int dcol[] = {-1, -1, 0, 1, 1, 1, 0, -1};



int main(){

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


    int n, m;

    int FieldNumber = 0;

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

        getchar();

        for(int i = 0; i < n; ++i)
            scanf("%s", &MineField[i]);


        if( FieldNumber )
            printf("\n");


        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){

                int temp = 0;

                // If mine found do nothing.
                if( MineField[i][j] == '*' )
                    continue;


                // For each adjacent squares of the current square calculate mine count.
                // and set the count in current square.
                for(int k = 0; k < 8; ++k){

                    // Check if out of bound of the 2D array or matrix.
                    if( i + drow[k] < 0 || j + dcol[k] < 0 || i + drow[k] >= n || j + dcol[k] >= m )
                        continue;

                    // Check the appropriate co-ordinate for mine, if mine found increase count.
                    if( MineField[i + drow[k] ][j + dcol[k]] == '*' )
                        ++temp;

                }

                // All adjacent squares checked set the mine count for current squares.
                MineField[i][j] = temp + '0';

            }
        }


        printf("Field #%d:\n", ++FieldNumber);


       for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j)
                putchar(MineField[i][j]);
            printf("\n");
       }

    }

    return 0;
}

UVA Problem 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:


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

Solving Technique:

Task for this problem is to find occurrence of each alphabetical character. Uppercase and lowercase are treated as same characters. No other characters except for upper and lower case characters must be counted.

After counting their occurrence print them in most to least order. If multiple characters have same character count then print the characters alphabetically. Ex: If E occurred 2 times, A occurred 2 times then, print A first then E.
 

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
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?

 


Output:

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10008 - What's Cryptanalysis
 * Technique: Counting character occurrence in string,
 *            Lexicographical / alphabetically sort characters,
 */


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


#define N 256


// Holds each character and its occurrence in string.
struct collection{
    char character;
    int occurence;
} node[26];


static char s[N];


// Sorts based on occurrence, if occurrence count is same
// then sort using lexicographical / alphabetically first character.
int cmp(collection a, collection b){

    if(a.occurence < b.occurence)
        return 0;
    else if(a.occurence > b.occurence)
        return 1;
    else
        return (a.character <= b.character) ? 1 : 0;

}



int main(){

    // O(1)
    // Represent character by its ASCII value index.
    for(int i = 'A'; i <= 'Z'; ++i)
        node[i].character = i;

    int n;

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

    while( n-- ){

        gets( s );

        // Convert string to uppercase O(n)
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'a' && s[i] <= 'z')
                s[i] = s[i] - 32;
        }


        // O(n)
        // Counting using character index
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'A' && s[i] <= 'Z' )
                ++node[ s[i] ].occurence;
        }

    }


    // Sorts occurrence most to least and in lexicographic order.
    std::sort(node + 'A', node + 'Z', cmp);


    // O(1)
    // Prints sorted occurrence most to least.
    // Also prints characters in lexicographic
    // order if two occurrence are same.
    for(int i = 'A'; i <= 'Z'; ++i){
        if(node[i].occurence)
            printf("%c %d\n", node[i].character, node[i].occurence);
    }



    return 0;
}

UVA Problem 11713 – Abstract Names Solution

UVA Problem 11713 – Abstract Names Solution:


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

Solving Technique:

For input of n there will be 2*n lines. Task is to match a pair of lines. The vowels a, e, i, o, u in the strings doesn’t matter. Except these the rest of both strings should match.

That means each character in a index from both strings should match. Their order needs to be same. Except vowels if the match then output is yes. Otherwise the output is no.

 

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:

5
pele
polo
pele
pola
ronaldo
ronaldino
pele
pelet
pele
bele

 


Output:

Yes
Yes
No
No
No

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11713 - Abstract Names
 * Technique: Removing specific characters from string
 *            by copying into another string.
 */

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

#define N 36


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

static char tmpS[N];
static char tmpT[N];


int main(){

    int n;

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

    while( n-- ){


        gets(s);
        gets(t);


        // If their length is not the same then output is no.
        if( strlen(s) != strlen(t) ){
            printf("No\n");
            continue;
        }


        // Reset memory.
        int j = 0, k = 0;
        memset(tmpS, 0, sizeof tmpS);
        memset(tmpT, 0, sizeof tmpT);


        // Remove vowels from the first string.
        for(int i = 0; s[i]; ++i){
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
                continue;
            else
                tmpS[j++] = s[i];
        }


        // Remove vowels from the second the string.
        for(int i = 0; t[i]; ++i){
            if(t[i] == 'a' || t[i] == 'e' || t[i] == 'i' || t[i] == 'o' || t[i] == 'u')
                continue;
            else
                tmpT[k++] = t[i];
        }


        // After removing the vowels the strings should match.
        if( strcmp(tmpS, tmpT) == 0 )
            printf("Yes\n");
        else
            printf("No\n");

    }

    return 0;
}

UVA Problem 424 – Integer Inquiry Solution

UVA Problem 424 – Integer Inquiry Solution:


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

Solving Technique:

This problem requires adding integers. The integers are very long, meaning they won’t fit even in long long. So the addition needs to be done using arrays.

It can be solved using integers arrays but my solution uses character array. Code is explained in the comments.

Similar to this problem UVA 10035 Primary Arithmetic and UVA 713 – Adding Reversed Numbers.

 

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:

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0

 


Output:

370370367037037036703703703670

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 424 - Integer Inquiry
 * Technique: Adding Multi String Integer characters column wise
 */


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

#define N 160


static char s[N][N];
static char output[N];



int main(){

    int i = 0;

    int maxlen = 0;


    // Finish taking all the inputs.
    while( gets(s[i]) ){

        // Exit for input of 0.
        if( s[i][0] == '0' && ! s[i][1] )
            break;

        int len = strlen( s[i] );

        // Get the max length to create padding.
        if( len > maxlen )
            maxlen = len;

        ++i;
    }

    // Save rows
    int rows = i;


    // Create padding for each of the strings.
    for(int j = 0; j < i; ++j){

        int temp = strlen( s[j] );

        if( temp != maxlen ){

            // Shift by this many spaces to create 0's in front.
            int padding = maxlen - temp;

            // shift by padding columns.
            for(int k = temp - 1; k >= 0; --k)
                s[j][k + padding] = s[j][k];

            // Add 0's as paddings.
            for(int k = 0; k < padding; ++k)
                s[j][k] = '0';
        }
    }


    int carry = 0, z = 0;

    for(int j = maxlen - 1; j >= 0; --j){

        int sum = 0;

        // Add values column wise.
        for(int i = 0; i < rows; ++i)
            sum += s[i][j] - '0';

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

        // Add value to output
        output[z++] = sum % 10 + '0';

        // get the carry for adding to next column
        carry = sum / 10;

    }

    // Print if any carry first
    if(carry)
        printf("%d", carry);


    // Then print what ever character is left
    for(int i = z - 1; i >= 0; --i){
        if(output[i] >= '0' && output[i] <= '9')
            printf("%c", output[i]);
    }
    printf("\n");

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