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:
\text{gcnd}(X, Y) is defined to be the largest integer that’s \le X or \le Y, and doesn’t divide both X and Y.
Given an array A with elements in [5, 10^7], compute the maximum value of \text{gcnd}(A_i, A_j) across all i \lt j.
EXPLANATION:
Suppose X \le Y. Let’s analyze what \text{gcnd}(X, Y) evaluates to be.
Clearly, the value must be \le Y.
However, it’s not possible to choose Y itself - after all, Y divides Y, but \text{gcnd}(X, Y) must not divide Y.
The next best option is to choose Y-1.
This is promising, because Y-1 will never divide Y as long as Y \gt 2 (and our array has elements \ge 5, so this condition is automatically satisfied).
We now have to think about when Y-1 divides X.
It can be seen that:
- If X = Y, we know that Y-1 can’t divide X.
- If X \lt Y-1, again we know that Y-1 can’t divide X (since a divisor of a number can’t be larger than it).
- Because of our assumption of X \le Y, the only remaining case is X = Y-1.
In this case, unfortunately Y-1 does divide X, so the answer can’t be Y-1.
From the above analysis, we’ve seen that \text{gcnd}(X, Y) = Y-1 almost always.
The only remaining part is the case of X = Y-1, i.e. computing \text{gcnd}(Y-1, Y).
For \text{gcnd}(Y-1, Y), we’ve already seen that the two best options of Y and Y-1 don’t work.
That means our next best option is Y-2.
And indeed, it can be seen that Y-2 does work - after all,
- Y-2 doesn’t divide Y-1.
- Y-2 also doesn’t divide Y as long as Y \ge 5.
This is because any strictly smaller divisor of Y cannot be larger than \frac{Y}{2}, and when Y \ge 5 we have Y-2 \gt \frac{Y}{2}.
Since all the array elements are \ge 5, we thus simply have \text{gcnd}(Y-1, Y) = Y-2.
We now know how to compute \text{gcnd}(X, Y) in constant time, given X and Y.
However, applying this to each pair (i, j) is still too slow, so we need to be smarter.
Let M = \max(A) denote the maximum element of A.
Observe that the answer is surely at least M-2, since we can just take the \text{gcnd} of M with any other element and it’ll be either M-1 or M-2.
Further, if we choose two elements that are both strictly smaller than M, then their \text{gcnd} will surely be at most M-2 anyway (because if X, Y \le M-1 then \text{gcnd}(X, Y) \le \max(X, Y)-1 \le M-2).
This means it’s optimal to always have M as one of the elements of the chosen pair.
As for the other element, there are N-1 choices - we can just try all of them and take the best outcome.
Alternately, you can do a bit of casework, and see that the answer is M-2 if the array has one copy of M and (N-1) copies of (M-1), and the answer is M-1 in all other cases.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
def gcnd(x, y): # x <= y
if x+1 == y: return y-2
else: return y-1
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
m = max(a)
skip = 0
ans = 0
for i in range(n):
if a[i] == m and skip == 0: skip = 1
else: ans = max(ans, gcnd(a[i], m))
print(ans)