Official Editorial

Explanation

Observe that we are given all of the jury's marks in chronological order. Therefore, if we knew the participant's initial score, we could compute the participant's announced score after each of the $k$ judges gives their respective ratings.

This motivates us to use prefix sums. Consider the prefix sum array $S$ such that $S[i]$ equals the sum of the first $i$ jury marks.

Now consider the value $b_1$, the first of the values that Polycarp remembers being announced. Letting the initial score be denoted by $I$, we observe that $b_1 = I + S[i]$ for some $i$ from $1$ to $k$. Thus, we must have that $I = b_1 - S[i]$ for some $i$. We can then iterate through $i$ to find our candidates for the participant's initial score.

Now, we must check if each of our candidates is an actually valid starting score. Recall that Polycarp remembers some of the announced scores, all of which were the participant's score at some point. Therefore, if we arbitrarily pick one of our candidate values, say $C$, then the set of values of the form $C + S[i]$ for $i$ ranging from $1$ to $k$ must contain all of Polycarp's remembered scores.

Thus, we check if each candidate yields a valid starting score, and use the count of valid candidates to compute our answer.

Implementation

Time Complexity: $\mathcal{O}(K^2 \log K)$

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int mark_num;
	int remember_num;
	cin >> mark_num >> remember_num;

	// All net changes in the score
	vector<int> changes(mark_num + 1);

Copy
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();
		// All net changes in the score
		int[] changes = new int[numJury + 1];

Copy
mark_num, remember_num = [int(i) for i in input().split()]

# All net changes in the score
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]