Presentación

Terminamos esta sesión con un problema semejante al anterior. Vamos concretamente a estudiar el problema 836 del juez on-line de la UVA:

PROBLEMA 836. Largest Submatrix: Enunciado del problema en el juez on-line de la UVA

El enunciado es simple: dada una matriz cuadrada A de unos y ceros de tamaño N × N, encontrar el número de unos contenidos en la mayor submatriz de A que esté compuesta exclusivamente por unos. Nótese que, al igual que en el caso del problema anterior, en general la submatriz no tiene que ser cuadrada.

Si el alumno se siente capaz, puede intentar resolver el problema sin seguir leyendo más adelante el análisis que sigue a continuación.

Continuar con la lectura del análisis del problema y su enunciado.

Análisis del problema y su enunciado

Lo primero que encontramos en este problema son ciertas "peculiaridades" en la entrada y salida de datos. Los datos de entrada, aun siendo numéricos, no podemos leerlos como números pues los unos y ceros van consecutivos. Debemos leerlos como caracteres independientes. Con relativa frecuencia podemos encontrar problemas de este tipo, por lo que conviene llevar preparadas rutinas de entrada que manejen datos de esta manera en el lenguaje que elijamos, o al menos esqueletos de rutinas para tomar datos que vengan dispuestos de este modo.

En cuanto a la salida, también debemos llevar precauciones con el formato pues se nos dice que el resultado de dos casos consecutivos irán separados por una línea en blanco. El hecho de que diga "separados" y no "precedidos" ni "seguidos" significa que no podemos tratar todos los casos de la misma forma, pues no podemos dejar una línea en blanco después de la respuesta de cada caso (pues el último caso no debe llevar línea en blanco después) ni tampoco podemos dejar una línea en blanco antes de cada uno (pues el primero no debe llevar línea en blanco antes).

Aunque este tipo de peculiaridades es cada vez menos frecuente en los concursos de los últimos años, conviene estar alerta a la hora de detectarlas, pues con frecuencia son fuente de errores de tipo "Presentation Error".

Al igual que en el caso del problema anterior, también aquí existe un algoritmo de fuerza bruta cuyo tiempo está en Θ(N⁶) y que obviamente rebasa los límites de tiempo de ejecución asignados a este problema. Este algoritmo consistiría en los siguientes tratamientos:

1. Enumerar todos los posibles extremos superior-izquierdos de la submatriz. Esto sería un tratamiento en Θ(N²).
2. Para cada extremo superior-izquierdo, enumerar todos los posibles extremos inferior-derechos que se pueden tomar para definir la submatriz. Este tratamiento estaría también en Θ(N²).
3. Realizar una búsqueda de un valor cero dentro de la submatriz. Si la búsqueda es exitosa (se encuentra un cero) se descarta esa submatriz, de lo contrario se calcula el número de unos que contiene y se considera ese valor como candidato para el máximo buscado. Este tratamiento en general estará también en Θ(N²).

Al igual que en el caso del problema anterior, este es un problema que puede ser resuelto mediante un algoritmo que combina la técnica de programación dinámica con cálculos y tratamientos diseñados específicamente para este caso concreto.

Conviene familiarizarse con este tipo de algoritmos "híbridos", por así decirlo, pues con mucha frecuencia encontraremos problemas que pueden ser abordados con éxito combinando distintas técnicas de diseño y, en ciertos casos, también con algunos tratamientos específicos.

¿Imaginas de qué forma podemos combinar la técnica de programación dinámica en este caso?

Continuar leyendo pistas de resolución del ejercicio.

Primera pista:

También en este caso hay un tratamiento de preprocesamiento que puede irse realizando conforme se van tomando los datos de la entrada. Se trata de ir calculando por filas (o por columnas) para cada elemento en cada posición (i, j) el número de unos consecutivos que hay desde el inicio de esa fila/columna hasta él.

Ejemplo:

