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 where and three equations,

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,

then it can also be written as,

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,

from equation (ii),

This can be rewritten as,

from equation (i),

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

This can be rewritten as,

similarly from (iii) and (iv),

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

Now from (v) and (vi),

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,

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

from equation (i),

but A can be at most 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,

---

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,

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,

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,

where,

and,

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