Official Analysis (C++, Java)

Explanation

Due to the low bounds, we can use a brute-force approach. There are seven labels $A$, $B$, $C$, $A + B$, $B + C$, $A + C$, and $A + B + C$. We need exactly $N$ of them, so we can iterate over all combinations of $N$ labels to decide which labels appear in this test case.

For a chosen set of labels, we need to decide which number corresponds to which label. We iterate over all permutations of the chosen labels, mapping them to the input array in order. Finally, we need to deduce the unique triple $(A, B, C)$ consistent with the mappings. To do this, we track candidate values for $A$, $B$, and $C$ using sets. If each of $A$, $B$, and $C$ has one consistent value, we record the triple as valid.

We can always deduce a possible value for each of $A$, $B$, and $C$, because each variable appears in four of the seven labels. At most three of these labels can be missing, so we can use the remaining label to determine the variable's value.

Implementation

Time Complexity: $\mathcal{O}(T)$

Copy
import itertools

for i in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]

	def deduce_ABC(tags):
		a = b = c = ab = bc = ac = abc = -1
		for i in range(N):
			value = arr[i]