# Verificador de SAT

Una fórmula en **forma normal conjuntiva** (CNF) es una conjunción de **cláusulas**, y cada cláusula es una
disyunción de **literales**: una variable $x_i$ o su negación $\lnot x_i$. Por ejemplo:

$$
\varphi = (x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_2 \lor x_3) \land (\lnot x_3 \lor \lnot x_1)
$$

Una **asignación** le da a cada variable un valor, verdadero o falso. La asignación **satisface** la fórmula si
cada cláusula tiene al menos un literal verdadero. $\mathrm{SAT}$ es el lenguaje de las fórmulas que tienen
alguna asignación que las satisface. Encontrarla es difícil. Comprobar una que alguien propone es evaluar la
fórmula, y eso es lo que hace este programa.

## Entrada

La fórmula viene en formato DIMACS, el que leen los solucionadores como `minisat` y el que ya usaron en
Algoritmos. Después vienen los certificados.

```text
c comentarios
p cnf n m
(m cláusulas: literales separados por espacios, cada cláusula termina en 0)
c
(c certificados: literales separados por espacios, cada certificado termina en 0)
```

- Las líneas que empiezan con `c` son comentarios. Solo aparecen antes de la línea `p cnf`.
- `p cnf n m` dice que la fórmula tiene las variables $x_1, \ldots, x_n$ y $m$ cláusulas.
- Un literal es un entero distinto de cero: `i` es $x_i$ y `-i` es $\lnot x_i$. Un `0` termina la cláusula.
  Casi siempre hay una cláusula por línea, pero el formato no lo exige: una cláusula puede seguir en la línea
  siguiente. Lean número por número, con `>>`.
- Una cláusula puede repetir un literal, o tener a $x_i$ y a $\lnot x_i$ a la vez. Una cláusula puede no tener
  ningún literal (solo el `0`): es falsa con cualquier asignación.
- Después de las cláusulas viene la cantidad $c$ de certificados. Un certificado es una lista de enteros
  distintos de cero, terminada en `0`: `i` dice que $x_i$ es verdadera, y `-i` que es falsa. Es el formato en el
  que `minisat` escribe la asignación que encuentra. Los literales pueden venir **en cualquier orden**.

## Salida

Una línea por certificado, en el mismo orden: `válido` si es una asignación que satisface la fórmula, e
`inválido` si no. Es válido cuando cumple todo esto:

1. Cada literal nombra una variable que existe: su valor absoluto está entre 1 y $n$.
2. Cada variable recibe un valor **exactamente una vez**. Si falta una variable, el certificado es inválido,
   aunque la fórmula quede satisfecha con las demás. Si una variable aparece dos veces, también, aunque sea con
   el mismo valor.
3. Cada cláusula tiene al menos un literal verdadero.

## Límites

- $1 \leq n \leq 100\,000$ y $0 \leq m \leq 200\,000$.
- Las cláusulas tienen entre todas a lo sumo 500 000 literales.
- $1 \leq c \leq 10$. Cada certificado tiene a lo sumo 200 000 literales.
- Los literales de las cláusulas tienen valor absoluto entre 1 y $n$. Los de los certificados, entre 1 y $10^9$:
  pueden nombrar variables que no existen.

## Ejemplo

Entrada (`casos/01.in`), con la fórmula $\varphi$ de arriba:

```text
c (x1 o no x2) y (no x1 o x2 o x3) y (no x3 o no x1)
p cnf 3 3
1 -2 0
-1 2 3 0
-3 -1 0
7
1 2 -3 0
-3 2 1 0
-1 -2 3 0
1 -2 -3 0
1 2 0
1 -1 2 -3 0
1 2 -4 0
```

Salida:

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

Los dos primeros son la misma asignación, $x_1$ y $x_2$ verdaderas y $x_3$ falsa, en distinto orden. El tercero
es otra asignación que también sirve. Con el cuarto, la segunda cláusula queda falsa. En el quinto $x_3$ no
tiene valor, en el sexto $x_1$ tiene dos y en el séptimo aparece una variable $x_4$ que no existe.

## Tiempo

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

La fórmula puede tener 500 000 literales y el certificado 100 000. Si por cada literal de la fórmula recorren
el certificado hasta encontrar su variable, son del orden de $10^{10}$ comparaciones por certificado y el juez da
`TLE`. Pasen primero el certificado a un arreglo indexado por la variable, con tres valores posibles: verdadera,
falsa y sin valor. Después, cada literal de la fórmula se consulta en tiempo constante.

## Casos de borde

Los casos pequeños traen, entre otros: una fórmula sin cláusulas (toda asignación completa la satisface), una
cláusula vacía, una fórmula sin solución, cláusulas con literales repetidos y con una variable y su negación, una
variable que no aparece en ninguna cláusula, cláusulas partidas en varias líneas, y certificados incompletos,
con variables repetidas, con variables fuera de rango y vacíos.

## Cómo avanzar

1. El esqueleto ya lee la fórmula y los certificados. Comprueben que entienden cómo salta los comentarios y cómo
   termina cada cláusula.
2. Escriban primero la comprobación de que el certificado está bien formado: las condiciones 1 y 2.
3. Evalúen la fórmula y pasen los casos del 01 al 09.
4. Pasen los casos 10 y 11, que `make test` genera con los programas `casos/gen_10.cpp` y `casos/gen_11.cpp`.
5. El entorno trae `minisat`. Quiten los certificados de `casos/01.in` y dénselo:

   ```sh
   head -5 casos/01.in > /tmp/f.cnf
   minisat /tmp/f.cnf /tmp/salida.txt
   cat /tmp/salida.txt
   ```

   La segunda línea de `salida.txt` es un certificado en el formato de este laboratorio. Agréguenlo a la entrada
   y comprueben que su verificador lo acepta. Así se usa un solucionador con cuidado: no se le cree, se comprueba
   lo que responde.
