Official Editorial (C++)

Solution

Explanation

Let's use a sliding window technique on sorted smartness values to track how many topics are being covered as we add and remove a student.

As we expand the team by moving the right pointer, we check the factors of each student's smartness to determine which topics they help cover. If all topics are covered, we calculate the difference between the highest and lowest smartness values in the current team. Then, we attempt to reduce the size of the team from the left to see if the range can be further minimized while still covering all topics.

Implementation

Time Complexity: $\mathcal{O}(n \log(n) + n \cdot \sqrt{M})$

Copy
M = 10**5
factors = [[] for _ in range(M + 1)]

# Precompute factors for all numbers from 1 to M
for i in range(1, M + 1):
	for j in range(i, M + 1, i):
		factors[j].append(i)

for _ in range(int(input())):
	n, m = map(int, input().split())