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

 

UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:


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

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

In this problem a few key points are,
  1. The amount doesn’t exceed $300.00
  2. Exit / terminate program for the input of 0.00
  3. Amount can be / is a floating point number
  4. There are different values that can be used make up the decimal and the fractional portion
  5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of.

Solution Technique:

Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is, $1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

For example,
  • $4.70      =      470 cents
  • $2.00      =      200 cents
  • $6.75      =      675 cents
  • $300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

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. Compile with C++ to be safe from compile errors although some codes do work with C compiler.


Input:

0.20
2.00
4.90
6.70
8.45
0.00

 


Output:

  0.20                4
  2.00              293
  4.90             5698
  6.70            19187
  8.45            49007

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars
 */

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

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

    c[0] = 1;
    for(i = 0; i < 11; ++i){
        for(j = coins[i]; j < N; ++j)
            c[j] += c[j - coins[i]];
    }

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}

Code (Loop Split):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 147 - Dollars ( Loop Split )
 */

#include<stdio.h>

#define N 30002

static long long c[N];

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

    c[0] = 1;

    /*
     * Loop Split
     */

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

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

    for(j = 20; j < N; ++j)
        c[j] += c[j - 20];

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

    for(j = 100; j < N; ++j)
        c[j] += c[j - 100];

    for(j = 200; j < N; ++j)
        c[j] += c[j - 200];

    for(j = 500; j < N; ++j)
        c[j] += c[j - 500];

    for(j = 1000; j < N; ++j)
        c[j] += c[j - 1000];

    for(j = 2000; j < N; ++j)
        c[j] += c[j - 2000];

    for(j = 5000; j < N; ++j)
        c[j] += c[j - 5000];

    for(j = 10000; j < N; ++j)
        c[j] += c[j - 10000];

	while(scanf("%f", &n) == 1 && n){
        // Rounding error fix
        unsigned coin = (unsigned)((n + 0.001) * 100);

        // 6 width justified including the input amount and 17 width afterwards including count
        printf("%6.2f%17lld\n", n, c[coin]);
    }
	return 0;
}

UVA Problem 357 – Let Me Count The Ways Solution

UVA Problem 357 – Let Me Count The Ways Solution:


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

Solving Technique:

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

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

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

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


Input:

17 
11
4

Output:

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

Split Loop Code:

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

#include<stdio.h>
#define N 30002

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

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

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

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

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

Combined / Loop Fusion:

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

#include<stdio.h>
#define N 30002

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

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

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

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

UVA Problem 674 – Coin Change Solution

UVA Problem 674 – Coin Change Solution:


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

Solving Technique:

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

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

We can also replace this,

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

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

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

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

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

Explanation:

/* TO DO */

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


Input:

11
26
5
4

Output:

4
13
2
1

Code Bottom Up:

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

#include <stdio.h>
#define N 8000

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

int main()
{
    register int i, j;

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

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

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

    return 0;
}

Loop Fission Variant:

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

#include <stdio.h>

#define N 8000
#define M 5

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

int main()
{
    register int i, j;

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

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

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

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

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

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

    return 0;
}

UVA Problem 10327 – Flip Sort Solution

UVA Problem 10327 – Flip Sort Solution:


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

Solving Technique:

Another sorting problem that requires us to “exchange two adjacent terms”. Use any stable sort to count the number of swaps. That is the output.

Here among three code the first one is a hybrid distribution between insertion sort and merge sort to count inversions / swaps. The next two codes are merge sort and bubble sort.

This merge sort also be made to work with selection sort. Please see Introduction to Algorithms book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein for more detail.

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


Input:

3
1 2 3
3
2 3 1

Output:

Minimum exchange operations : 0
Minimum exchange operations : 2

Hybrid Merge Sort and Insertion Sort Distribution:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

#define INSERTION_SORT_THERSHOLD 20

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid - front + 1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void insertionSort(int front, int rear) {
    register int i, j;
    int key;

    for (i = front + 1; i <= rear; ++i) {
        key = A[i];
        j = i - 1;
        while (j >= front && A[j] > key) {
            A[j + 1] = A[j];
            ++c;
            --j;
        }
        A[j + 1] = key;
    }
}

/**
 * Hybrid distribution between insertion sort and merge sort
 * Performs slower than regular merge sort for this small input range
 * Such distribution also works with selection sort
 * Please refer to book introduction to algorithm for more
 */
