Skip to Content
CTRL K

Jury Marks

Editorial oficial 

Explicación

Observemos que nos dan todas las notas del jurado en orden cronológico. Por lo tanto, si conociéramos la puntuación inicial del participante, podríamos calcular la puntuación anunciada del participante después de que cada uno de los kk jueces dé su calificación respectiva.

Esto nos motiva a usar sumas de prefijos. Consideremos el arreglo de sumas de prefijos SS tal que S[i]S[i] es igual a la suma de las primeras ii notas del jurado.

Ahora consideremos el valor b1b_1, el primero de los valores que Polycarp recuerda que se anunciaron. Si denotamos la puntuación inicial por II, observamos que b1=I+S[i]b_1 = I + S[i] para algún ii de 11 a kk. Así, debemos tener que I=b1−S[i]I = b_1 - S[i] para algún ii. Luego podemos iterar por ii para hallar nuestros candidatos a la puntuación inicial del participante.

Ahora debemos comprobar si cada uno de nuestros candidatos es realmente una puntuación de partida válida. Recordemos que Polycarp recuerda algunas de las puntuaciones anunciadas, todas las cuales fueron la puntuación del participante en algún momento. Por lo tanto, si elegimos de forma arbitraria uno de nuestros valores candidatos, digamos CC, entonces el conjunto de valores de la forma C+S[i]C + S[i] para ii que va de 11 a kk debe contener todas las puntuaciones recordadas por Polycarp.

Así, comprobamos si cada candidato produce una puntuación de partida válida, y usamos el recuento de candidatos válidos para calcular nuestra respuesta.

Implementación

Complejidad temporal: O(K2log⁡K)\mathcal{O}(K^2 \log K)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int mark_num;
	int remember_num;
	cin >> mark_num >> remember_num;
 
	// Todos los cambios netos en la puntuación
	vector<int> changes(mark_num + 1);
	vector<int> scores(remember_num);
	for (int i = 1; i <= mark_num; ++i) {
		cin >> changes[i];
		changes[i] += changes[i - 1];
	}
	for (int &p : scores) { cin >> p; }
 
	set<int> poss_starts;
	for (int m = 1; m <= mark_num; ++m) {
		poss_starts.insert(scores.front() - changes[m]);
	}
 
	int ans = 0;
	for (int s : poss_starts) {
		// Cómo quedan todas las puntuaciones dada la puntuación de partida
		set<int> points;
		for (int i = 1; i <= mark_num; ++i) { points.insert(s + changes[i]); }
 
		bool valid = true;
		for (int p : scores) { valid &= points.count(p); }
 
		ans += valid;
	}
	cout << ans << endl;
}
import java.io.*;
import java.util.*;
 
public class JuryMarks {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int numJury = io.nextInt();
		int numScores = io.nextInt();
		// Todos los cambios netos en la puntuación
		int[] changes = new int[numJury + 1];
		int[] scores = new int[numScores];
 
		for (int x = 1; x <= numJury; x++) {
			changes[x] = io.nextInt() + changes[x - 1];
		}
		for (int x = 0; x < numScores; x++) { scores[x] = io.nextInt(); }
 
		Set<Integer> possStarts = new TreeSet<>();
		for (int x = 1; x <= numJury; x++) { possStarts.add(scores[0] - changes[x]); }
 
		int validStarts = 0;
		for (int s : possStarts) {
			// Cómo quedan todas las puntuaciones dada la puntuación de partida
			Set<Integer> points = new TreeSet<>();
			for (int i = 1; i <= numJury; i++) { points.add(s + changes[i]); }
 
			boolean valid = true;
			for (int p : scores) { valid &= points.contains(p); }
 
			validStarts += valid ? 1 : 0;
		}
		io.println(validStarts);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
mark_num, remember_num = [int(i) for i in input().split()]
 
# Todos los cambios netos en la puntuación
changes = [0] + [int(i) for i in input().split()]
scores = {int(i) for i in input().split()}
assert mark_num == len(changes) - 1 and len(scores) == remember_num
 
for i in range(1, len(changes)):
	changes[i] += changes[i - 1]
 
poss_starts = set()
random_score = next(iter(scores))
for c in range(1, len(changes)):
	poss_starts.add(random_score - changes[c])
 
valid_starts = 0
for s in poss_starts:
	# Cómo quedan todas las puntuaciones dada la puntuación de partida
	resulting_scores = set()
	for c in range(1, len(changes)):
		resulting_scores.add(s + changes[c])
 
	valid_starts += scores.issubset(resulting_scores)
 
print(valid_starts)
Fundamentos