# Verificar un producto de matrices al azar

Alguien les entrega tres matrices $A$, $B$ y $C$ de $n \times n$ y afirma que $C = A \cdot B$. Comprobarlo
multiplicando cuesta $n^3$ operaciones. Con el algoritmo de Freivalds se comprueba con $O(n^2)$ por ronda,
lanzando monedas, y con una probabilidad de error que ustedes eligen.

Todas las cuentas de este problema son **módulo el primo $p = 10^9 + 7 = 1\,000\,000\,007$**. Las entradas de
las matrices son restos, entre 0 y $p - 1$, y la pregunta es si cada entrada de $A \cdot B$, reducida módulo
$p$, es igual a la entrada correspondiente de $C$.

## Entrada

La primera línea tiene $n$. Siguen $3n$ líneas con $n$ números cada una, separados por espacios: las $n$ filas
de $A$, después las $n$ filas de $B$ y después las $n$ filas de $C$.

```text
2
1 2
3 4
5 6
7 8
19 22
43 50
```

## Salida

Una sola línea: `iguales` si $A \cdot B = C$ módulo $p$, y `distintos` si no.

## Límites

- $1 \leq n \leq 2000$.
- Todas las entradas de $A$, $B$ y $C$ son enteros entre 0 y $p - 1 = 1\,000\,000\,006$.
- La entrada tiene siempre el formato descrito: no tienen que detectar errores.

## Ejemplo

Para la entrada de arriba la salida es:

```text
iguales
```

porque

$$
\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \cdot \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix} = \begin{pmatrix} 19 & 22 \\ 43 & 50 \end{pmatrix}.
$$

Es el caso `casos/01.in`. El caso `casos/02.in` es igual salvo la última entrada de $C$, que vale 51, y su
salida es:

```text
distintos
```

## Tiempo

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

En los dos casos grandes $n = 2000$. Calcular $A \cdot B$ por la definición son $n^3 = 8 \cdot 10^9$
multiplicaciones con su reducción módulo $p$, y el juez da `TLE`. Una ronda de Freivalds son tres productos de
matriz por vector: $3n^2 = 1{,}2 \cdot 10^7$ operaciones.

## El algoritmo

Una ronda:

1. Elegir un vector $r$ de $n$ coordenadas, cada una 0 o 1 con una moneda independiente.
2. Calcular $x = B \cdot r$, después $y = A \cdot x$, y aparte $z = C \cdot r$. Todo módulo $p$.
3. Si $y \neq z$, la respuesta es `distintos`, con seguridad.

Si $A \cdot B \neq C$, una ronda lo detecta con probabilidad al menos $1/2$: está demostrado en los apuntes de
la semana 15. Repitan la ronda **$k = 30$ veces**, con monedas nuevas cada vez, y respondan `iguales` solo si
ninguna encontró una diferencia. La probabilidad de responder `iguales` por error es a lo sumo
$2^{-30} < 10^{-9}$.

Eso quiere decir que una solución correcta puede, en principio, recibir un `WA`. Hay 11 casos con respuesta
`distintos`, así que la probabilidad de que el juez le marque algún error a una solución correcta es menor que
$11 \cdot 10^{-9}$ por cada vez que lo corren. Si ven un `WA`, no es eso: busquen el error.

## Cuidado con el overflow

- Una entrada es menor que $p < 2^{30}$ y cabe en 32 bits.
- El producto de dos entradas llega a $(p - 1)^2 \approx 10^{18}$. **No cabe en 32 bits**, y sí en 64 bits
  sin signo, que llegan hasta $1{,}8 \cdot 10^{19}$. Conviertan a `std::uint64_t` **antes** de multiplicar:
  `std::uint64_t{a} * b`, y no `a * b` guardado después en una variable de 64 bits.
- Al sumar productos, reduzcan módulo $p$ antes de que la suma pase de $2^{64}$. Lo más simple es reducir
  después de cada suma.
- Las coordenadas de $B \cdot r$ ya son restos módulo $p$, y no ceros y unos: en $A \cdot (B \cdot r)$ hay
  productos de verdad.

Los casos `05` y `11` tienen entradas iguales a $p - 1$ para que un producto en 32 bits no pase.

## Qué trae el esqueleto

`solution.cpp` ya lee la entrada, y deja las tres matrices en vectores de `std::uint32_t` guardados por filas:
la entrada $(i, j)$ de una matriz `m` está en `m[i * n + j]`. La lectura usa un lector por bloques, porque en
los casos grandes hay 12 millones de números y leerlos uno por uno con `std::cin` tarda más que todo el
algoritmo. No hace falta tocarlo.

Falta la función `probably_equal`. Tal como está, responde siempre `iguales`, y el juez da `WA` en los casos
con respuesta `distintos`.

En `code/week-15/freivalds.h` hay una versión del algoritmo, la que usan los ejemplos de los apuntes. Pueden
leerla. Está escrita para que se parezca a la definición y no para ser rápida, con un vector por fila y una
división en cada operación; `solution.cpp` se escribe **sin incluirla**, porque el juez compila ese único
archivo.