void HybridMergesort(int front, int rear){
    if(rear - front < INSERTION_SORT_THERSHOLD)
        insertionSort(front, rear);
    if(front < rear){
       int mid = (rear + front) >> 1;
       HybridMergesort(front, mid);
       HybridMergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);

        HybridMergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Merge Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<stdio.h>
#include<limits.h>

static int A[1024], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    register unsigned int i, j, n;
    unsigned key;
	while(scanf("%u", &n) == 1){
        for(i = c = 0; i < n; ++i)
            scanf("%u", &A[i]);
        Mergesort(0, n - 1);

        printf("Minimum exchange operations : %u\n", c);
	}
	return 0;
}

Bubble Sort Inversion Count:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10327 Flip Sort
 */

#include<cstdio>
#include<iostream>

static unsigned a[1024];

int main(){
    register unsigned int i, j, k, n;
	while(scanf("%u", &n) == 1){
        for(i = 0; i < n; ++i)
            scanf("%u", &a[i]);

        /**
         * Bubble Sort
         */
        for(k = j = 0; j < n; ++j){
            for(i = 0; i < n - j - 1; ++i){
                if(a[i] > a[i + 1]){
                    std::swap(a[i], a[i + 1]);
                    ++k;
                }
            }
        }

        printf("Minimum exchange operations : %u\n", k);
	}
	return 0;
}

UVA Problem 1586 – Molar mass Solution

UVA Problem 1586 – Molar mass Solution:


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

Solving Technique:

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

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

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

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

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


Input:

4 
C 
C6H5OH 
NH2CH2COOH 
C12H22O11

Output:

12.010 
94.108 
75.070 
342.296

Code ( Commented):

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

#include<stdio.h>

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

static char s[128];

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

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

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

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

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

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

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

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

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

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

Code ( Precomputed Strength Reduction Faster ):

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

#include<stdio.h>

static char s[128];

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

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

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

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

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

UVA Problem 299 – Train Swapping Solution

UVA Problem 299 – Train Swapping Solution:


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

Solving Technique:

The problem specifically asks to “find the least number of swaps of two adjacent carriages necessary to order the train”. That’s it.

It is a sorting problem and we have to count the number of swap between adjacent carriages. So a stable must be applied. Here I have provided three codes with insertion sort, bubble sort, merge sort.

Even though merge sort is O(n lg n) because input size is so small ( 0 <= L <= 50 ) it doesn’t make much difference. For Bubble sort though no need to perform swaps 🙂 just count it. A hybrid between insertion and merge sort me be a slight performance booster. I will try to include it later.

The problem UVA 11462 age sort is solved also with merge sort among other sort algorithms. A commented version merge sort can be found there.

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


Input:

3
3
1 3 2
4
4 3 2 1
2
2 1

Output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Code ( Bubble Sort No Swap ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Bubble Sort No Swap)
 */

#include<stdio.h>

/**
 * c is swap count
 */
static int A[64], c;

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

    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Bubble Sort
         */
        for(i = 0; i < m - 1; ++i){
            for(j = i + 1; j < m; ++j){
                /**
                 * No need to swap elements
                 * This code may be moved input loop
                 */
                if(A[i] > A[j])
                    ++c;
            }
        }

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Code ( Insertion Sort ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Insertion Sort)
 */

#include<stdio.h>

static int A[64], c;

int main(){
    register int n, i, j;
    int m, key;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * Insertion sort using inner for loop
         */
        for(i = 1; i < m; ++i){
            key = A[i];
            for(j = i - 1; j >= 0 && A[j] > key; --j){
                A[j + 1] = A[j];
                ++c;
            }
            A[j + 1] = key;
        }

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

Code ( Merge Sort Swap Count ):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 299 Train Swapping (Merge Sort)
 */

#include<stdio.h>
#include<limits.h>

static int A[64], c;

void Merge(int front, int mid, int rear){
    int n1 = mid-front+1;
    int n2 = rear - mid;

    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];

    register unsigned i = 0;
    for(; i < n1; ++i)
        L[i] = A[front + i];

    register unsigned j = 0;
    for(; j < n2; ++j)
        R[j] = A[mid + 1 + j];

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = j = 0;

    /**
     * Might work without swaps by just incrementing index counters
     */
    register unsigned k = front;
    for(; k <= rear; ++k){
        if(L[i] <= R[j]){
            A[k] = L[i++];
            c += j;
        }
        else
            A[k] = R[j++];
    }
}

