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;
}

 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]);

Para resolver este problema trazaremos las rectas (imaginariamente) desde todos los puntos que pueden existir en la cuadrícula hacia el origen. Dichas rectas, además de pasar siempre por el origen, la coordenada $(x_2 = 0, y_2 = 0)$, también deberán pasar por el punto $(x_1 = x, y_2 = y)$ donde $0 ≤ x, y ≤ N$. Recordemos la ecuación de la recta: $(x_2 - x_1) / (y_2 - y_1) + b$, por tanto para nuestras rectas la ecuación se reducirá a $x / y$.

Podemos ver que algo sucede con los puntos que no son visibles, y es que la recta que los une puede ser expresada por un múltiplo de la recta de uno que si es visible. El caso más sencillo: tomando el punto visible $(1, 1)$ y el punto no visible $(3, 3)$, tenemos que las coordenadas del punto no visible es tan solo $(3 * 1) / (3 * 1)$, la forma para identificar esto es obtener el MCD de $x$ y $y$, mientras que para el punto visible $MCD(x, y) = 1$, para el no visible $MCD(x, y) > 1$.

Ahora solo hay que obtener todos los puntos dentro de nuestra cuadrícula cuyo MCD sea igual a 1 para cada consulta que nos hagan. Esto es sencillo pero es un gasto inecesario de recursos, por lo que lo mejor es realizar un precálculo partiendo de que para $N = 0$ la respuesta es $0$ y para $N = 1$ la respuesta es $3$. Otro punto a considerar es que podemos solo calcular la mitad de los puntos ya que los puntos son simétricos.

a[0] = 0;
a[1] = 3;
for(int x = 2; x <= 1000; x++){
 int sum = 0;
 for(int y = 1; y < x; y++){
  if(mcd(x,y) == 1) sum++;
 }
 a[x] = a[x-1] + 2 * sum;
}