REC09B - Editorial

PROBLEM LINK:

Johnny Bravo

Author: Rishabh Sethi
Tester: Abhishek Chaudhary
Editorialist: Rishabh Sethi

DIFFICULTY:

EASY

PREREQUISITES:

Math

PROBLEM:

Given two integers A and B, we have to find two integers C and D such that value of (C^{2}+D^{2}) is greater than value of (A^{2}+B^{2}) and the multiplication of (A^{2}+B^{2}) and (C^{2}+D^{2}) results into sum of square of two integers X and Y. Furthermore, the value of (X^{2}+Y^{2}) should be minimum.

QUICK EXPLANATION:

Firstly we need to find all the integer value of C and D such that (A^{2}+B^{2})*(C^{2}+D^{2}) results into sum of squares of two integers. It can be easily proved that whatever be the value of C and D, the multiplication will always result into sum of sqaures of two integers. With this proved, we can find C and D such that the value of C^{2}+D^{2} is just greater than A^{2}+B^{2}. Since the values of C and D are less than 2000, we can easily use brute force to find the values.

EXPLANATION:

Firstly we need to prove that whatever be the value of C and D, (A^{2}+B^{2})*(C^{2}+D^{2}) results into sum of squares of integers.
Let P and Q be two complex numbers.
P = a + ib
Q = c + id
Since multiplication of 2 complex number results into yet another complex number,thus on multiplying these two numbers we have
X = P*Q
x + iy = (a + ib)*(p + iq)
Now, taking magitude and sqauring on both sides, we have
(x^{2} + y^{2}) = (a^{2} +b^{2})*(p^{2} + q^{2})

Thus we can see that the above equation is independent of values of a,b,p and q.
Now, on iterating over all possible values of C and D, we find the values of C^{2} + D^{2} such that it is just greater than A^{2} + B^{2}.

For all C from 1 to 2000
 For all D from C+1 to 2000
 	If C^2 + D^2 > A^2 + B^2 and C^2 + D^2<=Minimum value
 		Minimum Value = C^2 + D^2
 		If C^2 + D^2 == Minimum Value and C + D < Minimum Sum
 			Final C, D = C,D
 		Elif C^2 + D^2<Minimum Value
 			Minimum Value = C^2 + D^2
 			Minimum Sum = C+D
 			Final C, D = C, D

SOLUTIONS:

Setter's Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
	int t;
	cin>>t;
	while(t--){
		int a, b;
		cin>>a>>b;
		int p = a*a + b*b;
		int mn1 = 10000000, mn2 = 10000000;
		int c = 2000, d = 2000;
		for(int i=1; i<=2000; i++){
			for(int j=i; j<=2000; j++){
				int q = i*i + j*j;
				if(q>p){
					if(q<=mn1){
						if(q==mn1){
							if(i+j<mn2){
								mn2 = i + j;
								c = i;
								d = j;
							}
						}
						else{
							mn1 = q;
							mn2 = i + j;
							c = i;
							d = j;
						}
					}
				}
			}
		}
		cout<<c<<" "<<d<<endl;
	}
	return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long  long ll;

int main()
{
	ios_base::sync_with_stdio(false);
	 cin.tie(NULL);
	
	ll t;
	cin>>t;
	while(t--)
	{
		ll x,y,mn=1e17,c=1e17,d=1e17;
		cin>>x>>y;
		ll sm1=(x*x + y*y);
		for(ll i=1;i<=2000;i++)
		{
			for(ll j=i;j<=2000;j++)
			{
				if((i*i + j*j)>sm1)
				{
					if((i*i + j*j)*sm1<=mn)
					{
						if((i*i + j*j)*sm1==mn)
						{
							if(i+j<c+d )
							{
								c=i;
								d=j;
							}
							assert(i+j==c+d);
						}
						else
						{
							mn=(i*i + j*j)*sm1;
							c=i;
							d=j;
						}
					}
				}
			}
		}
		cout<<c<<" "<<d<<"\n";
	}
}
2 Likes

The following is my 15 lines of code C++14 solution of this problem using binary search.

https://www.codechef.com/viewsolution/27908802

1 Like

Yeah, I later on realized that the question can be done with binary search. One for loop for C and inside the For loop binary search D from 1 to 2000. Had the constraint been of the around 10^5, it would have been fun.

1 Like