void Mergesort(int front, int rear){
    if(front < rear){
       int mid = (rear + front) >> 1;
       Mergesort(front, mid);
       Mergesort(mid + 1, rear);
       Merge(front, mid, rear);
    }
}

int main(){
    int n, i, j, m;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &m);
        for(i = c = 0; i < m; ++i)
            scanf("%d", &A[i]);

        /**
         * To understand Merge sort see my UVA solution age sort 11462
         */
        Mergesort(0, m - 1);

        printf("Optimal train swapping takes %d swaps.\n", c);
    }
    return 0;
}

UVA Problem 10041 – Vito’s Family Solution

UVA Problem 10041 – Vito’s Family Solution:


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

Solving Technique:

This is a sorting problem. It requires us minimize the distance from Vito’s to every other house. That distance must be median because median value minimizes the distance from every side. So the median is the position of Vito’s house.

The problem requires us to find, “minimal sum of distances from the optimal Vito’s house to each one of his relatives”. So this means we calculate distance from Vito’s house ( Median ) to every other house and sum them. Meaning subtract position of every house from Vito’s house and sum their distance.

I have provided Three commented codes below. First one uses STL Sort and doesn’t calculate absolute value for distance. Second one shows the use of Insertion Sort and calculates absolute value to find their distance. The last one uses vector to store data and STL algorithm to find nth element in an array. Here ( for this code ) the calculated nth element is the median.

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


Input:

2
2 2 4
3 2 4 6

 


Output:

2
4

Code ( Without Calculating Absolute Value ):

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

#include<cstdio>
#include<algorithm>

static int A[512];

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

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

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            int dist = 0, median, key;

            for (i = 0; i < m; ++i)
                scanf("%d", &A[i]);

            /**
             * Sort the input using stl sort
             * Instead of using sorting algorithm, Try to implement Selection Algorithm to find Median in O(n) time
             */
            std::sort(A, A + m);

            /**
             * Find median dividing by two or shifting bit to left once
             * here, key is the value of median
             */
            median = m >> 1;
            key = A[median];

            /**
             * here, dist is the summation of distance of every house
             * Any value less than Median can subtracted from median will result in a positive value
             */
            for (i = 0; i< median; ++i)
                dist += key - A[i];

            /**
             * No need calculate for the median so start from (median + 1)
             * In case of value greater than Median, the Median must be subtracted from that value for positive number
             * Also by removing duplicates of median we may speed up the code
             */
            for (i = median + 1; i < m; ++i)
                dist += A[i] - key;

            printf("%d\n", dist);
        }
	}
	return 0;
}

 

Code ( Insertion Sort ):

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

#include<stdio.h>
#include<stdlib.h>

static int A[512];

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

	while (n--){
        scanf("%d", &m);
        int dist = 0, median, key;

        for (i = 0; i < m; ++i){
            scanf("%d", &A[i]);
        }

        /**
         * Insertion Sort:
         * Two portions sorted and unsorted
         */
        for (i = 1; i < m; ++i){
            key = A[i];
            j = i - 1;

            /**
             * Compare every element with sorted portion ( elements to its left )
             */
            while (j >= 0 && A[j] > key){

                /**
                 * While comparing shift items to right until the comparison is false
                 */
                A[j + 1] = A[j];
                --j;
            }

            /**
             * When comparison is False or done, we found the sorted position for that element so we insert it in that position
             */
            A[j + 1] = key;
        }

        /**
         * Find Median value, left shift once is divided by Two
         */
        key = A[m >> 1];

        /**
         * Since elements after Median is bigger than Median So, we need to find absolute value of them
         */
        for (i = 0; i < m; ++i){
            dist += abs(key - A[i]);
        }

        printf("%d\n", dist);
	}
	return 0;
}

 

Code ( using vector & n-th element to find median ):

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

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>

using namespace std;

