¡Programa conmigo! ep 50: Cards Permutation (Hackerrank)

En este episodio vamos a dejar Rust de lado un momento para centrarnos en un problema muy duro de Hacker Rank que no he conseguido resolver completamente: https://www.hackerrank.com/challenges...

Veremos algunos conceptos nuevos interesantes como las bases factoriales ¡y MUCHA combinatoria!

Al final del episodio se me pasa comentar que la otra estrategia prometedora para resolverlo puede ser utilizando programación dinámica, si podemos expresar el valor que aporta cada columna en base a las anteriores...

0:00 repaso del episodio anterior y anuncio
1:56 presentación del problema
4:30 "solución" por fuerza bruta calculando todas las permutaciones
8:35 solución por fuerza bruta, permutando comodines
9:19 representación factorial de las permutaciones
10:25 código Lehmer de la permutación (tabla de inversiones)
15:36 optimización: podemos agrupar permutaciones que tienen el mismo valor
18:05 fórmulas combinatorias para contar inversiones
24:14 estimamos la complejidad del algoritmo
25:04 nota sobre la complejidad de la aritmética de precisión arbitraria
25:40 caché de factoriales y combinaciones
26:40 atajo aritmético para un caso especial con todo comodines
28:54 resumen y despedida