Convertir matriz a una ordenada utilizando sólo dos operaciones

Question

he encontrado esta pregunta en un foro en línea: realmente interesado en la forma en que se puede resolver:

Dada una matriz A de enteros positivos. Convierta a una matriz ordenada con un costo mínimo. La única operación válidos son:
1) Disminuir con un costo = 1
2) Eliminar un elemento completamente de la matriz con coste = valor del elemento

Ésta es una pregunta de la entrevista se le preguntó por una empresa de tecnología

Answer 1

NOTA: La respuesta original ha sido reemplazada por una en la que tengo mucha más confianza (y puedo explicarlo también). Ambas respuestas produjeron los mismos resultados en mi conjunto de casos de prueba.

Puede resolver este problema utilizando un enfoque de programación dinámica. La observación clave es que nunca tiene sentido decrementar un número a un valor que no se encuentra en la matriz original. (Prueba informal:. Supongamos que disminuye un número O1 a un valor X que no está en la secuencia original con el fin de evitar la eliminación de un número O2 > X de la secuencia resultado A continuación, puede disminuir O1 a O2 lugar, y reducir el costo por O2-X)

Ahora la solución se vuelve fácil de entender: es un DP en dos dimensiones. Si clasificamos los elementos de los distintos elementos de la secuencia original d en una matriz ordenada s, la longitud de d se convierte en la primera dimensión del DP; la longitud de s se convierte en la segunda dimensión.

Declaramos dp[d.Length,s.Length]. El valor de dp[i,j] es el costo de resolver el subproblema d[0 to i] manteniendo el último elemento de la solución en s[j]. Nota: este costo incluye el costo de eliminar d[i] si es menor que s[j].

La primera fila dp[0,j] se calcula como el coste de recorte d[0] a s[j], o cero si d[0] < s[j]. El valor de dp[i,j] siguiente fila se calcula como el mínimo de dp[i-1, 0 to j] + trim, donde trim es el costo de recorte d[i] a s[j] o d[i] si necesita ser eliminada porque s[j] es más grande que d[i].

La respuesta se calcula como el mínimo de la última fila dp[d.Length-1, 0 to s.Length].

Aquí es una implementación en C#:

static int Cost(int[] d) { 
    var s = d.Distinct().OrderBy(v => v).ToArray(); 
    var dp = new int[d.Length,s.Length]; 
    for (var j = 0 ; j != s.Length ; j++) { 
     dp[0, j] = Math.Max(d[0] - s[j], 0); 
    } 
    for (var i = 1; i != d.Length; i++) { 
     for (var j = 0 ; j != s.Length ; j++) { 
      dp[i, j] = int.MaxValue; 
      var trim = d[i] - s[j]; 
      if (trim < 0) { 
       trim = d[i]; 
      } 
      dp[i, j] = int.MaxValue; 
      for (var k = j ; k >= 0 ; k--) { 
       dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim); 
      } 
     } 
    } 
    var best = int.MaxValue; 
    for (var j = 0 ; j != s.Length ; j++) { 
     best = Math.Min(best, dp[d.Length - 1, j]); 
    } 
    return best; 
} 

Esta aplicación directa tiene la complejidad del espacio O(N^2). Puede reducirlo a O(N) observando que solo se usan dos últimas filas al mismo tiempo.

Answer 2

1. Construya el gráfico de decisión, agregue el vértice de inicio a él. Cada vértice contiene "nivel de recorte", es decir, el valor al que se deben disminuir todos los valores de matriz a la izquierda del nodo actual. El "nivel de ajuste" del vértice de inicio es infinito. Cada borde del gráfico tiene un valor, que corresponde al costo de la decisión.
2. Para cada elemento de la matriz, a partir de la más a la derecha, realice los pasos 3 .. 5.
3. para cada vértice de la hoja, realice los pasos 4 .. 5.
4. Crear hasta 2 bordes salientes, (1) con el el costo de eliminar el elemento de matriz y (2) con el costo de recortar todos los elementos a la izquierda (exactamente, el costo de disminuir el "nivel de recorte").
5. Conecte estos bordes a los vértices recién creados, un vértice para cada elemento de la matriz y cada "nivel de recorte".
6. Encuentra la ruta más corta desde el vértice de inicio hasta uno de los vértices, correspondiente al elemento de la matriz más a la izquierda. La longitud de esta ruta es igual al costo de la solución.
7. Disminuye y elimina elementos de matriz de acuerdo con el gráfico de decisión.

