Quiz Master (Codeforces 1777C)
Tags: Math, two pointers

A school has to decide on its team for an international quiz. There are $$$n$$$ students in the school. We can describe the students using an array $$$a$$$ where $$$a_i$$$ is the smartness of the $$$i$$$-th ($$$1 \le i \le n$$$) student. There are $$$m$$$ topics $$$1, 2, 3, \ldots, m$$$ from which the quiz questions will be formed. The $$$i$$$-th student is considered proficient in a topic $$$T$$$ if $$$(a_i \bmod T) = 0$$$. Otherwise, he is a rookie in that topic. We say that a team of students is collectively proficient in all the topics if for every topic there is a member of the team proficient in this topic.Find a team that is collectively proficient in all the topics such that the maximum difference between the smartness of any two students in that team is minimized. Output this difference.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print the answer on a new line. If there is no solution, output $$$-1$$$.

Note: In the first test case, we have participants with smartnesses $$$3$$$ and $$$7$$$, and $$$m = 4$$$. Thus, there is no student with smartness divisible by $$$2$$$. Since $$$2 \leq m$$$, there is no way to choose a team.In the second test case, we can select the participant with smartness $$$2$$$ to be the only one on the team. This way the team will be collectively proficient in both topics $$$1$$$ and $$$2$$$.In the third test case, consider the team with participants of smartnesses $$$4, 5, 6, 7$$$. This way the team will be collectively proficient in all topics $$$1, 2, \ldots, 7$$$.

Sample Inputs:
3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7

Sample Outputs:
-1
0
3

Solution (Python):
from sys import stdin
MAX = 100005
factors = [[] for _ in range(MAX)]
for i in range(1, MAX):
    for j in range(i, MAX, i):
        factors[j].append(i)

def update(x, m, freq, active):
    for f in factors[x]:
        if f > m:
            break
        if freq[f] == 0:
            active += 1
        freq[f] += 1
    return active

def remove(x, m, freq, active):
    for f in factors[x]:
        if f > m:
            break
        if freq[f] == 1:
            active -= 1
        freq[f] -= 1
    return active
T = int(input())
for t in range(T):
    (n, m) = map(int, stdin.readline().split())
    a = sorted(set(map(int, stdin.readline().strip().split())))
    ln = len(a)
    freq = [0] * (m + 1)
    (l, r) = (0, 0)
    active = 0
    active = update(a[l], m, freq, active)
    best = MAX
    while r < ln and l < ln:
        if active < m:
            if r < ln - 1:
                r += 1
                active = update(a[r], m, freq, active)
            else:
                break
        else:
            if l <= r:
                best = min(best, a[r] - a[l])
            active = remove(a[l], m, freq, active)
            l += 1
            if active == m and l <= r:
                best = min(best, a[r] - a[l])
    print(best if best < MAX else -1)

Solution (Python):
N = int(input())
from collections import defaultdict
M = defaultdict(lambda : [])
for i in range(1, int(100000.0) + 1):
    for j in range(i, int(100000.0) + 1, i):
        M[j].append(i)

def solve():
    (n, m) = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    A.sort()
    freq = {}
    (l, i) = (0, 0)
    res = 100000
    while i < n:
        for fac in M[A[i]]:
            if fac > m:
                break
            if fac not in freq:
                freq[fac] = 0
            freq[fac] += 1
        while len(freq) == m:
            res = min(res, A[i] - A[l], res)
            for fac in M[A[l]]:
                if fac > m:
                    break
                freq[fac] -= 1
                if freq[fac] == 0:
                    del freq[fac]
            l += 1
        i += 1
    print(res if res != 100000 else -1)
for i in range(N):
    solve()

Solution (Python):
import math
from collections import defaultdict
from itertools import accumulate

def check(num):
    for fac in memo[num]:
        if m >= fac >= mod and rmd[fac - mod] == 1:
            return False
    return True

def update(num):
    for fac in memo[num]:
        if m >= fac >= mod:
            rmd[fac - mod] -= 1
N = 100000
memo = defaultdict(list)
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        memo[j].append(i)
for t in range(int(input())):
    (n, m) = map(int, input().split())
    a = list(set(map(int, input().split())))
    n = len(a)
    a.sort()
    mod = m // 2 + 1
    rmd = [0] * (m - m // 2)
    z = m - m // 2
    l = n
    for i in range(n):
        if a[i] // mod > 0:
            l = i
            break
    ans = math.inf
    for i in range(l, n):
        for fac in memo[a[i]]:
            if m >= fac >= mod:
                if rmd[fac - mod] == 0:
                    z -= 1
                    assert z > -1
                rmd[fac - mod] += 1
        while l < i and check(a[l]):
            update(a[l])
            l += 1
        if z == 0:
            ans = min(ans, a[i] - a[l])
    if ans == math.inf:
        print(-1)
    else:
        print(ans)