Skip to Content
CTRL K

Quiz Master

Editorial oficial (C++) 

Solución

Explicación

Usemos una técnica de ventana deslizante sobre los valores de inteligencia ordenados para llevar el registro de cuántos temas se cubren a medida que agregamos y quitamos un estudiante.

A medida que expandimos el equipo moviendo el puntero derecho, comprobamos los factores de la inteligencia de cada estudiante para determinar qué temas ayudan a cubrir. Si todos los temas están cubiertos, calculamos la diferencia entre los valores de inteligencia más alto y más bajo del equipo actual. Luego, intentamos reducir el tamaño del equipo desde la izquierda para ver si el rango se puede minimizar aún más sin dejar de cubrir todos los temas.

Implementación

Complejidad temporal: O(nlog⁡(n)+n⋅M)\mathcal{O}(n \log(n) + n \cdot \sqrt{M})

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
 
const int M = 1e5;
std::vector<int> factors[M + 1];
 
int main() {
	// Precomputar factores de todos los números de 1 a M
	for (int i = 1; i <= M; i++) {
		for (int j = i; j <= M; j += i) { factors[j].push_back(i); }
	}
 
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, m;
		std::cin >> n >> m;
		std::vector<int> arr(n);
		std::vector<int> freq(m + 1);
		for (int &x : arr) { std::cin >> x; }
 
		std::sort(std::begin(arr), std::end(arr));
 
		int topics_covered = 0;
		int res = INT_MAX;
		for (int i = 0, j = 0; i < n; i++) {
			// agregar estudiante
			while (j < n && topics_covered < m) {
				for (int x : factors[arr[j]]) {
					if (x <= m) {
						freq[x]++;
						if (freq[x] == 1) {  // tema x cubierto por primera vez
							topics_covered++;
						}
					}
				}
				j++;
			}
			if (topics_covered == m) { res = std::min(arr[j - 1] - arr[i], res); }
 
			// quitar estudiante
			for (int x : factors[arr[i]]) {
				if (x <= m) {
					freq[x]--;
					if (freq[x] == 0) {  // tema x ya no cubierto
						topics_covered--;
					}
				}
			}
		}
 
		std::cout << (res == INT_MAX ? -1 : res) << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class Main {
	private static final int M = 100000;
	private static List<Integer>[] factors = new ArrayList[M + 1];
 
	public static void main(String[] args) throws IOException {
		// Precomputar factores de todos los números de 1 a M
		for (int i = 1; i <= M; i++) { factors[i] = new ArrayList<>(); }
		for (int i = 1; i <= M; i++) {
			for (int j = i; j <= M; j += i) { factors[j].add(i); }
		}
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int testNum = Integer.parseInt(st.nextToken());
 
		for (int t = 0; t < testNum; t++) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int[] arr = new int[n];
			int[] freq = new int[m + 1];
 
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); }
 
			Arrays.sort(arr);
 
			int topicsCovered = 0;
			int res = Integer.MAX_VALUE;
			for (int i = 0, j = 0; i < n; i++) {
				// agregar estudiante
				while (j < n && topicsCovered < m) {
					for (int x : factors[arr[j]]) {
						if (x <= m) {
							freq[x]++;
							if (freq[x] == 1) {  // tema x cubierto por primera vez
								topicsCovered++;
							}
						}
					}
					j++;
				}
				if (topicsCovered == m) { res = Math.min(arr[j - 1] - arr[i], res); }
 
				// quitar estudiante
				for (int x : factors[arr[i]]) {
					if (x <= m) {
						freq[x]--;
						if (freq[x] == 0) {  // tema x ya no cubierto
							topicsCovered--;
						}
					}
				}
			}
 
			System.out.println(res == Integer.MAX_VALUE ? -1 : res);
		}
	}
}
M = 10**5
factors = [[] for _ in range(M + 1)]
 
# Precomputar factores de todos los números de 1 a 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())
	arr = list(map(int, input().split()))
 
	arr.sort()
	freq = [0] * (m + 1)
	topics_covered = 0
	res = float("inf")
	j = 0
 
	for i in range(n):
		# agregar estudiante
		while j < n and topics_covered < m:
			for x in factors[arr[j]]:
				if x <= m:
					freq[x] += 1
					if freq[x] == 1:  # tema x cubierto por primera vez
						topics_covered += 1
 
			j += 1
 
		if topics_covered == m:
			res = min(res, arr[j - 1] - arr[i])
 
		# quitar estudiante
		for x in factors[arr[i]]:
			if x <= m:
				freq[x] -= 1
				if freq[x] == 0:  # tema x ya no cubierto
					topics_covered -= 1
 
	print(-1 if res == float("inf") else res)
Fundamentos