Si suponemos que lo hacemos por columnas, tomemos la matriz del ejemplo de entrada del enunciado del problema en el juez on-line. La siguiente imagen muestra alternativamente la matriz de entrada (compuesta exclusivamente por ceros y unos) y la matriz resultado del preprocesamiento descrito:

Para realizar este tratamiento con el elemento de la posición (i, j) debemos en general comprobar el valor de su vecino de la fila anterior, es decir, el valor en la posición (i – 1, j). Para resolver el problema de la primera fila podríamos pensar en hacer algo parecido a lo del problema anterior, es decir, incluir una primera fila 0 inicializada con valores adecuados, pero puesto que la primera fila debemos tratarla de forma distinta de todos modos, pues es la que determina el tamaño de la matriz que a priori no es conocido, no será necesario extender la tabla de esa forma.

De este modo, si partimos de unas declaraciones como las siguientes:

Código Pascal: definiciones y declaraciones de tipos y variables

const
    MAX_N = 25;
    ORD_0 = ord ('0');

type
    TRango = 1 .. MAX_N;
    TMatriz = array [TRango, TRango] of Integer;

var
    i, j  : TRango;
    rango : Integer;
    a     : TMatriz;
    c     : Char;

Podríamos hacer la entrada de datos (para un caso) y su preprocesamiento del siguiente modo:

Código Pascal: entrada de datos y preprocesamiento:

    rango := 0;
    (*
     * Leemos la primera línea y al mismo tiempo
     * calculamos la dimensión de la tabla en la
     * variable 'rango':
     *)
    while not eoln do
    begin
        read (c);
        inc (rango);
        a[1,rango] := ord (c) - ORD_0
    end;
    readln;
    (*
     * Leemos el resto de líneas mediante iteraciones
     * 'for', ahora que ya conocemos la dimensión de
     * la tabla:
     *)
    for i := 2 to rango do
    begin
        for j := 1 to rango do
        begin
            read (c);
            if c = '1' then
                a[i,j] := 1 + a[i-1,j]
            else
                a[i,j] := 0
        end;
        readln
    end;

Al igual que en el caso anterior, este tratamiento se realiza en el mismo tiempo (asintótico) en que se leen los datos de la entrada, por lo que también en este caso podemos decir que antes de empezar ya hemos hecho algunos cálculos.

Con la tabla dispuesta de este modo podemos encontrar con relativa facilidad y eficiencia el resultado pedido. ¿Sabes cómo?

Continuar leyendo la siguiente pista para de resolución del ejercicio.

Segunda pista:

Una vez que los datos están dispuestos según el preprocesamiento anteriormente descrito, el problema puede ser resuelto de la siguiente forma:

1. Enumerar todos los elementos de la matriz. Esto sería un tratamiento en Θ(rango²), utilizando la notación del código Pascal anterior.
2. Para cada uno de estos elementos cuyo valor sea distinto de cero (o lo que es lo mismo, que en la matriz original de entrada tuviese un 1) contar cuántos vecinos adyacentes tiene en su misma fila (incluido él mismo) cuyo valor sea mayor o igual que el suyo propio. Es decir, dado un valor A_i, j de la tabla, buscaremos cuál es la mayor submatriz de altura A_i, j con todo unos que se puede construir y que tenga como base la fila i–ésima y contenga al elemento (i, j). Esto sería un tratamiento en Θ(rango)

Estamos, por tanto, describiendo un tratamiento cuyo tiempo de ejecución estará en general en Θ(rango³). Nótese que para una posición (i, j) concreta este cálculo no necesariamente va a dar el valor de la mayor submatriz de unos en la que está contenida la posición (i, j), sino el valor de la mayor submatriz que contiene al elemento (i, j) y que tiene como base la fila i–ésima y contenga al elemento (i, j). Puesto que este tratamiento lo aplicaremos a toda la matriz, en algún momento tomaremos la fila base de la submatriz máxima, por lo que tendremos garantías de encontrar el valor máximo mediante este método.

