Link al problema: RAINBOWB

Dificultad: Medio

Problema: Dado un número $N$, $1 ≤ N ≤ 10^6$, encontrar todas las maneras posibles de formar un “arreglo arcoiris” de tamaño $N$. Un arrelgo arcoíris contiene todos los números del 1 al 7 ordenados de manera ascendente hasta la mitad del arreglo, mientras que para la otra mitad contiene los la misma cantidad pero ordenados de manera descendente. Este es un ejemplo de un arreglo de ese tipo con $N = 15$: $\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 7,\ 7,\ 6,\ 5,\ 4,\ 3,\ 2,\ 1\}$.

Solución: (Existe solución en $O(1)$ para este problema, sin embargo aquí se expone una solución empleando la programación dinámica)

Primero que nada debemos identificar que podemos trabajar con una sola mitad del arreglo, puesto que la otra es igual. Después debemos identificar que para cada $N$ que nos den existen $R$ números extras (repetidos) que podemos colocar, (en el ejemplo presentado más arriba $R=2$ por eso hay dos $7$ más). Podemos obtener $R/2$ de la siguente manera: aumentando $N$ en uno, dividiéndolo entre dos y a eso restarle $7$, que es la cantidad de elementos distintos en un arreglo arcoíris.

La función de programación dinámica dependerá de dos parámetros, $r$ la cantidad de números repetidos que podemos poner todavía y $n$, el número que estamos poniendo en nuestro arreglo arcoíris.

Sabemos que $1≤n≤7$ , por tanto si en algún momento toma un valor distinto, hemos puesto $7$ números distintos en el arreglo, debemos entonces revisar $r$, si $r=0$ hemos usado todos nuestros números extras y por tanto esa es una manera de formar un arreglo, por el contrario si $r≠0$ llegamos a la mitad de nuestro arreglo sin usar todos nuestros números extras, por tanto esa no es una posibilidad.

Si se cumple que $1≤n≤7$ , de nuevo tenemos que fijarnos en el valor de $r$ para tomar la decisión de repetir un número o no.

Por último, resta llamar a $f(1,R/2)$ para obtener el resultado. No olvides ir aplicando $%$ para mantener tu resultado en un rango correcto.

Pra obtener el preciado AC, tuve que implementar la DP de manera iterativa, ya que recursiva daba RTE

Código:

#include <cstdio>
#define L 7
#define MOD 1000000007
int N;
int m[10][1000010];
int dp(int i, int res){
    for(int ii = 8; ii >= 1; ii--) {
        for(int r = 0; r <= res; r++) {
            if(ii == 8) { 
                if(r) 
                    m[ii][r] = 0; 
                else 
                    m[ii][r] = 1; 
                continue; 
            }
            if(res){
                m[ii][r] = (m[ii][r-1] % MOD 
                                + m[ii+1][r] % MOD) % MOD;
            } else {
                m[ii][r] = m[ii+1][r] % MOD;
            }
        }
    }
    return m[i][res];
}
int main(){
    scanf("%d", &N);
    N++; N /= 2;
    if(N - L < 0) printf("0\n");
    else {
        printf("%d\n", dp(1,N - L) % MOD);
    }   
    return 0;
}

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:

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:

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.

#define place second
#define distance first
typedef std::pair<int,int> frog;

for(int i = 1; i <= N; i++){
 roots[i] = i;
 scanf("%d", &frogs[i].distance);
 frogs[i].place = i;
}
std::sort(frogs+1, frogs+N+1);
for(int i = 1; i < N; i++){
 if(frogs[i + 1].distance - frogs[i].distance <= K){
  join(frogs[i + 1].place, frogs[i].place);
 }
}

root(a) == root(b) ? printf("Yes\n") : printf("No\n");

##+##
1234

struct Group{
 int o; // Original index
 int v; // Value of the group  
 int d; // Digit amount
 int s; // Positive or negative: 1 or -1
 int value(){ // Return the final value
  return s * v;
 }
};

  int n = -1;
  int neg;
  int ii = 0;
  int ix = 0;
  n = G[0].d;
  while(n > 0 && G[0].s > 0){
   for(ix = 0; G[ix].d == n && ix <= p; ix++){
    if(G[ix].s < 0) { break; }
    G[ix].d--;
    G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
    ii++;
   }
   n = G[0].d;
  }

   reverse(nums+ii, nums+k);
   neg = ix;
   n = G[ix].d;
   while(n){
    for(; G[ix].d == n && ix <= p; ix++){
     G[ix].d--;
     G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
     ii++;
    }
    n = G[neg].d;
   }

  int res = 0;
  for(i = 0; i <= p; i++){
   res += G[i].value();
  }
  printf("%d\n", res);

 int dp(int i,int j){
 }

if(i==n)
   return 0;

return max(dp(i+1,j)+piramide[i+1][j],dp(i+1,j+1)+piramide[i+1][j+1]);

res = dp(0,0);
printf("%d\n",res + piramide[0][0]);