Supongo que llegar a las matrices a[i][j][k] y b[i][j][k] ([matemáticas] 1 \ leq i, j, k \ leq N [/ matemáticas] ) se puede hacer con la fórmula simple dada en el enunciado del problema.
De aquí en adelante, usaré el término cubelet coincidente para referirme a un “punto 3D” [matemática] (x, y, z) [/ matemática] tal que a[x][y][z] == b[x][y][z] .
Mediante la programación dinámica , precalculemos una matriz dp[i][j][k] (para [matemáticas] 0 \ leq i, j, k \ leq N [/ matemáticas]) que almacena el número de cubos coincidentes en el rango [ matemáticas] 1 \! \ leq \! X \! \ leq \! i, \ 1 \! \ leq \! y \! \ leq \! j, \ 1 \! \ leq \! z \! \ leq \! k [/ matemáticas]. Esto se puede hacer en [math] \ mathcal {O} (N ^ 3) [/ math].
¡Ahora usando esta matriz podemos encontrar el número de cubelets coincidentes en el rango [matemáticas] x_1 \! \ leq \! X \! \ leq \! x_2, \ y_1 \! \ leq \! y \! \ leq \! y_2, \ z_1 \! \ leq \! z \! \ leq \! z_2 [/ math] en [math] \ mathcal {O} (1) [/ math].
- ¿Por qué es Introducción a los algoritmos una lectura obligada para convertirse en un mejor programador?
- ¿De dónde obtienen los fondos de cobertura sus datos en tiempo real para algoritmos?
- Procesamiento de lenguaje natural: ¿Cuál es la mejor manera de detectar si un fragmento de texto es interrogativo?
- ¿Cuál es la manera de mejorar en la resolución de preguntas recurrentes y complicadas de estructura de datos / algoritmo?
- ¿Qué es mejor para la búsqueda binaria, la matriz ordenada o la lista vinculada?
Ahora la similitud [matemática] S [/ matemática] es el tamaño del subcubo más grande de tal manera que al menos [matemática] P% [/ matemática] de los cubelets coinciden. Entonces, iteremos hacia atrás sobre [math] S [/ math].
Para una [matemática] S [/ matemática] dada, podemos verificar si esta es la similitud en [matemática] \ matemática {O} (N ^ 3) [/ matemática] iterando sobre todos los “puntos finales” posibles [matemática] (i, j, k) [/ math] (para [math] S \ leq i, j, k \ leq N [/ math]) del subcubo y comprobar si al menos [math] P% [/ math] cubelets de este subcubo coincide o no.
Complejidad general: [math] \ mathcal {O} (T \ cdot N ^ 4) [/ math] (puede reducirse a [math] \ mathcal {O} (T \ cdot N ^ 3 \ log {N}) [ / math] por binario buscando [math] S [/ math]), lo cual es lo suficientemente bueno para pasar.
Enlace a mi solución AC .
PD: Si desea más explicaciones sobre alguna parte particular de este “editorial”, con gusto lo ayudaré. 🙂