int main(){
    register int n, m, i, j;
    int key, num;
    vector<int> v;

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

        if (m == 1){
            /**
             * If only 1 input then no need to process
             * For 1 input the distance is always Zero
             */
            scanf("%*d");
            printf("0\n");
        }

        else{
            /**
             * Input an a value and push it to vector
             */
            v.clear();
            for (i = 0; i < m; ++i){
                scanf("%d", &num);
                v.push_back(num);
            }

            /**
             * sort for median
             */
            nth_element(v.begin(), v.begin() + v.size()/2, v.end());

            /**
             * Get the value of median
             */
            key = v[v.size()/2];

            /**
             * Get distance of every value from median
             */
            int dist = 0;
            for (j = 0; j < i; ++j)
                dist += abs(key - v[j]);

            printf("%d\n", dist);

        }
    }
    return 0;
}

UVA Problem 673 – Parentheses Balance Solution

UVA Problem 673 – Parentheses Balance Solution:


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

Solving Technique:

This problem can be solved easily using Stack ( also check out these problems i have solved using stack uva 11192uva 483 ).  Here the only corner case is space character. Input only contains three types of character 1st bracket, 3rd bracket and a space character.

Here i have provided three solutions. All have same logic. But first one is well commented and written for easier understanding. Second one is modified version of first. For the first and second code i take input as string but in the last i take input one by one as characters.

In the second code i have checked if length is odd then i know it can’t be balanced. So i just print NO. Which is “strlen(par) & 1“. It is equivalent to “strlen(par) % 2 == 1” meaning string length is odd.

The logic for this code is whenever we find a closing bracket it must have its corresponding opening bracket before ( to its immediate left ) that. So we remove those two and keep processing rest of the input. Example,

[ [(  )]  ()]

Here we do nothing ( or, store them in string ) when we find an opening bracket. Whenever we find a closing bracket we see the character before that ( to its left ) is its opening bracket. If this condition doesn’t match then there is error in the input. So break immediately. Also when we find a closing bracket with its opening bracket we remove them and process rest of the input. Example,

[ [(  )]  ()]  /* our input */
[ [] ()]       /* we remove first occurrence of closing and its corresponding opening bracket to its left */
[ ()]          /* Process rest of the input */
[ ]
               /* Here nothing is left so it is a valid input */

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.


Critical Input:

More Critical inputs can be found in this link,

https://gist.github.com/quickgrid/72b1adc38d8752cd6905

3
([])
(([()])))
([ ()[  ]  ( )])()

Output:

Yes
No
Yes

