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.
$$ f(n,r) = \left\{ \begin{array}{ll} 1 & \mbox{if } n = 8\ and\ r = 0 \\ 0 & \mbox{if } n = 8\ and\ r \neq 0 \\ f(n,r-1) + f(n+1,r) & \mbox{if } r \neq 0 \\ f(n+1,r) & \mbox{if } r = 0 \\ \end{array} \right. $$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;
}
