PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abhi_inav
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
928
PREREQUISITES:
None
PROBLEM:
Given X and Y, check whether
X^4 +4Y^2 = 4X^2Y
is true.
EXPLANATION:
X and Y are pretty large: so large that you might not be able to compute and store X^4 or 2Y^2 accurately in some languages (mainly, C/C++).
Instead, notice that
\begin{align*}
& \ \ \ \ \ \ \ \ \ \ \ \ X^4 + 4Y^2 = 4X^2Y \\
& \iff X^4 + 4Y^2 - 4X^2Y = 0 \\
& \iff (X^2 - 2Y)^2 = 0 \\
& \iff X^2 = 2Y
\end{align*}
That is, the given equation is true if and only if X^2 = 2Y, so it suffices to check for that.
Since X \leq 10^9 and Y \leq 10^{18}, this check does fit within the limts for long long
and so can be done to solve the problem!
Of course, if you use a language like Python that has support for larger numbers, you can directly check if the initial equation is true or not.
TIME COMPLEXITY
\mathcal{O}(1) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x, y = map(int, input().split())
print('Yes' if x**2 == 2*y else 'No')
Correct the equations mentioned in editorial. Put parenthesis around 2Y, making (2Y)^2 and on right hand side of equation as well, make it 2(X^2)*2Y.
Oops, thanks for pointing out. Some of those 2's were supposed to be 4's, fixed now.
Why is the following code not failing on test cases where ‘X’ and ‘Y’ obtain a very large value such that X^4 or Y^2 become out of the range of long long int?
…
#include
#include <bits/stdc++.h>
#include
#define ll long long int
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
ll X,Y;
cin>>X>>Y;
ll LHS;
ll RHS;
LHS=(X*X*X*X)+4*(Y*Y);
RHS=4*X*X*Y;
if(LHS==RHS){
cout<<"YES"<<"\n";
}
else{
cout<<"NO"<<"\n";
}
}
return 0;
}
It’s in fact not so simple to create a testcase that fails that implementation: in this specific case, even if overflow occurs the answer might still be right.
In particular if the answer is Yes
then that code will always correctly output Yes
, because both sides will overflow to the same value and hence be equal when compared.
If the answer is No
then there’s a high chance both sides overflow to different numbers, so it’ll probably be correct on most random tests too.
One example of a testcase that fails your code is
1
146544 153728
which unfortunately isn’t in the actual testdata.