# Verificador de SUBSET-SUM

Dada una lista de números $x_1, \ldots, x_n$ y un objetivo $t$, ¿hay un subconjunto de los números que sume
exactamente $t$?

$$
\mathrm{SUBSET\text{-}SUM} = \{\, \langle x_1, \ldots, x_n, t \rangle : \text{hay posiciones distintas } i_1, \ldots, i_k \text{ con } x_{i_1} + \cdots + x_{i_k} = t \,\}
$$

La lista puede repetir números: lo que no se puede repetir es la posición. En Algoritmos lo resolvieron con una
tabla de $n \cdot t$ casillas, que sirve cuando $t$ es pequeño. Aquí los números tienen 13 dígitos y esa tabla no
entra en ninguna memoria. Comprobar un subconjunto que alguien propone, en cambio, es sumar.

## Entrada

```text
n t
x1 x2 ... xn
c
k i1 i2 ... ik     (c líneas: un certificado por línea)
```

- Los $n$ números y el objetivo $t$.
- Siguen $c$ certificados. Cada uno es un número $k$ y después $k$ enteros: las **posiciones**, contadas desde
  1, de los números elegidos. Pueden venir en cualquier orden.

## Salida

Una línea por certificado, en el mismo orden: `válido` si las posiciones son un subconjunto que suma $t$, e
`inválido` si no. Es válido cuando cumple todo esto:

1. Cada posición existe: $1 \leq i_j \leq n$.
2. Ninguna posición se repite.
3. $x_{i_1} + x_{i_2} + \cdots + x_{i_k} = t$.

El certificado vacío, con $k = 0$, es el subconjunto vacío, que suma 0.

## Límites

- $1 \leq n \leq 500\,000$.
- $1 \leq x_i \leq 10^{13}$ y $0 \leq t \leq 9 \cdot 10^{18}$.
- $1 \leq c \leq 1000$.
- En cada certificado, $0 \leq k \leq 1\,000\,000$, y los $k$ de todos los certificados suman a lo sumo
  1 000 000.
- Los elementos de un certificado son enteros entre $-10^9$ y $10^9$: pueden no ser posiciones.

## Los números no caben en un int

Un `int` tiene 32 bits y llega hasta $2^{31} - 1 = 2\,147\,483\,647$, unos $2 \cdot 10^9$. Aquí un solo número
puede valer $10^{13}$, y la suma de todos llega a $500\,000 \cdot 10^{13} = 5 \cdot 10^{18}$. Usen `long long`,
que tiene 64 bits y llega hasta $2^{63} - 1 \approx 9{,}22 \cdot 10^{18}$: los números, el objetivo y la suma
caben, con poco margen.

- Si suman en un `int`, la suma se trunca y el programa responde `válido` a sumas que difieren de $t$ en un
  múltiplo de $2^{32}$. Hay casos armados para eso.
- Si suman en un `double`, la suma se redondea: un `double` tiene 53 bits de precisión, y cerca de $10^{18}$ no
  distingue un número del siguiente. Hay un caso donde la suma se pasa de $t$ por 1.
- El margen alcanza solo si suman posiciones **distintas**. Si siguen sumando después de encontrar una posición
  repetida, un certificado de un millón de posiciones iguales suma $10^{19}$, que ya no cabe. Dejen de sumar
  cuando el certificado ya es inválido, pero sigan leyendo.

## Ejemplo

Entrada (`casos/01.in`):

```text
6 28
8 13 21 5 17 2
5
4 1 2 4 6
3 3 4 6
2 1 3
4 4 4 4 2
4 1 2 4 7
```

Salida:

```text
válido
válido
inválido
inválido
inválido
```

El primero es $8 + 13 + 5 + 2 = 28$ y el segundo $21 + 5 + 2 = 28$. El tercero suma 29. El cuarto suma
$5 + 5 + 5 + 13 = 28$, pero usa tres veces la posición 4. El quinto nombra una posición 7 que no existe.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Sumar es lineal. Lo que puede salir caro es la condición 2: si para saber si una posición se repite la comparan
con todas las anteriores del certificado, un certificado de 500 000 posiciones cuesta del orden de $10^{11}$
comparaciones y el juez da `TLE`. Usen un arreglo indexado por la posición. Con hasta 1000 certificados, piensen
también cuánto cuesta dejar ese arreglo limpio entre uno y otro.

## Casos de borde

Los casos pequeños traen, entre otros: objetivo 0 con el certificado vacío, un solo número, números repetidos en
la lista (posiciones distintas con el mismo valor), el mismo subconjunto en distinto orden, posiciones que no
existen (0, negativas y mayores que $n$), un objetivo mayor que la suma de todos los números, y sumas que pasan
de $2^{32}$.

## Cómo avanzar

1. El esqueleto ya lee todo con `long long`. Sumen los números de las posiciones y comparen con $t$, sin
   comprobar nada más. Miren qué casos pasan.
2. Agreguen las condiciones 1 y 2, y pasen los casos del 01 al 10.
3. Pasen los casos 11 y 12, que `make test` genera con los programas `casos/gen_11.cpp` y `casos/gen_12.cpp`.
4. Cambien `long long` por `int` en la suma y vuelvan a correr el juez. Anoten qué casos fallan y por qué.
