LCM Challenge - 235 A

https://codeforces.com/problemset/problem/235/A

Simplified Problem Statement

Given n, take 3 numbers a, b, c <= n. Maximize LCM(a, b, c).

Constraint

n <= 10^6.

Analysis

We want to minimize common divisor among the number, for LCM(a, b, c) = a*b*c / GCD(a, b, c). Is it possible to have GCD(a, b, c) to become 1? If we have 2k-1, 2k, 2k+1, it is clear that the GCD will be 1. However, the number n might be even, hence 2k+1, which is the max value is not equal to n.

Looking at the test cases. For n = 9 and 7, the solution seems to be consistent with our method. Which are 504 and 210 respectively.

Let’s see for even valued n. The number 2k-2, 2k-1, 2k should have GCD of 2. Thus for big enough n, 2k-1, 2k, 2k+1 seems to be the best solution.

We need to consider the fact that the three numbers a, b, and c does not need to be different.

Uh oh! The formula LCM(a, b, c) = a*b*c / GCD(a, b, c) is completely wrong. As an example, LCM(7, 7, 6) is not 294 but rather 42. For sure, because it seems to be easy for a C problem if that’s so. Moving on, we can actually use lcm(a,b,c) = lcm(a, lcm(b,c)), which by analyzing GCD will generate us lcm(a,b,c) = a*lcm(b, c)/GCD(a, lcm(b,c)) = a*b*c/GCD(b,c)*GCD(a, b*c/GCD(b,c)). Bleh.. expanding the equation doesn’t seem to be very helpful.

So what now? If we go back to the initial hypothesis that 2k-1, 2k, 2k+1 will give us the best result, maybe we can try to prove directly from there?

We can try from smaller n

• n = 1 -> 1,1,1 = 1
• n = 2 -> 2,2,2 = 2
• n = 3 -> 1,2,3 = 6
• n = 4 -> 2, 3, 4 = 12 (better than 1, 2, 3 = 6)
• n = 5 -> 3, 4, 5 = 60
• n = 6 -> 4, 5, 6 = 60 (equally good as 3, 4, 5 = 60) (I believe that as n grows, the solution with more “odds” will perform better and this is the tipping point)
• n = 7 -> 5, 6, 7 = 210
• n = 8 -> 6, 7, 8 = 168 (now it’s less than 5, 6, 7 = 210).

I think we can try to submit this. As i’m pretty confident.

Implementation

The special cases that doesn’t follow the patterns are n = 1, 2, 3, 4. So we can hardcode this.

int main() {
        setIO();
        ll n; re(n);
        if(n == 1) ps(1);
        else if(n == 2) ps(2);
        else if(n == 3) ps(6);
        else if(n == 4) ps(12);
        else if(n & 1) ps((n-2)*(n-1)*n); // n is odd
        else ps((n-3)*(n-2)*(n-1));
}

Uh oh! This result on WA on test 33. This might be resulted because of not enough bit space I guess? I don’t think it’s a fundamental error on the solution but rather an edge case. Before looking at the test result and peeking at the issue, let us try to test some first. Strangely for n = 1000000 it still work and produce 999994000010999994. So there might be an edge case? Does anything happen that might cause 2k-3, 2k-1, 2k be a better solution (for even n). Let us see, for n=8, this pattern will generate 5, 7, 8 = 280, which is actually bigger than 210! Oh lol. But I need to be carefull since if n is divisible by 3, like in the case of 6, we will have duplicate factor of 3. I think we can simply try to get the max of both. Uh oh! Max wouldn’t work. Since we need to take into account the factor of 3 thing. I guess we can try if n is divisible by 3, we use the old pattern, otherwise use the new pattern.

int main() {
        setIO();
        ll n; re(n);
        if(n == 1) ps(1);
        else if(n == 2) ps(2);
        else if(n == 3) ps(6);
        else if(n == 4) ps(12);
        else if(n & 1) ps((n-2)*(n-1)*n); // n is odd
        else if(n % 3 == 0) ps((n-3)*(n-2)*(n-1)); // n is divisible by 3
        else ps(n*(n-1)*(n-3));
}

Accepted!