NOTUNIT-Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Sandeep V
Tester: Istvan Nagy, Aryan
Editorialist: Vijay

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Dazzler has a task for you.

Given two positive integers A and B, find two positive integers i and j such that:

  • gcd(i,j) \gt 1;
  • A \leq i \lt j \leq B;
  • The value (i + j) is minimum possible.

If there are multiple solutions, you may print any of them. If no such pair exists, print -1.

EXPLANATION:

Observation : We can show that for intervals of length greater than or equal to 4, we can always find two numbers such that their gcd is greater than 1.

Suppose we have an interval of length greater than or equal to 4 . Now,if the interval starts from x , we can write the first 4 numbers as (x,x+1,x+2,x+3). Now, if x is even, then we have (x, x+2) as even, otherwise we have (x+1, x+3) as even. Thus, we have a valid pair of (A, B) with sum at most 2 \cdot x+4. Now, if any of A or B is greater than or equal to x+4, we will have the sum greater than or equal to 2 \cdot x + 4. Thus, this will not further improve the answer. So, we can simply ignore and truncate the interval up to length 4.
Now we can just brute force on this truncated interval which can have at most length 4 to obtain the most optimal pair.

TIME COMPLEXITY:

O(log(min(a,b)) for each test case.

SOLUTION:

Editorialist's Solution 
#include <bits/stdc++.h>

using namespace std;

#define nline '\n'
void solve()
{

int a,b;
cin>>a>>b;
int sum=INT_MAX;
pair<int,int>ans={-1,-1};
for(int i=a;i<=min(b,a+3);i++){
      for(int j=i+1;j<=min(b,a+3);j++){
           if(__gcd(i,j)>1){
                if(i+j<sum){
                     sum=i+j;
                     ans={i,j};
                }
           }
      }
}

if(ans.first==-1)cout<<-1<<endl;
else cout<<ans.first<<" "<<ans.second<<endl;

}



int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    cin >> t;

    while (t--)
    {
        solve();
    }
}
2 Likes
2

Hi, ,
Why we are doing a+3 ?, according to statement written above is that if a is even that we do a, a+2 otherwise we do a+1, a+3 but here a+3 has written.

3

I wonder why I was getting TLE from this go solution! Maybe my input reading is messed up somewhere, pretty new to CP.

Thanks for the explanation, might try once again.

Edit# If someone is golang expert, please do enlighten me :slight_smile:

4

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
long long int a,b,r,w;
cin>>a>>b;
if(a==1){
cout<<-1<<endl;
}
else{
if(a%2==0){
if((b-a)<2){
cout<<-1<<endl;
}
else{
r=a+2;
cout<<a<<" “<<r<<endl;
}
}
else{
if((b-a)<3){
cout<<”-1"<<endl;
}
else{
r=a+1;
w=a+3;
if(a%3==0){
cout<<a<<" “<<w<<endl;
}
else
cout<<r<<” "<<w<<endl;
}
}
}
}
return 0;
}

Please can anyone tell me that why this code isn’t working??