P1: ¿Cuántos conjuntos son posibles a partir de una array de tamaño n, tal que cada número del conjunto divide al número consecutivo del conjunto? Puede usar un valor solo una vez en un conjunto particular.
Enfoque: ordenar la array de entrada, iterar en la array de entrada e iterar a través de los divisores de A[i] y agregar los dp[divsors] a dp[A[i]]
Edge Case: cuando la array contiene cero, no itere a través de ceros y la respuesta será 2 * ans + 1
Q2: Dado un árbol. Una señal comienza en la raíz en el tiempo t=0, cada segundo cada Node que tiene la señal puede pasarla a uno de sus hijos y la señal persiste, calcule el tiempo mínimo para que todos los Nodes del árbol tengan la señal.
Enfoque: se puede resolver con dfs+dp, si las respuestas a todos los hijos de un Node se ordenan en orden descendente, la respuesta al Node será como máximo (ans[hijo]+i+1, ans[Node]) , donde i es el índice del hijo, y la respuesta para el Node hoja será 1 como caso base.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA