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 11716 – Digital Fortress Solution

UVA Problem 11716 – Digital Fortress Solution:


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

Solving Technique:

This is an easier string problem. The task is to arrange the characters within the string in a certain order.

If the input string length is not square of a number then print INVALID. Ex: “DAVINCICODE” has length of 11. Squaring no number results in 11.

“DTFRIAOEGLRSI TS” has length of 16 including the space character. Square root of 16 is 4 and 4 * 4 is 16. So this is valid input.

Now if the input is valid then next task is to rearrange them. Instead of following given solution technique in the question it can solved much faster in another way. Following instruction in the question gives intuition that first the string must be positioned on 2 dimensional matrix in row major order. Then traverse them column by column.

A better way is find out each group length from square rooting the original string length. Next starting from first group take a character then skip by group length to get next column major character. After its done do this from the next character of first group.


Visualization:
uva 11716 rearrange string in column major order
uva 11716 rearrange string in column major order

 

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
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS

 


Output:

WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11716 - Digital Fortress
 * Technique: Square String Traverse from row major
 *            to column major by skipping.
 */

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


#define N 10002
static char s[N];
static char output[N];


int main(){

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


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


    while( n-- ){
        gets(s);


        // Get the length of string and length of each string group.
        int len = strlen(s);
        int rc = sqrt(len);


        // Reset in case there are characters from previous iteration.
        memset(output, 0, sizeof output);



        // If the string length can be divided into equal parts
        // then traverse by skipping certain length.
        if( rc * rc == len ){

            int k = 0;

            for( int j = 0; j < rc; ++j ){
                for( int i = j; i < len; i = i + rc ){
                    output[k++] = s[i];
                }
            }

            puts(output);

        }
        else{
            puts("INVALID");
        }

    }


    return 0;
}

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 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 11565 – Simple Equations Solution

UVA Problem 11565 – Simple Equations Solution:


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

UPDATE:

As a commenter below pointed out the solution is wrong due to the fact I made some wrong assumptions. Kindly check other sources for correct solution. This was accepted due to weak test cases. Also check udebug for different test cases.

Problem Statement Description:

Given input of A, B, C where 0 \leqslant A, B, C \leqslant 10000 and three equations,

\mathbf{ x + y + z = A }
\mathbf{ x.y.z = B }
\mathbf{ x^2 + y^2 + z^2 = C }

The task is to find values of x, y, z where x, y, z are three different integers which is ( x != y != z ). Meaning x can not be equal to y, t can not be equal to z and z can not be equal to x.

The problem asks to output the least value of x then y then z meaning the output will be in x < y < z order.


Things to notice:

One very important thing to notice is that for all three equation the values of x, y, z can be interchanged and it will still satisfy the problem.

For example,
\mathbf{ if, x = 5, y = 0, z = 9 }

then it can also be written as,
\mathbf{ x = 0, y = 5, z = 9 }
\mathbf{ x = 9, y = 5, z = 0 }

etc. all possible combinations. But the problem asks for least value of x then y then z.

So if after calculation the result is x = 9, y = 0, z = 5 which is supposed to be x = 0, y = 5, z = 9. In that case the values can be sorted which will result in x = 0, y = 5, z = 9 and this still satisfies the equations.


Solution Technique Explanation:

The simple approach to solve this problem is try all possible combinations of x, y, z and see if it produces a correct result.

The values of x, y, z being negative also satisfies this problem. Forgetting the value of negatives for the moment and focusing on the positive values. To get the naive loop count limit see x or y or z can be at least 0 and at most 100.

Same goes for the negative portion so looping for -100 to 100 for each 3 nested loops seem easy ( I haven’t given the 3 nested loop solution here. It can be found on other sites ). So from -100 to 0 to 100 there are 201 number in between. So naive solution requires 201*201*201 which is more than 8 million (8120601). This program should do 117 * 45 = 5265 iterations per test case.


This problem can be solve much faster using some algebraic substitution. Notice,

\mathbf{ x + y + z = A ........ (i) \\ }
\mathbf{ x.y.z = B ........ (ii) \\ }
\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) \\ }

from equation (ii),

\mathbf{ x.y.z = B }

This can be rewritten as,

\mathbf{ z = \frac{B}{x.y} ........ (iv) }

from equation (i),

\mathbf{ x + y + z = A }

substituting value of z from (iv) to (i) gives,

\mathbf{ x + y + \frac{B}{x.y} = A }

This can be rewritten as,

\mathbf{ \frac{B}{x.y} = A - x - y ........ (v) }

similarly from (iii) and (iv),

\mathbf{ x^2 + y^2 + z^2 = C }

