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


## 3 thoughts on “UVA Problem 11565 – Simple Equations Solution”

1. Could you please explain how you got the loop ranges -58, 58 and -22,22 again? That seems to be the only part confusing me, but it is a very clever optimization

Like

2. This is a very wrong post the solution shared is also wrong.
I can provide test cases where this will fail. Here is the test case
1
9 4331 8763

for values of A=9 B=4331 and C=8763
It will give no solution but there is solution to this test case
that is x=-61 y=-1 and z=71

The optimizations of running the first loop from -58 to 58 and second loop from -22 to 22 is wrong.

Liked by 1 person