Este algoritmo se puede tratar como una optimización del enfoque de fuerza bruta. Para la búsqueda de fuerza bruta, comenzando desde el elemento de la matriz más a la derecha, construye el árbol de decisión binario. Cada vértice tiene 2 bordes de salida, uno para la decisión de "eliminar", otra decisión de "recorte". El costo de la decisión está asociado con cada borde. El "nivel de recorte" está asociado a cada vértice. La solución óptima está determinada por el camino más corto en este árbol.

Elimine cada ruta, que obviamente no es óptima. Por ejemplo, si el elemento más grande es el último en la matriz, la decisión de "recortar" ha costado cero, y la decisión de "eliminar" no es óptima. Eliminar ruta, a partir de esta decisión de "eliminar". Después de esta optimización, el árbol de decisión es más disperso: algunos vértices tienen 2 bordes salientes, algunos, solo uno.

En cada nivel de profundidad, el árbol de decisión puede tener varios vértices con el mismo "nivel de recorte". Los subárboles, a partir de estos vértices, son idénticos entre sí. Esa es una buena razón para unir todos estos vértices a un vértice. Esto transforma el árbol en un gráfico que tiene como máximo n /2 vértices.

implementación más simple de este algoritmo es O (n), porque para cada uno de los O (n) vértices que calcula el recorte de coste iterativamente, en O Complejidad de tiempo (n) .

Los cálculos de costos de recorte repetidos no son necesarios si hay memoria suficiente para almacenar todos los resultados del costo de recorte parcial. Esto puede requerir O (n) o incluso O (n) espacio.

Con dicha optimización, este algoritmo es O (n). Debido a la estructura simple del gráfico, la búsqueda de ruta más corta tiene O (n) complejidad, no O (n * log (n)).

C++ 11 aplicación (tanto en el espacio y el tiempo la complejidad es O (n 2 )):

//g++ -std=c++0x 
#include <iostream> 
#include <vector> 
#include <algorithm> 

typedef unsigned val_t; 
typedef unsigned long long acc_t; // to avoid overflows 
typedef unsigned ind_t; 
typedef std::vector<val_t> arr_t; 

struct Node 
{ 
    acc_t trimCost; 
    acc_t cost; 
    ind_t link; 
    bool used; 

    Node() 
    : trimCost(0) 
    , used(false) 
    {} 
}; 

class Matrix 
{ 
    std::vector<Node> m; 
    ind_t columns; 

    public: 
    Matrix(ind_t rows, ind_t cols) 
    : m(rows * cols) 
    , columns(cols) 
    {} 

    Node& operator() (ind_t row, ind_t column) 
    { 
    return m[columns * row + column]; 
    } 
}; 

void fillTrimCosts(const arr_t& array, const arr_t& levels, Matrix& matrix) 
{ 
    for (ind_t row = 0; row != array.size(); ++row) 
    { 
    for (ind_t column = 0; column != levels.size(); ++column) 
    { 
     Node& node = matrix(row + 1, column); 
     node.trimCost = matrix(row, column).trimCost; 

     if (array[row] > levels[column]) 
     { 
     node.trimCost += array[row] - levels[column]; 
     } 
    } 
    } 
} 

void updateNode(Node& node, acc_t cost, ind_t column) 
{ 
    if (!node.used || node.cost > cost) 
    { 
    node.cost = cost; 
    node.link = column; 
    } 
} 

acc_t transform(arr_t& array) 
{ 
    const ind_t size = array.size(); 

    // Sorted array of trim levels 
    arr_t levels = array; 
    std::sort(levels.begin(), levels.end()); 
    levels.erase(
    std::unique(levels.begin(), levels.end()), 
    levels.end()); 

    // Initialize matrix 
    Matrix matrix(size + 1, levels.size()); 
    fillTrimCosts(array, levels, matrix); 
    Node& startNode = matrix(size, levels.size() - 1); 
    startNode.used = true; 
    startNode.cost = 0; 

    // For each array element, starting from the last one 
    for (ind_t row = size; row != 0; --row) 
    { 
    // Determine trim level for this array element 
    auto iter = std::lower_bound(levels.begin(), levels.end(), array[row - 1]); 
    const ind_t newLevel = iter - levels.begin(); 

    // For each trim level 
    for (ind_t column = 0; column != levels.size(); ++column) 
    { 
     const Node& node = matrix(row, column); 
     if (!node.used) 
     continue; 

     // Determine cost of trimming to current array element's level 
     const acc_t oldCost = node.trimCost; 
     const acc_t newCost = matrix(row, newLevel).trimCost; 
     const acc_t trimCost = (newCost > oldCost)? newCost - oldCost: 0; 

     // Nodes for "trim" and "delete" decisions 
     Node& trimNode = matrix(row - 1, newLevel); 
     Node& nextNode = matrix(row - 1, column); 

     if (trimCost) 
     { 
     // Decision needed, update both nodes 
     updateNode(trimNode, trimCost + node.cost, column); 
     updateNode(nextNode, array[row - 1] + node.cost, column); 
     trimNode.used = true; 
     } 
     else 
     { 
     // No decision needed, pass current state to the next row's node 
     updateNode(nextNode, node.cost, column); 
     } 

     nextNode.used = true; 
    } 
    } 

    // Find optimal cost and starting trim level for it 
    acc_t bestCost = size * levels.size(); 
    ind_t bestLevel = levels.size(); 
    for (ind_t column = 0; column != levels.size(); ++column) 
    { 
    const Node& node = matrix(0, column); 
    if (node.used && node.cost < bestCost) 
    { 
     bestCost = node.cost; 
     bestLevel = column; 
    } 
    } 

    // Trace the path of minimum cost 
    for (ind_t row = 0; row != size; ++row) 
    { 
    const Node& node = matrix(row, bestLevel); 
    const ind_t next = node.link; 

    if (next == bestLevel && node.cost != matrix(row + 1, next).cost) 
    { 
     array[row] = 0; 
    } 
    else if (array[row] > levels[bestLevel]) 
    { 
     array[row] = levels[bestLevel]; 
    } 

    bestLevel = next; 
    } 

    return bestCost; 
} 