plugging in the value of z and solving for x and y,

\mathbf{ x^2 + y^2 + ( \frac{B}{x.y} )^2 = C ........ (vi) }

Now from (v) and (vi),
\mathbf{ x^2 + y^2 + (A - x - y)^2 = C }

Notice this equation above does not contain z. Now z can be calculated in terms of B, x, y.

This will completely remove one of the nested loops. Further improvements can be made by cutting down number of loop iterations.


Important point to notice that A, B, C can be at most 10000. Also x, y, z can differ by 1 and satisfy the equation. From above equations,

\mathbf{ x + y + z = A ........ (i) }
\mathbf{ x.y.z = B ........ (ii) }
\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) }

So if x, y, z differ by 1 then,

\mathbf{ y = x + 1 }
\mathbf{ z = x + 2 }

from equation (i),

\mathbf{ x + (x + 1) + (x + 2) = A }

but A can be at most 10000.

\mathbf{ x + (x + 1) + (x + 2) = 10000 }
\mathbf{ 3x + 3 = 10000 }

So, x = 3332.3333….

But to keep it simple, notice the lower order term 3 does not make much difference. By setting x = y = z the equation can be,

\mathbf{ x + x + x = 10000 }
\mathbf{ 3x = 10000 }
\mathbf{ x = 3333.3333.... }


from equation (iii) since x is squared so it to get its iteration just calculate the square root. or, setting x = y = z and B = 10000 in equation (iii) gives,

\mathbf{ x^2 + x^2 + x^2 = 10000 }
\mathbf{ 3x^2 = 10000 }
\mathbf{ x = 57.735.... }

after rounding of,
x = 58

So the loop range for x is [-58…58].


Again from equation (ii) the iteration limit for y can be counted using x = y = z,

\mathbf{ y.y.y = 10000 }
\mathbf{ y^3 = 10000 }
\mathbf{ y = 21.544.... }

Rounded of to,
y = 22

So iteration limit for y will be from [-22…22].

Calculating using y + 1 result in rounded range [-21…21]. Although I have not tested it.


Doing further algebraic simplification will remove another loop as z can be calculated in terms of A,B,C using,

\mathbf{ (A-z)^2 - 2.\frac{B}{z} = C - z^2 }

where,

\mathbf{ xy = \frac{B}{z} }

and,

\mathbf{ x + y = A - z }

using the main equation above, the value of z can be found and by solving the other equations the values of x and y can be calculated.


Also the loops can be input dependent. If max of A, B, C is bigger than 58 than choose 58 other wise choose the max as the loop counter.

There may be more improvements possible but that’s all I can come up with now. One final improvement can be made by breaking from all loops at once once the values are found. Although goto isn’t recommended c++ doesn’t support label to break out of multiple loops unlike java.

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
1 2 3
6 6 14

Output:

No solution.
1 2 3

Optimized Code without goto:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11565 - Simple Equations
 * Technique: Mathematical elimination and substitution
 */

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    int A, B, C;

    while( n-- ){
        scanf("%d%d%d", &A, &B, &C);

        bool solutionFound = false;
        int x, y, z;

        for( x = -58; x <= 58; ++x ){
            for( y = -22; y <= 22; ++y ){

                if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

                    int temp = x * y;

                    if( temp == 0 ) continue;

                    z = B / temp;

                    if( z != x && z != y && x + y + z == A   ){
                        if(!solutionFound){
                            int tmpArray[3] = {x, y, z};
                            std::sort(tmpArray, tmpArray + 3);
                            std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

                            solutionFound = true;
                            break;
                        }
                    }

                }
            }
        }

        if(!solutionFound) std::cout << "No solution." << "\n";

    }

    return 0;
}

Optimized Code without goto:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11565 - Simple Equations
 * Technique: Mathematical elimination and substitution
 */

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

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

    int A, B, C;

    while( n-- ){
        scanf("%d%d%d", &A, &B, &C);

        bool solutionFound = false;
        int x, y, z;

        for( x = -58; x <= 58; ++x ){
            for( y = -22; y <= 22; ++y ){

                if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

                    int temp = x * y;

                    if( temp == 0 ) continue;

                    z = B / temp;

                    if( z != x && z != y && x + y + z == A   ){
                        if(!solutionFound){
                            int tmpArray[3] = {x, y, z};
                            std::sort(tmpArray, tmpArray + 3);
                            std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

                            solutionFound = true;
                            goto done;
                        }
                    }

                }
            }
        }

        if(!solutionFound) std::cout << "No solution." << "\n";
        done:;

    }

    return 0;
}

 

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