## Cómo avanzar

```sh
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

Los dos casos grandes no están guardados: `make test` los genera con `casos/gen_19.cpp` y `casos/gen_20.cpp`.
Ocupan unos 120 MB cada uno en `build/casos/`; `make clean` los borra.

1. Escriban una ronda de Freivalds y pasen `casos/01.in` y `casos/02.in`. Hagan primero a mano el caso `02`
   con $r = (0, 1)$ y con $r = (1, 0)$: ¿cuál de los dos detecta la diferencia, y por qué?
2. Pongan la aritmética módulo $p$ y pasen los casos pequeños. Antes de correr el juez, respondan: ¿cuánto vale
   $(p - 1) \cdot (p - 1)$ módulo $p$? Es el caso `05`.
3. Repitan la ronda 30 veces y pasen los casos grandes. Si alguno da `TLE`, cuenten cuántas operaciones hace
   su programa por ronda: tienen que ser unas $3n^2$.

Los casos traen, entre otros: matrices de $1 \times 1$; una matriz $A$ nula; la identidad; entradas iguales a
$p - 1$; una $C$ que es $B \cdot A$ en vez de $A \cdot B$; diferencias en una sola entrada, la primera o la
última; y dos casos (`07` y `17`) en los que cada fila de $C$ tiene dos entradas cambiadas, una en $+d$ y otra
en $-d$, de modo que la suma de cada fila queda igual. En esos, el vector de solo unos no ve nada: no reemplacen
las monedas por un vector fijo.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Medir el error con una ronda

Este es el paso 4 de la guía. El archivo `experiment.cpp` arma dos matrices de $40 \times 40$ y una $C$ que
difiere de $A \cdot B$ en **una sola entrada**, que es el peor caso para el algoritmo. Después corre 1000 veces
"$k$ rondas" y cuenta en cuántas ninguna ronda detectó la diferencia. No lee nada de la entrada.

Copien en la función `round_detects` de ese archivo su ronda de Freivalds: tiene que elegir el vector con el
generador `rng` que recibe y devolver `true` si $A \cdot (B \cdot r) \neq C \cdot r$.

```sh
g++ -Wall -Wextra -std=c++20 -O2 experiment.cpp -o build/experiment
build/experiment
```

Tal como viene, la función no detecta nunca nada, y la tabla lo muestra:

```text
semilla 1, 1000 ejecuciones por fila
 k   fallos   fracción   cota 2^-k
 1     1000      1.000    0.500000
 2     1000      1.000    0.250000
 5     1000      1.000    0.031250
10     1000      1.000    0.000977
```

Con su ronda, miren la fila de $k = 1$. Respondan:

- ¿Cuántos fallos esperaban en 1000 ejecuciones, según la cota $1/2$? ¿Cuántos salieron?
- Corran con otras semillas: `build/experiment 2`, `build/experiment 3`. ¿Cuánto cambia el número?
- La cota dice "a lo sumo $1/2$". ¿Por qué aquí la fracción no sale mucho menor que $1/2$? Miren en los
  apuntes qué pasa cuando la diferencia está en una sola entrada.

Si la fila de $k = 1$ da una fracción muy lejos de $0{,}5$, hay un error: en la ronda, o en cómo se sacan los
bits del generador. Por ejemplo, si todas las coordenadas de $r$ salen del mismo número al azar sin separar sus
bits, las monedas dejan de ser independientes.

## Repetir: k = 2, 5 y 10

Este es el paso 5. El mismo programa llena las otras tres filas. Anoten la tabla y compárenla con la columna
de la cota.

- Con $k = 2$, 5 y 10 se esperan cerca de $1000 \cdot 2^{-k}$ fallos: 250, 31 y 1. ¿Qué obtuvieron?
- Con $k = 10$ lo más probable es ver 0, 1 o 2 fallos. ¿Cuántas ejecuciones habría que hacer para esperar ver
  un fallo con $k = 30$?
- Cambien `experiment.cpp` para que $C$ difiera de $A \cdot B$ en **todas** las entradas de una fila. ¿Qué pasa
  con la fracción de fallos de $k = 1$? ¿Contradice la cota?

## Para seguir

Opcional, sin casos en el juez.

- La variante con $r$ en todo el rango: elijan cada coordenada de $r$ al azar entre 0 y $p - 1$, y no solo
  entre 0 y 1. Es el ejercicio 8 de los apuntes: entonces una ronda falla con probabilidad a lo sumo
  $1/p \approx 10^{-9}$. ¿Cuántas rondas hacen falta ahora para el error de 30 rondas con ceros y unos? ¿Qué
  se pierde en velocidad en el cálculo de $B \cdot r$ y de $C \cdot r$?
- Cuando la respuesta es `distintos`, impriman además una fila $i$ en la que $A \cdot B$ y $C$ difieren. El
  vector $A \cdot (B \cdot r) - C \cdot r$ ya dice cuál. ¿Cómo encontrarían también la columna, sin multiplicar
  las matrices?
