Guión del Vídeo

1. Enunciado.
2. Establecer relación entre el problema dado y el enunciado de LeetCode.
   1. Resolverlo usando el clásico mecanismo de dos tiempos: primero pensando y luego tecleando.
   2. Mostrar lista de invitados a la fiesta numerados, listar estilos musicales.
   3. Mapeo de estilos a números.
   4. Establecer relación con el enunciado del LeetCode.
3. Solución en n^2.
   1. Explicar.
   2. Análisis temporal y espacial.
   3. Implementar.
4. Ver el problema como agrupación de invitados en sus géneros según van llegando.
   1. Explicar creando grupos y moviendo a los músicos en cada grupo.
   2. Análisis temporal y espacial.
   3. Implementar con diccionario y con lista.
5. Solución matemática, la solución más friki.

Enunciado

Imagina que eres el director de una influyente discográfica y estás organizando una épica fiesta al más puro estilo del icónico Studio 54. El objetivo de esta extravagante velada es que los músicos asistentes tengan la oportunidad de establecer conexiones y desencadenar fascinantes colaboraciones.

Los músicos invitados son puristas apasionados de sus respectivos géneros musicales y han establecido una regla vital: solo aceptarán colaborar con músicos que compartan su mismo género. Además, las colaboraciones se limitan a dúos, sin permitir agrupaciones de tres o más músicos.

Tu misión es calcular la cantidad de posibles colaboraciones únicas que podrían brotar entre músicos del mismo género. Cuando hablamos de "colaboraciones únicas", nos referimos a que si el músico A colabora con el músico B, la colaboración inversa de B con A no debe contabilizarse nuevamente.

Por ejemplo, considera que en la fiesta hay 3 cantantes de hip-hop, 2 músicos de rock y 1 músico de jazz. El músico de jazz no puede entablar colaboraciones por la ausencia de otros músicos de su género. Los dos músicos de rock pueden formar un dúo entre sí. Los cantantes de hip-hop tienen la capacidad de configurar 3 dúos únicos, sumando así un total de 4 colaboraciones.

¿Eres capaz de desarrollar un algoritmo ingenioso para calcular el número total de colaboraciones que la animada fiesta podría potenciar?

Otro Enunciado

En el vídeo sólo se expone el enunciado de los músicos, pero existen otras formas originales de plantear este problema. Ahí va otra idea, esta vez ambientada en la política.

Imagina encontrarte en una convención política, donde los políticos se congregan en un amplio salón. La hostilidad política es tan pronunciada en este contexto que cada político solo está dispuesto a estrechar la mano de aquellos que comparten su misma partido.

Debes calcular la cantidad mínima de estrechamientos de manos necesarios para que todos los miembros de un mismo partido se saluden mutuamente en medio de esta tensa reunión política.

Soluciones

Solución 1 - Bucles Anidados

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums)):
	        for j in range(len(nums)):
		        if i < j and nums[i] == nums[j]:
			        count += 1

Complejidad temporal $\mathcal{O}(n^2)$ y complejidad espacial $\mathcal{O}(1)$.

Esta solución se puede mejorar ligeramente si limitamos las iteraciones del bucle j.

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        count = 0
        for i in range(len(nums)):
	        for j in range(i+1, len(nums)):
		        if nums[i] == nums[j]:
			        count += 1

Si ejecutamos esta solución en LeetCode veremos que hemos reducido sustancialmente el tiempo de ejecución, pero ¿hemos mejorado la complejidad temporal? Se podría decir que la mejora de esta última solución es una forma de disminuir la constante que multiplica al término predominante, hemos pasado de $\mathcal{O}(C{n}^2)$ a $\mathcal{O}(\frac{C}{2}{n}^2)$. En el análisis de algoritmos las constantes se ignoran, por lo que la complejidad temporal de esta nueva implementación es exactamente la misma que la solución anterior.

Solución 2 - Diccionario de Counts

Esta implementación se puede mejorar un poquito más usando una lista en lugar de un diccionario. Esto es posible debido a que las restricciones del enunciado nos dicen que 1 <= nums[i] <= 100, por lo que bastaría con crear una lista de 100 elementos para llevar la cuenta de colaboraciones entre músicos del mismo estilo musical.

class Solution:
    def numIdenticalPairs(self, nums: List[int]) -> int:
        counts = [0] * 101
        count = 0
        for i in nums:
            count += counts[i]
            counts[i] += 1
        return count

Solución 3 - Friki de las Matemáticas

Se puede resolver utilizando Combinaciones de Pares. Al mismo tiempo, si puede ser resuelto con combinaciones de pares puede ser resuelto con Combinaciones, que no son más que un caso más general de las combinaciones de pares.