Code Usage of Stack ( Explained ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

/**
 * Size for our stack although they said 128 but stack safety
 */
#define SIZE 256

/**
 * Our stack or array to hold parenthesis
 */
static char stack[SIZE];
/**
 * Our stack index counter
 */
int top = -1;

/**
 * Push function of out stack, We basically store the character and increase the counter
 * Checking of stack overflow is not implemented since stack size is large enough for this program
 */
void push(char c){
    stack[++top] = c;
}

/**
 * Set the element in current index to NUL and decrease the index
 * Stack underflow never occurs for this program
 */
void pop(){
    stack[top--] = '\0';
}

int main(){
    register unsigned n, i;
    unsigned char c;

    /**
     * Scan the test case count, getchar() is needed because i used gets() below which takes away my new line if getchar() is not used
     */
    scanf("%u", &n); getchar();

    while (n--){
        stack[SIZE] = {'\0'};
        /**
         * Reset the stack index, meaning we start using our stack array from the beginning
         */
        top = -1;
        /**
         * If no error then error is 0 else if there is error then error is 1
         */
        unsigned error = 0;

        /**
         * Our character array to take the input string
         */
        char *par = new char[SIZE + 1];
        gets(par);

        for (i = 0; par[i]; ++i){
            /**
             * Corner case the input can have space
             */
            if(par[i] == ' ')
                continue;

            /**
             * Push the character to stack if open bracket
             */
            if(par[i] == '[' || par[i] == '(')
                push(par[i]);

            /**
             * Pop or remove the element from top of stack if matching closing bracket found
             */
            else if(par[i] == ']' && stack[top] == '[')
                pop();
            else if(par[i] == ')' && stack[top] == '(')
                pop();

            else{
                /**
                 * If matching closing bracket not found then set error flag to 1 (ON)
                 */
                error = 1;
                /**
                 * Since we found a mistake there is no need to process rest of the string
                 */
                break;
            }
        }

        /**
         * If error flag is on or there still exist some brackets on stack then print NO
         */
        if(error || top > -1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

Taking input as string:(Faster)

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

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

static char stack[256];
static char par[256];
int top;

int main(){
    unsigned n, error;

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

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

        if(strlen(par) & 1)
            printf("No\n");
        else{
            stack[256] = {'\0'};
            top = -1;
            error = 0;

            for(unsigned i = 0; par[i]; ++i){
                if(par[i] == ' ')
                    continue;

                if(par[i] == '[' || par[i] == '(')
                    stack[++top] = par[i];
                else if((par[i] == ')' && stack[top] == '(') || (par[i] == ']' && stack[top] == '['))
                    --top;
                else{
                    error = 1;
                    break;
                }
            }

            (error || top > -1) ? printf("No\n") : printf("Yes\n");
        }
    }
    return 0;
}

Taking input one by one as characters:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 673 ( Parentheses Balance )
 */

#include<stdio.h>

#define SIZE 256

char stack[SIZE];

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

    while(n--){
        register int top = -1;
        unsigned error = 0;

        while ((ch = getchar()) != '\n'){
            if (ch == ' ') continue;
            if (ch == '[' || ch == '(') stack[++top] = ch;
            else if ((ch == ']' && stack[top] == '[') || (ch == ')' && stack[top] == '(')) --top;
            else error = 1;
        }

        if (error || top > -1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

UVA Problem 12894 – Perfect Flag Solution

UVA Problem 12894 – Perfect Flag Solution:


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

Solving Technique:

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

This problem may seem very hard if we don’t read it carefully. Also there is no need to use floating point numbers to solve this problem. Also no need to worry about negative length or widths. In case you forgot about Ratio.

Here are the key points,

1. length (L) to width ratio of 10:6,
>> length / width = 10 / 6
>> 6 * length = 10 * width
>> 3 * length = 5 * width

2. length (L) to radius ratio of 5:1,

>> length / radius = 5 / 1
>> 1 * length = 5 * radius

3. Example: If the length is 10, then width should be 6 and radius should be 2.
Set these values in our equations above and check if both sides are equal.

4. Its center (Circle’s) will be placed on the intersecting point of thee perpendicular drawn from the nine-twentieth part of the length of the flag,

>> nine-twentieth of length, ( 9 / 20 ) * length
>> Circles x distance on flag = given x position of circle - initial x position
>> 20 * (circle center x - initial x) = 9 * length

5. Horizontal line drawn through the middle of its width,

>> Circle middle y distance = given circle y - initial y
>> middle of width, (1/2) * width
>> 2 * ( given circle y - initial y ) = width

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


Input:

4
0 0 20 12 9 6 4
0 0 10 6 4 3 2
1 1 21 13 10 7 4
0 0 20 20 9 10 4

Output:

YES
NO
YES
NO

Code (with given Formula):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12894 ( Perfect Flag )
 */

#include<stdio.h>

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

    while (n--){
        int x0, y0, x1, y1, cx, cy, r;
        scanf("%u%u%u%u%u%u%u", &x0, &y0, &x1, &y1, &cx, &cy, &r);

        unsigned len = x1 - x0;
        unsigned wid = y1 - y0;

        if (( 5 * wid == 3 * len ) && ( len == 5 * r ) && 20 * ( cx - x0 ) == 9 * len && 2 * ( cy - y0 ) == wid)
            printf("YES\n");
        else
            printf("NO\n");

    }
    return 0;
}

 Another in C++ ( Without Optimization ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 12894 ( Perfect Flag )
 */

#include<iostream>

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

    register unsigned n;
    unsigned int x0, y0, x1, y1, cx, cy, r;

    std::cin >> n;
    while (n--){
        std::cin >> x0 >> y0 >> x1 >> y1 >> cx >> cy >> r;
        unsigned len = x1 - x0, wid = y1 - y0;
        (( 5*wid == 3*len ) && ( len == 5*r ) && (20*( cx - x0 ) == 9*len) && ((( cy-y0 ) << 1) == wid) ) ? std::cout << "YES\n" : std::cout << "NO\n";
    }

    return 0;
}

 Code (Strength Reduction Optimization based on the first code):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 * Problem UVA 12894 ( Perfect Flag )
 */
#include<stdio.h>

int main(){
    unsigned n, x0, y0, cx, cy, r;
    scanf("%u", &n);

    while (n--){
        scanf("%u%u%*u%*u%u%u%u", &x0, &y0, &cx, &cy, &r);

        if (2 * ( cx - x0 ) + ( y0 - cy ) == 3 * r)
            printf("YES\n");
        else
            printf("NO\n");

    }
    return 0;
}