Link del problema: 2958 - Almost Complete Binary Tree
Dificultad: Medio
Información:
Un Árbol Binario Completo es un árbol binario en donde en cada nivel, excepto quizá en el último está completamente lleno, es decir, todos los nodos tienen dos hijos excepto en las hojas y además éstas hojas están lo más a la izquierda posible. Por ejemplo:
Sabiendo esto, si no está ni lleno ni con las hojas lo más a la izquierda posible, le podemos llamar un Árbol Binario Casi Completo. Como en el siguiente ejemplo:
Problema:
Dada una $1<=N<=3000$ como la cantidad de nodos totales de nuestro árbol, digamos ¿cuantos Árboles Binarios Casi Completos se pueden formar? Se piden $1<= T <=100$ casos de prueba.
Primero debemos preguntarnos por donde atacar este problema...
Veámos un ejemplo
Veámos un ejemplo
Supongamos que tenemos una N = 4 o sea un árbol de 4 nodos y las diferentes combinaciones con 4 nodos pueden ser las siguientes:
Árbol 1:
Árbol 2:
Árbol 3:
Árbol 4:
Entonces tenemos todas las maneras de poder formar árboles con 4 Nodos pero si logramos observar en el Árbol 1 se cumple la condición de que sea un Árbol Binario Completo (lo cual no deseamos) puesto que tenemos las hojas lo más a la izquierda posible entonces ese árbol no se considera como solución y para N = 4 la respuesta de todos los Árboles Binarios Casi Completos es 3 (las tres últimas imágenes).
Si bien este problema podría verse con una solución con dp (Dynamic Programming) la solución que pude ver de inicio fue con combinatoria, no fue hasta hoy que en el Club de Algoritmia de mi escuela pude corroborar con el gran Edgar (Garo) que se podía resolver de ambas formas, por esta ocasión lo explicare con combinatoria.
Solución:
La idea es llegar al nivel en el árbol al número de nodos donde nos excedamos de nuestro número N para así poder contar sobre los nodos de ese nivel, de cuantas formas podemos acomodar los nodos que nos falte poner, vamos a ejemplificar con la misma N = 4.
Tomando el primer nivel donde nos excedamos de nuestra N = 4 el árbol quedaría así:
Figura 1
Un nivel anterior a este podemos ver que se pueden poner 3 nodos de la siguiente manera:
Figura 2
Pero nos faltaría 1 nodo para que se cumpliera nuestra N = 4 entonces debemos de ver de cuantas formas posibles se puede acomodar con 4 posiciones las cuales se mostraron en la Fig. 1
Si regresamos a las figuras del inicio de los 4 árboles podemos observar las diferentes formas de poner el nodo que nos falta pero tendríamos que descartar la forma de poner un nodo lo más a la izquierda posible entonces nuestra fórmula se reduciría a obtener las combinaciones de los nodos que nos faltan por poner encima de todas las que podemos poner, menos uno.
Así sería la respuesta nCr - 1 (n combina r menos uno) siendo n las formas de ponerlo, r los que nos faltan poner y el "-1" la que está lo más a la izquierda.
Entonces para calcular las combinaciones tendríamos la fórmula
n!
--------
r! (n-r)!
Pero calcular los factoriales tendría varios inconvenientes el desborde de las variables y que no suele ser tan eficiente ya que la complejidad sería O(n + r + n-r) o O(n) y además como tenemos varios casos por cada caso tendríamos que hacer este proceso.
Una de las formas óptimas sería hacer un precálculo de todas las combinaciones con el Triangulo de Pascal para el calculo de los coeficientes polinomiales y bastaría con tener los números para hacer la combinación antes dichos y buscar esas posiciones en la matriz donde calculamos el triangulo de pascal.
0 1 2 3 4 5
---------------
0|1
1|1 1
2|1 2 1
3|1 3 3 1
4|1 4 6 4 1
5|1 5 10 10 5 1
Siendo que tendríamos que obtener 4C1 iríamos a la fila 4 columna 1, la cuál tiene un valor de 4 y como tenemos que quitarle 1 por la que está más a la izquierda nuestra respuesta sería 3.
Bien implementado nos tendría que dar siempre la respuesta.
Aquí insertaré el código de como programé mi triangulo de pascal:
int k=1; for(int i=0;i<3001 1="" for="" i-1="" i="" if="" int="" j-1="" j="" k="" mat="" mod="" pre="">A eso solo tendrían que conseguir los elementos a combinar que es el último nivel del árbol y la resta de cuantos nodos son o sea N menos cuantos nodos hay un nivel anterior, y mandaríamos llamar a la respuesta en:printf("%lld\n",mat[(p-1)%mod][(res2)%mod]-1);Cabe decir que el cálculo del triangulo de pascal es una especie de tabla dinámica de dp.Por esta ocasión fue todo y si necesitan un tema o problema no duden en sugerirlo.Complejidad: La complejidad se reduciría a calcular el nivel del árbol el cual es O(log n) donde sobrepasa a nuestra N y el calculo de la matriz de pascal que aproximadamente es O(3000^2) pues a lo más nos piden 3000 nodos.
No hay comentarios on "2958 - Almost Complete Binary Tree (COJ)"