BIGDIF - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given N and K, find any two integers a, b such that:

  • 1 \leq a, b \leq N
  • |a-b| \geq K
  • |\gcd(a, b) - \text{lcm}(a, b)| \geq 2K

EXPLANATION:

Let’s look at the |a-b| condition first.
If K \geq N, it’s impossible to find two integers in [1, N] with a difference of at least K, so immediately we know that no answer exists.

What about when K \lt N?
Note that if K is small we have more choice, while if K is large we’re more restricted in which pairs of elements we can choose.
So, it’s natural to look at the largest values of K and see how exactly we’re restricted.

Suppose K = N-1.
Then, the only possible pair is a = 1, b = N (or a = N, b = 1).
Here, we have \gcd(1, N) = 1 and \text{lcm}(1, N) = N, so their difference is N-1, which is certainly not \geq 2K in this case.
So, if K = N-1 no solution exists.

Next, let’s look at K = N-2.
The only candidate pairs now are (1, N-1), (1, N), (2, N).
(1, N-1) and (1, N) both still don’t work, since they’ll have a GCD of 1 and an LCM of N-1 or N respectively.
As for (2, N):

  • If N is even, \gcd(2, N) = 2 and \text{lcm}(2, N) = N so this isn’t a valid pair either.
  • If N is odd, \gcd(2, N) = 1 and \text{lcm}(2, N) = 2N, and 2N - 1 \gt 2\cdot (N-2) so this pair is in fact valid.

So, if K = N-2, only (2, N) needs to be checked for validity (and it will be valid if and only if N is odd).

Great, what about K = N-3?
Here, note that if N is odd we can just use the pair (2, N) as above.
If N is even, we can instead use (2, N-1). This works for the same reason: when N-1 is odd, the difference between gcd and lcm is 2\cdot (N-1) - 1 = 2N - 2, which is certainly greater than 2K = 2\cdot (N-3).
So, if K = N-3, a solution always exists: either (2, N) or (2, N-1) depending on the parity of N.

As for K \lt N-3, note that we can just use the solution for K = N-3 since we only wanted lower bounds on the difference, and not exact equality.

While we derived the solution using casework, there’s a very simple implementation that doesn’t need to check every case.
Notice from above that if an answer exists, it’s either (2, N) or (2, N-1). So, simply check both pairs, and if one of them works report it, otherwise no solution exists.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    
    def check(x):
        import math
        return x > 0 and abs(x-2) >= k and abs(math.gcd(x, 2) - math.lcm(x, 2)) >= 2*k
    
    # Check (2, n) and (2, n-1)
    if check(n): print(2, n)
    elif check(n-1): print(2, n-1)
    else: print(-1, -1) # If both fail, no solution exists
2

i may be naive for asking this but during the contest I felt that if I iterate from n-k to 1 while taking the 2nd value as n it will be sufficient, but it does not seem to work like that can anybody help me to know why?

here is the code

include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(int a, int b) {
while (b!= 0) {
int temp = b;
b =a % b;
a =temp;
}
return a;
}

int lcm(int a, int b) {
return (a/ gcd(a, b)) * b;
}

int main() {
int t;
cin >> t;
while (t–) {
int n, k;
cin >> n >> k;

    bool possible = false;
    int a = n;
    
    if(k>=n) possible = false;
    
    else{
    for (int i = n - k; i >= 1; i--) {
        ll value= abs(gcd(a, i) - lcm(a, i));
        if (value >=2 * k) {
            possible =true;
            cout << a << " " << i << endl;
            break;
        }
    }
    }

    if (!possible) cout << -1 << " " << -1 << endl;
}

return 0;

}

3

This is not feasible as it is not considering the case of N-1 and 2 when N is even.
You can understand through this :
for n = 30 and k = 27 :
(3,30), (2,30) and (1,30) are not valid but (2,29) is.