Algunas personas mencionan que es una buena copia y pegue desde aquí. Encuentre el elemento máximo en cualquier submatriz de matriz, pero antes de decir eso, verifíquelo. Usuario sudoer esta también es mi cuenta.
_______________________________________________________
Un enfoque de algoritmo de tabla dispersa : –
- ¿Cómo implemento un árbol N-ary en C?
- Tengo conocimiento de estructuras de datos y algoritmos, pero me falta programación competitiva, ¿cómo debo mejorar? ¿Puedo sobrevivir a la competencia de hoy?
- ¿Puede [math] \ sqrt {n} ^ 2 = -n [/ math]?
- ¿Cuáles son algunos algoritmos del mundo real que corresponden al 'caso 3' del método maestro?
- Dado un gráfico de N vértices con m1 bordes unidireccionales y m2 bordes bidireccionales, ¿cómo podemos dirigir los bordes bidireccionales de modo que no tengamos ninguna caminata cerrada?
Tiempo de precomputación : O( N x M x log(N) x log(M))
Tiempo de consulta – O(1)
Para comprender este método, debe tener conocimiento de cómo encontrar RMQ utilizando un algoritmo de tabla disperso.
Podemos usar [math] 2D [/ math] Algoritmo de tabla dispersa para encontrar la consulta mínima de rango.
Lo que hacemos en One Dimension: –
preprocesamos RMQ para sub matrices de longitud [matemática] 2 ^ k [/ matemática] usando programación dinámica. Mantendremos una matriz M[0, N-1][0, logN] donde M[i][j] es el índice del valor mínimo en la matriz secundaria que comienza en i .
Para calcular M[i][j] debemos buscar el valor mínimo en la primera y segunda mitad del intervalo. Es obvio que las piezas pequeñas tienen una longitud [matemática] 2 ^ (j – 1) [/ matemática], por lo que el pseudocódigo para el cálculo es: –
if (A [M [i] [j-1]] <A [M [i + 2 ^ (j-1) -1] [j-1]])
M [i] [j] = M [i] [j-1]
más
M [i] [j] = M [i + 2 ^ (j-1) -1] [j-1]
Aquí A es una matriz real que almacena valores. Una vez que tenemos estos valores preprocesados, vamos a mostrar cómo podemos usarlos para calcular RMQ (i, j) . La idea es seleccionar dos bloques que cubran completamente el intervalo [i..j] y encontrar el mínimo entre ellos. Deje k = [log(j - i + 1)] . Para calcular RMQ (i, j) podemos usar la siguiente fórmula: –
si (A [M [i] [k]] <= A [M [j – 2 ^ k + 1] [k]])
RMQ (i, j) = A [M [i] [k]]
más
RMQ (i, j) = A [M [j – 2 ^ k + 1] [k]]
Para 2 dimensiones: –
De manera similar, también podemos extender la regla anterior para 2 Dimension, aquí preprocesamos RMQ para la submatriz de longitud [matemática] 2 ^ K, 2 ^ L [/ matemática] usando programación dinámica y mantenemos una matriz M[0,N-1][0, M-1][0, logN][0, logM] . Donde M[x][y][k][l] es el índice del valor mínimo en la submatriz que comienza en [x , y] y tiene una longitud de 2^K, 2^L respectivamente.
El seudocódigo para el cálculo M[x][y][k][l] es: –
M [x] [y] [i] [j] = GetMinimum (M [x] [y] [i-1] [j-1], M [x + (2 ^ (i-1))]] [y ] [i-1] [j-1], M [x] [y + (2 ^ (j-1))] [i-1] [j-1], M [x + (2 ^ (i-1 ))] [y + (2 ^ (j-1))] [i-1] [j-1])
Aquí la función GetMinimum devolverá el índice del elemento mínimo de los elementos proporcionados. Ahora que hemos preprocesado, veamos cómo calcular RMQ (x, y, x1, y1) . Aquí [x, y] punto inicial de la submatriz y [x1, y1] representan el punto final de la submatriz significa el punto inferior derecho de la submatriz. Aquí tenemos que seleccionar cuatro bloques de submatrices que cubran completamente [x, y, x1, y1] y encontrar el mínimo de ellos. Dejar
k = [log(x1 - x + 1)] & l = [log(y1 - y + 1)] . Para calcular RMQ (x, y, x1, y1) podemos usar la siguiente fórmula:
RMQ (x, y, x1, y1) = GetMinimum (M [x] [y] [k] [l], M [x1 – (2 ^ k) + 1] [y] [k] [l], M [x] [y1 – (2 ^ l) + 1] [k] [l], M [x1 – (2 ^ k) + 1] [y1 – (2 ^ l) + 1] [k] [l] );
Pseudocódigo para la lógica anterior: –
# recuerde el índice de almacenamiento de la matriz ‘M’ de la matriz real ‘P’, de modo que para comparar valores en la función GetMinimum compare los valores de la matriz ‘P’ no de la matriz ‘M’
SparseMatrix (n, m) {
para i = 0 a 2 ^ i <= n:
para j = 0 a 2 ^ j <= m:
para x = 0 a x + 2 ^ i -1 <n:
para y = 0 a y + (2 ^ j) -1 <m:
si i == 0 y j == 0:
M [x] [y] [i] [j] = Par (x, y) # almacenar x, y
más si i == 0:
M [x] [y] [i] [j] = GetMinimum (M [x] [y] [i] [j-1], M [x] [y + (2 ^ (j-1))]] [i ] [j-1])
más si j == 0:
M [x] [y] [i] [j] = GetMinimum (M [x] [y] [i-1] [j], M [x + (2 ^ (i-1))] [y] [i -1] [j])
más
M [x] [y] [i] [j] = GetMinimum (M [x] [y] [i-1] [j-1], M [x + (2 ^ (i-1))]] [y ] [i-1] [j-1],
M [x] [y + (2 ^ (j-1))] [i-1] [j-1], M [x + (2 ^ (i-1))] [y + (2 ^ (j-1) ))] [i-1] [j-1]);
}
RMQ (x, y, x1, y1) {
k = log (x1 – x + 1)
l = log (y1 – y + 1)
ans = GetMinimum (M [x] [y] [k] [l], M [x1 – (2 ^ k) + 1] [y] [k] [l], M [x] [y1 – (2 ^ l) + 1] [k] [l], M [x1 – (2 ^ k) + 1] [y1 – (2 ^ l) + 1] [k] [l]);
devuelve P [ans-> x] [ans-> y] # ans-> x representa el número de fila retenido en ans y de forma similar ans-> y representa el almacén de columnas en ans
}
