Definición. K es el número de participantes en la sala de competición.

Subpregunta 1

Esta subpregunta se puede resolver tratando de colocar a los participantes en todos los rectángulos posibles.

Solo habrá exactamente un tamaño de rectángulo válido que es el rectángulo 1 × K1.

Suponga que el rectángulo que se va a seleccionar se encuentra en los cuadrados (1, c_1) a (1, c_2). Entonces, para calcular el número mínimo de participantes en el rectángulo seleccionado, es el número de participantes menos el número de participantes que ya están en el rectángulo. Para contar el número de participantes en el rectángulo seleccionado, simplemente repita todos los valores desde los cuadrados (1, c_1) a (1, c_2).

El número de rectángulos posibles que se pueden formar es tanto como O (C) y el número de iteraciones necesarias para calcular el número de participantes en el rectángulo es O (C) para cada posible cuadrado de largo.

La complejidad de esta solución es O (C ^ 2).

Subpregunta 2

Usando la misma observación que en el subsuelo anterior, podemos optimizar cómo contar el número de participantes en un rectángulo usando la suma del prefijo.

Definición. ~prefix_ {i}~ es el número de participantes de la parcela (1, 1) a (1, i).

Para contar el número de participantes usando la suma del prefijo de plot (1, c_1) a (1, c_2) es calcular el valor de ~prefix_{c_2} - prefix_{c_1-1}~.

La complejidad de esta solución es O (C).

Subpregunta 3

Este problema se puede resolver probando todos los tamaños posibles de los rectángulos y probando todas las ubicaciones de los rectángulos. Usando la misma observación que en el problema 3 podemos calcular el desplazamiento mínimo para cada valor posible.

El número de rectángulos posibles es O (RC) mientras que el número de ubicación de un rectángulo es O (RC) y las iteraciones necesarias para calcular los participantes en un rectángulo. rectángulo son O (RC).

La complejidad final de esta solución es ~O ((RC)^3)~.

Subpregunta 4

Usando el mismo método que el subsuelo anterior, podemos optimizar cómo contar el número de participantes en un rectángulo usando la suma del prefijo 2D.

Definición. ~prefix_{i,j}~, es el número de participantes de las parcelas (1,1) a (i, j).

Para contar el número de participantes usando la suma de prefijo 2D usamos prefix sums e inclusión exlclusión, ~prefix_{i,j} = prefix_{i-1,j} + prefix_{i,j-1} - prefix_{i-1,j-1} + a_{i,j}~.

La complejidad final de esta solución es ~O ((RC) ^ 2)~.

Subpregunta 5

Utilizando el mismo método que en la subpregunta anterior, podemos optimizar el cálculo de rectángulos de varios tamaños. Un rectángulo válido de tamaño A × B debe satisfacer la ecuación A × B = K o, en otras palabras, A divide uniformemente el K. El número de números naturales que divide uniformemente el K no será mayor que ~\sqrt{k}~.

La complejidad final de esta solución es ~O ((RC) ^ {1.5})~