TWONUMBERS - Editorial

PROBLEM LINK:

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

Setter: Lavish Gupta
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

1546

PREREQUISITES:

GCD, LCM

PROBLEM:

Given two positive integers a and b, we define f(a,b)=lcm(a,b)−gcd(a,b), where lcm denotes the lowest common multiple and gcd denotes the greatest common divisor.

Chef has a positive integer N. He wonders, what is the maximum value of f(a,b) over all pairs (a,b) such that a and b are positive integers, and a+b=N?

EXPLANATION:

Quick explanation: We find the pair a < b such that gcd(a, b) = 1 and b - a is as small as possible. In details:

  • If N is odd, a = \lfloor N / 2 \rfloor and b = \lceil N / 2 \rceil.
  • If N is divisible by 4, a = N / 2 - 1 and b = N / 2 + 1.
  • If N \equiv 2 \pmod{4}, a = N / 2 - 2 and b = N / 2 + 2.

There is one small edge case to this: when N = 2, a = b = 1.

To see how this works, note that since lcm(a,b) \cdot gcd(a,b) = ab, or lcm(a,b) = \frac{ab}{gcd(a,b)}, intuitively, we have two goals simultaneously when trying to maximize f(a, b):

  • Minimizing gcd(a, b). This can be done by making gcd(a, b) = 1.
  • Maximize ab. This can be done by making a and b as close to each other as possible.

Hence we have the aforementioned algorithm, where we can easily prove that in every case, a and b are the closest pair of numbers such that gcd(a, b) = 1. Proving that this strategy indeed maximizes f(a, b) follows naturally from that: we can prove that any pair of (a, b) closer than the proposed pair gives a smaller f(a, b), and any pair (a, b) further than the proposed pair has product ab less than the proposed f(a, b), and hence its f(a, b) must be less than the proposed f(a, b).

TIME COMPLEXITY:

Time complexity is O(1) for each test case.

SOLUTION:

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    int n=readInt(2,1000000000,'\n');
    if(n==2)
    {
        cout<<0<<'\n';
        return;
    }
    if(n%2==1)
    {
        long long x=n/2,y=x+1;
        cout<<(x*y-1)<<'\n';
    }
    else
    {
        long long x=n/2,y=n/2;
        x--,y++;
        if(x%2==0)
            x--,y++;
        cout<<(x*y-1)<<'\n';
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,100000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e6+1;
ll a[N];
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;
	while(t--){
		ll n;cin >> n;
		if(n==2) cout << "0\n";
		else if(n%2==1) cout << (n-1)/2*(n+1)/2-1 << '\n';
		else if(n%4==0) cout << (n/2-1)*(n/2+1)-1 << '\n';
		else cout << (n/2-2)*(n/2+2)-1 << '\n';
	}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        if (n == 2) {
            cout << "0\n";
        } else if (n % 2 == 1) {
            cout << 1LL * (n / 2) * (n / 2 + 1) - 1 << '\n';
        } else if (n % 4 == 0) {
            cout << 1LL * (n / 2 - 1) * (n / 2 + 1) - 1 << '\n';
        } else {
            cout << 1LL * (n / 2 - 2) * (n / 2 + 2) - 1 << '\n';
        }
    }
}
2 Likes

One could have just iterated x = n / 2 to 0 until we find gcd(x, y) != 1, here y = (n - x) everytime, basically checking co-primes, co primes have lcm maximum and gcd always 1. Making f(a,b) maximum. Here’s my solution :

import java.util.*;
import java.io.*;

class CP {
    static Scanner s = new Scanner(System.in);
    static class pair{
        long key;
        int count;
        pair(long key , int count){
            this.count = count;
            this.key = key;
        }
    }

