Three Days Grace (Codeforces 1699E)
Tags: Greedy, number theory

Ibti was thinking about a good title for this problem that would fit the round theme (numerus ternarium). He immediately thought about the third derivative, but that was pretty lame so he decided to include the best band in the world — Three Days Grace.You are given a multiset $$$A$$$ with initial size $$$n$$$, whose elements are integers between $$$1$$$ and $$$m$$$. In one operation, do the following:   select a value $$$x$$$ from the multiset $$$A$$$, then  select two integers $$$p$$$ and $$$q$$$ such that $$$p, q > 1$$$ and $$$p \cdot q = x$$$. Insert $$$p$$$ and $$$q$$$ to $$$A$$$, delete $$$x$$$ from $$$A$$$. Note that the size of the multiset $$$A$$$ increases by $$$1$$$ after each operation. We define the balance of the multiset $$$A$$$ as $$$\max(a_i) - \min(a_i)$$$. Find the minimum possible balance after performing any number (possible zero) of operations.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.The second line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 5 \cdot 10^6$$$) — the initial size of the multiset, and the maximum value of an element.The third line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the elements in the initial multiset.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$ and the sum of $$$m$$$ across all test cases does not exceed $$$5 \cdot 10^6$$$.

Output: For each test case, print a single integer — the minimum possible balance.

Note: In the first test case, we can apply the operation on each of the $$$4$$$s with $$$(p,q) = (2,2)$$$ and make the multiset $$$\{2,2,2,2,2,2,2\}$$$ with balance $$$\max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0$$$. It is obvious we cannot make this balance less than $$$0$$$.In the second test case, we can apply an operation on $$$12$$$ with $$$(p,q) = (3,4)$$$. After this our multiset will be $$$\{3,4,2,3\}$$$. We can make one more operation on $$$4$$$ with $$$(p,q) = (2,2)$$$, making the multiset $$$\{3,2,2,2,3\}$$$ with balance equal to $$$1$$$.In the third test case, we can apply an operation on $$$35$$$ with $$$(p,q) = (5,7)$$$. The final multiset is $$$\{6,5,7\}$$$ and has a balance equal to $$$7-5 = 2$$$.In the forth test case, we cannot apply any operation, so the balance is $$$5 - 1 = 4$$$.

Sample Inputs:
4
5 10
2 4 2 4 2
3 50
12 2 3
2 40
6 35
2 5
1 5

Sample Outputs:
0
1
2
4

Solution (Python):
rr = input
rri = lambda : int(rr())
rrm = lambda : list(map(int, rr().split()))
from itertools import combinations
from collections import Counter, defaultdict

def solve(n, m, A):
    (mn, mx) = (min(A), max(A))
    ans = mx - mn
    dp = []
    freq = [0] * (mx + 1)
    appear = [0] * (mx + 1)
    high = mx
    for x in A:
        freq[x] = 1
        appear[x] = 1
    for i in range(mx + 1):
        dp.append(i)
    cur = mx
    while cur >= 1:
        j = cur
        while j * cur <= mx:
            if appear[j * cur]:
                freq[dp[j * cur]] -= 1
            dp[j * cur] = min(dp[j], dp[j * cur])
            if appear[j * cur]:
                freq[dp[j * cur]] += 1
            j += 1
        while freq[high] == 0:
            high -= 1
        if cur <= mn:
            ans = min(ans, high - cur)
        cur -= 1
    return ans
T = rri()
for i in range(1, T + 1):
    (n, m) = rrm()
    A = rrm()
    ans = solve(n, m, A)
    print(ans)

Solution (Python):
def solve():
    (n, m) = map(int, input().split())
    arr = list(map(int, input().split()))
    maxv_toggle = [0] * (m + 1)
    check = [0] * (m + 1)
    minv = m
    maxv = 1
    for num in arr:
        check[num] = 1
        maxv_toggle[num] = 1
        minv = min(minv, num)
        maxv = max(maxv, num)
    dp = [*range(m + 1)]
    ptr = maxv
    ans = maxv - minv
    for i in range(m, 0, -1):
        for j in range(i * i, m + 1, i):
            if check[j]:
                maxv_toggle[dp[j]] -= 1
            dp[j] = min(dp[j], dp[j // i])
            if check[j]:
                maxv_toggle[dp[j]] += 1
        while maxv_toggle[ptr] == 0:
            ptr -= 1
        if i <= minv:
            ans = min(ans, ptr - i)
    print(ans)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
import sys
import collections
import os

def maximum(a, b):
    return max(a, b)

def minimum(a, b):
    return min(a, b)

def leftshift(a):
    return a << 1
r = [0] * int(600000.0 + 5)
f = [0] * int(5000000.0 + 5)
c = [0] * int(5000000.0 + 5)
fl = [0] * int(5000000.0 + 5)
T = int(input())
for i in range(T):
    (a, b) = map(int, input().split())
    L = list(map(int, input().split()))
    ma = b + 1
    s = 0
    anuvab = sys.maxsize
    mas = 0
    anuvab1 = sys.maxsize
    i = 1
    while i <= b:
        if i >= min(3000, b):
            f[i] = i
        else:
            f[i] = 1 + b
        fl[i] = 0
        i = i + 1
    z = 0
    while a:
        fl[L[z]] = 1
        mas = maximum(mas, L[z])
        anuvab1 = minimum(anuvab1, L[z])
        a = a - 1
        z = z + 1
    anuvab = mas - anuvab1
    i = 1
    while i <= b:
        s += fl[i]
        c[f[i]] = c[f[i]] + fl[i]
        i = i + 1
    i = minimum(3000, b)
    while i:
        c[f[i]] = c[f[i]] - fl[i]
        f[i] = i
        c[i] = c[i] + fl[i]
        j = leftshift(i)
        while j <= b:
            c[f[j]] = c[f[j]] - fl[j]
            f[j] = minimum(f[j], maximum(f[j // i], i))
            c[f[j]] += fl[j]
            j = j + i
        while not c[ma]:
            ma -= 1
        if ma <= b:
            anuvab = minimum(anuvab, ma - i)
        i = i - 1
    print(anuvab)
    i = 1
    while i <= b:
        c[f[i]] = c[f[i]] - fl[i]
        i = i + 1