EXISTENCE - Editorial

editorial
,
1

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')
2

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.

3

Oops, thanks for pointing out. Some of those 2's were supposed to be 4's, fixed now.

4

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;

}

5

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.