    static class sort implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            if(Math.abs(o1) > Math.abs(o2)){
                return 1;
            }else if(Math.abs(o1) < Math.abs(o2))return -1;
            return 0;
        }
    }
    public static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(String s) throws FileNotFoundException {
            br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }

    static private long gcd(long a , long b){
        if(b == 0)return a;
        return gcd(b , a % b);
    }
    static private void printArrayList(ArrayList<Object> al){
        String st = "";
        for(Object i : al){
            st += i + " ";
        }
        System.out.println(st);
    }
    static private long digitSum(long n){
        long sum = 0;
        while(n != 0){
            sum += n%10;
            n = n/10;
        }
        return sum;
    }

    static boolean checkPrime(int x){
        for(int i = 2; i <= Math.sqrt(x);i++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }
    static boolean checkPallindrome(String st){
        int i = 0, j = st.length() - 1;
        while (i <= j){
            if(st.charAt(i) != st.charAt(j))return false;
            i++;
            j--;
        }
        return true;
    }
    static boolean checkPowerOfTwo(int n){
        final double v = Math.log(n) / Math.log(2);
        return (int)(Math.ceil(v))
                == (int)(Math.floor(v));
    }

    static ArrayList<Long> insert(int n) throws IOException {

        ArrayList<Long> al = new ArrayList<>();
        for(int i =0 ; i < n; i++){
            al.add(s.nextLong());
        }
        return al;
    }

    static int debugger = 1;
    static void debug(){
        System.out.println("Reached " + debugger++);
    }

    static String reverse(String st){
        String ans = "";
        for(int i = st.length() - 1; i >= 0; i--)ans += st.charAt(i);
        return ans;
    }

    static void dfs(int root , Map<Integer , ArrayList<Integer>> children){
        if(children.size() == 0)return;


        for(int i = 0; i < children.size(); i++){

            // do operations
        }

    }





    /*
    ArrayList<Integer> al = new ArrayList<>();
            Map<Integer , ArrayList<Integer>> children = new HashMap<>();
           for(int i = 0; i < n; i++){
               al.add(s.nextInt());
               children.put(i + 1 , new ArrayList<>());
           }

           for(int i = 0; i < m; i++){
                int x = s.nextInt();
                int y = s.nextInt();
                ArrayList<Integer> temp = children.get(x);
                temp.add(y);
                children.put(x , temp);
           }

     */

    //funtions that you have ramakant

    // a sort (comparator)
    // gcd
    // digitSum
    // checkPrime (sqrt method)
    // checkPallindrome (two pointer)
    // checkPowerOfTwo (log method)
    // reverse a string
    // dfs of graph / tree
    // insert in arrayList
    // print ArrayList



    public static void main(String[] args) {
        try {


            StringBuffer sb = new StringBuffer();
            int t = s.nextInt();
            while (t-- > 0){
                long n = s.nextLong();
                long ans = 0;
                long x = 0 , y = 0;
                if(n == 1){sb.append("0\n"); continue;}
               
                    x = n / 2;
                    y = n - x;
                   while(x > 0 && gcd(x , y) != 1){
                       x--;
                       y = n - x;
                   }
                   ans = Math.max((x * y) - 1 , (n - 2));
                   
                    
                
               
                sb.append(ans +"\n");
            }








            System.out.println(sb);
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}

Also, was said n <= 10^9, then it must have been strictly. I faced 4 wrong submissions just because I took n as int and not long. As far as I know, if 10^18 then take long otherwise if 10^9, take int. Costed me -100 rank.

What is the idea behind N is divisible by 4 ? Couldn’t get it.

basically idea behind that is :
we have to tackle the parity of n differently!
if(n is odd){
then a=n/2;
b=n/2+1}

else {
//n is even

on dividing even no. by 2 we get two possibilities
either the answer would be even no. or odd !
and we have to tackle both these cases differently!

for even :
a will be n/2+1;
for odd
a will be n/2+2;

and b=n-a;

}
(for better understanding try to solve the question by taking n as 10)!

my solution : Solution: 66205011 | CodeChef

2 Likes

Got it thankyou :slightly_smiling_face:

How do we know that gcd of ceil(N/2) and floor(N/2) will always be 1 when N is odd.