void printArray(const arr_t& array) 
{ 
    for (val_t val: array) 
    if (val) 
     std::cout << val << ' '; 
    else 
     std::cout << "* "; 
    std::cout << std::endl; 
} 

int main() 
{ 
    arr_t array({9,8,7,6,5,4,3,2,1}); 
    printArray(array); 

    acc_t cost = transform(array); 
    printArray(array); 
    std::cout << "Cost=" << cost << std::endl; 

    return 0; 
} 

Answer 3

Estoy asumiendo que "ordenadas" significa valores más pequeños en el inicio de la array, dada la naturaleza de las operaciones permitidas.

El límite de rendimiento entre las dos operaciones se produce cuando el costo de eliminar un elemento fuera de secuencia es igual al costo de disminuir todos los elementos de mayor valor hasta el delincuente incluido, o eliminar todos los elementos de menor valor después El ofensor. Puede elegir entre disminuir elementos precedentes o eliminar elementos posteriores en función de por qué el elemento infractor está fuera de secuencia. Si es menor que el elemento anterior, considere disminuir los elementos anteriores; si es mayor que el siguiente elemento, considere eliminar elementos posteriores.

Algunos ejemplos:

10 1 2 3 4 5 

Decremento de 10 a 1, el costo 9.

1 2 3 4 10 4 

Eliminar 4, cuestan 4.

1 2 3 4 10 5 

Eliminar 5 o disminuir 10 a 5, costará 5.

5 6 7 8 1 10 

Remove 1, cuesta 1.

5 6 7 8 6 10 

Decremento 7 y 8 a 6, costó 3.

2 1 1 4 2 4 4 3 

Decremento la primera 1, la primera 4 por dos, y los otros dos a cuatro patas una vez cada uno, costo 5.

La implementación más sencilla de encontrar las soluciones basa en tener liberar el conocimiento, por lo que es muy ineficiente. Afortunadamente, la pregunta no se preocupa por eso. La idea es recorrer el conjunto y tomar la decisión de eliminar o disminuir para fijar el conjunto cuando se encuentra un elemento fuera de secuencia. Una implementación mucho más eficiente de esto sería usar totales acumulados (a diferencia de calcular métodos) y recorrer la matriz dos veces, hacia adelante y hacia atrás. He escrito una maqueta de la versión más simple, ya que creo que es más fácil de leer.

Pseudocódigo, vuelve coste total:

if array.Length < 2 : return 0; // no sorting necessary 

resultArray = array.Copy(); 
int cost = 0; 

for i = 0 to array.Length - 1 : 

if i > 0 and array[i-1] > array[i] : 

if CostToDecrementPreviousItems(i, array[i]) > array[i]) : 
resultArray[i] = -1; 
cost += array[i]; 
else : 
cost += DecrementItemsThroughIndexGreaterThanValue(resultArray, i, array[i]); 
end if 

else if i < array.Length - 1 and array[i+1] < array[i] : 

if CostToRemoveLaterItems(i, array[i]) > array[i] : 
resultArray[i] = -1; 
cost += array[i]; 
else : 
cost += RemoveItemsAfterIndexGreaterThanValue(resultArray, i, array[i]); 
end if 

end if 
end for 

RemoveNegativeElements(resultArray); 
array = resultArray; 

return cost; 

esperemos que la llamadas a métodos definidos son explica por sí mismo.