Minimum Cost of Ropes

Q: ¿Cuál es la complejidad temporal de Minimum Cost of Ropes?

Tiempo O(n log n) y espacio O(n) con un montículo mínimo: n-1 uniones, cada una con tres operaciones de montículo de O(log n) . En cambio, recorrer todo el montón para encontrar las dos cuerdas más cortas lo hace O(n²) .

FácilMontículo Voraz

+10

Tienes algunas cuerdas, y ropes[i] es la longitud de la cuerda i. Puedes unir dos cuerdas cualesquiera para formar una sola cuerda cuya longitud sea la suma de las dos, y esa unión cuesta esa misma suma. Sigue uniendo cuerdas hasta que quede una sola.

Escribe una función llamada minCostRopes que devuelva el costo total mínimo de unir todas las cuerdas en una sola, o 0 si solo hay una cuerda desde el principio.

Función

minCostRopes(ropes: integer-array) → integer

ropesinteger-array: la longitud de cada cuerda
Devuelveinteger: el costo total mínimo de unir todas las cuerdas en una sola

Restricciones

1 ≤ ropes.length ≤ 10⁴
1 ≤ ropes[i] ≤ 100
La respuesta cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: ropes = [5, 2, 8, 3]
Salida: 33
Explicación: Une 2 y 3 para obtener 5, las dos cuerdas de longitud 5 para obtener 10, después 8 y 10 para obtener 18. El total es 5 + 10 + 18 = 33.

Entrada: ropes = [1, 1, 1, 1]
Salida: 8
Explicación: Une los 1 en pares por 2 cada uno, después une las dos cuerdas de longitud 2 por 4: 8 en total. Añadir cada 1 a una cuerda que va creciendo costaría 2 + 3 + 4 = 9.

Para ir más allá

Supongamos que una unión puede atar hasta tres cuerdas y cuesta la longitud total de estas. ¿Cómo cambia la regla voraz cuando el número de cuerdas no se puede dividir equitativamente?

Solución

Cada unión cuesta la longitud total de ambas piezas, así que una cuerda que se une pronto se vuelve a pagar en cada unión posterior de la que forma parte. Deja las cuerdas largas fuera de las primeras uniones: une las dos cuerdas más cortas en cada ronda. Un montículo mínimo encuentra esas dos en O(log n).

Busca las dos más cortas en cada ronda

Correcto, pero no termina con las pruebas más grandes

Intuición

En cada ronda, busca en el montón la cuerda más corta y sácala, vuelve a buscar la siguiente más corta y coloca de nuevo la unión de ambas.

¿Por qué las dos más cortas? Dibuja las uniones como un árbol con las cuerdas como hojas. La longitud de una cuerda se paga una vez por cada unión que hay por encima de ella, es decir, según su profundidad. El nivel más profundo tiene dos hojas una junto a la otra, y colocar allí las dos cuerdas más cortas nunca aumenta el costo. Así que algún plan de costo mínimo une primero las dos cuerdas más cortas, y el argumento se repite con el montón más pequeño.

Hay n-1 rondas de dos recorridos completos: O(n²), unas 10^8 comparaciones para 10^4 cuerdas.

Algoritmo

Copia las cuerdas en una lista de trabajo, pile, y empieza total en 0.
Repite hasta que quede una sola cuerda: encuentra la cuerda más corta y elimínala moviendo la última cuerda a su lugar.
Haz lo mismo de nuevo para obtener la siguiente cuerda más corta.
Suma las dos longitudes a total y añade a la pila una cuerda de esa longitud.
Devuelve total.

def minCostRopes(ropes):
    pile = list(ropes)

    def take_shortest():
        k = 0
        for i in range(1, len(pile)):
            if pile[i] < pile[k]:
                k = i
        pile[k], pile[-1] = pile[-1], pile[k]  # move it to the end, then remove it
        return pile.pop()

    total = 0
    while len(pile) > 1:
        joined = take_shortest() + take_shortest()
        total += joined
        pile.append(joined)
    return total

Montículo mínimo

Intuición

Un montículo mínimo mantiene la cuerda más corta en su raíz, y extraer la raíz o insertar una cuerda cuesta O(log n). Una ronda consiste en dos extracciones, que te dan las dos cuerdas más cortas, y una inserción de la cuerda unida.

n cuerdas necesitan n-1 uniones de tres operaciones del montículo cada una, así que el tiempo es O(n log n): aproximadamente 4 × 10^5 pasos para 10^4 cuerdas. El montículo nunca contiene más de n cuerdas.

Algoritmo

Coloca la longitud de cada cuerda en un montículo mínimo y establece total = 0.
Repite hasta que quede una cuerda: extrae las dos más cortas.
Suma su total a total y vuelve a insertar la suma en el montículo.
Devuelve total, que permanece en 0 cuando solo había una cuerda.

import heapq


def minCostRopes(ropes):
    heap = list(ropes)
    heapq.heapify(heap)  # a min-heap: heap[0] is the shortest rope
    total = 0
    while len(heap) > 1:
        joined = heapq.heappop(heap) + heapq.heappop(heap)
        total += joined
        heapq.heappush(heap, joined)
    return total

Errores comunes y casos límite

Ordenar una vez y añadir cada cuerda a una cuerda acumulada. La cuerda acumulada puede crecer más que las cuerdas que aún no has usado: para [2, 3, 4, 4] cuesta 5 + 9 + 13 = 27, mientras que unir las dos más cortas cuesta 5 + 8 + 13 = 26.
Retirar la cuerda unida. Su longitud vuelve a la pila y se paga de nuevo en una unión posterior.
Devolver la longitud de la cuerda final. Para [5, 2, 8, 3], la última cuerda mide 18, pero el costo es 33.
Usar por accidente un montículo máximo. priority_queue de C++ y BinaryHeap de Rust entregan el valor más grande, a menos que inviertas el orden.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Minimum Cost of Ropes?

Tiempo O(n log n) y espacio O(n) con un montículo mínimo: n-1 uniones, cada una con tres operaciones de montículo de O(log n). En cambio, recorrer todo el montón para encontrar las dos cuerdas más cortas lo hace O(n²).

¿Es el costo mínimo de las cuerdas lo mismo que la codificación de Huffman?

Sí, es el mismo algoritmo. La codificación de Huffman construye un código de prefijos fusionando una y otra vez los dos símbolos menos frecuentes, y minimiza la suma de cada frecuencia multiplicada por su profundidad en el árbol. Aquí las cuerdas representan los símbolos y sus longitudes representan las frecuencias, así que el costo total es esa misma suma.

¿Se puede resolver Minimum Cost of Ropes sin un montículo?

Sí, con dos colas. Ordena las cuerdas en una cola y agrega cada cuerda unida al final de una segunda. Las cuerdas unidas salen en orden no decreciente, así que la cuerda más corta que queda está al frente de una de las colas. Cada ronda es entonces O(1) y, con longitudes de hasta 100, un ordenamiento por conteo hace que la ejecución sea O(n).

def minCostRopes(ropes):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

ropes = [5, 2, 8, 3]

Salida Esperada