En este momento el lector tiene toda la información necesaria para diseñar un algoritmo que resuelve el problema en un tiempo que está en Θ(rango³).

Ver el listado del programa que resuelve el problema.

Listado del programa (Pascal y C):

Programa Pascal:

program p836;

const
    MAX_N = 25;
    ORD_0 = ord ('0');

type

    TRango  = 1 .. MAX_N;
    TMatriz = array [TRango, TRango] of Integer;

    procedure Calcula_Max_Sub (
            A            : TMatriz;
            rango        : TRango;
            linea_blanca : Boolean);
    var
        i, j                     : TRango;
        k                        : Integer;
        maximo, actual, contador : Integer;
    begin
        maximo := 0;
        for i := 1 to rango do
            for j := 1 to rango do
                if A[i,j] > 0 then
                begin
                    (* contamos al propio [i,j] ya como 1: *)
                    contador := 1;
                    (* ahora contamos los anteriores en la fila i: *)
                    k := j - 1;
                    while k >= 1 do
                        if A[i,k] >= A[i,j] then
                        begin
                            inc (contador);
                            dec (k)
                        end
                        else
                            k := 0;
                    (* y ahora contamos los posteriores en la fila i: *)
                    k := j + 1;
                    while k <= rango do
                        if A[i,k] >= A[i,j] then
                        begin
                            inc (contador);
                            inc (k)
                        end
                        else
                            k := rango + 1;
                    (*
                     * el número de vecinos >= que él mismo multiplicado
                     * por su valor será el número de unos de la submatriz:
                     *)
                    actual := A[i,j] * contador;
                    if actual > maximo then maximo := actual
                end;
                            
        if linea_blanca then writeln;
        writeln (maximo)
    end; (* Calcula_Max_Sub *)

    var
        i, j             : TRango;
        n, ncases, rango : Integer;
        a                : TMatriz;
        salto            : Boolean;
        c                : Char;

begin
    readln (ncases);
    salto := False;

    for n := 1 to ncases do
    begin
        readln;
        rango := 0;
        while not eoln do
        begin
            read (c);
            inc (rango);
            a[1,rango] := ord (c) - ORD_0
        end;
        readln;
        for i := 2 to rango do
        begin
            for j := 1 to rango do
            begin
                read (c);
                if c = '1' then
                    a[i,j] := 1 + a[i-1,j]
                else
                    a[i,j] := 0
            end;
            readln
        end;
        Calcula_Max_Sub (a, rango, salto);
        salto := True
    end
end.

Programa C:

#include 

#define MAX_N	25

int main (void)
{
    int c, nCasos, linea_blanca = 0, rango, i, j, k, contador, actual, maximo;
    int A[MAX_N][MAX_N];

    scanf ("%d", &nCasos);

    while ( nCasos-- ) {
        while ((c = getchar()) == '\n')
            ;
        rango = 0;
        do {
            A[0][rango++] = c - '0';
        } while ((c = getchar()) != '\n');

        for (i = 1; i < rango; i++) {
            for (j = 0; j < rango; j++)
                if (getchar() == '1')
                    A[i][j] = 1 + A[i-1][j];
                else
                    A[i][j] = 0;
            getchar();
        }

        maximo = 0;
        for (i = 0; i < rango; i++ )
            for (j = 0; j < rango; j++ )
                if (A[i][j]) {
                    contador = 1;
                    for (k = j - 1; k >= 0 && A[i][k] >= A[i][j]; k--)
                        contador++;
                    for (k = j + 1; k < rango && A[i][k] >= A[i][j]; k++)
                        contador++;
                    actual = contador * A[i][j];
                    if (actual > maximo) maximo = actual;
                }
        if (linea_blanca) printf ("\n");
        linea_blanca = 1;
        printf ("%d\n", maximo);
    }

    return 0;
}

Olimpiada de programación - Facultad de Informática - Universidad de Murcia