Problema Two Knights


#1

Hola,
estoy resolviendo este problema.
Mi solución es la siguiente:

Resumen
#include<bits/stdc++.h>

using namespace std;

#define tint long long
#define forsn(i, s, n) for(tint i=s;i<int(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) (v.begin(), v.end())

tint numeroCombinatorio(tint n, tint k){
 if(k==0 || k==n) return 1;
 return numeroCombinatorio(n-1, k)+numeroCombinatorio(n-1, k-1);
}

int main(){ 
 tint n; cin >> n;
 forn(i, n){
 	if(i==0) cout << 0 << endl;
 	else{
 		cout << (numeroCombinatorio((i+1)*(i+1), 2))-(4*i*(i-1)) << endl;
 	}
 }
}

Tengo una funcion que calcula \binom{n}{k}.
Luego, para calcular la cantidad de formas de colocar dos caballos en un tablero de n*n de tal forma que no se ataquen entre ellos, hago \binom{n*n}{2}-4*(n-1)*(n-2), donde \binom{n*n}{2} es la forma de colocar dos caballos en un tablero y 4*(n-1)*(n-2) es la forma de colocar dos caballos en un tablero con la condición de que estos se ataquen, ya que un par de caballos atacados determina un rectángulo de 2*3 0 3*2, y hay 2*(n-1)*(n-2) rectángulos en en tablero inicial que son de este tipo. A esto se lo multiplica por dos ya que hay dos formas de poner los caballos en cada rectángulo.
Hay un caso de prueba en el cual n=10000, y me tirá “execution timed out”.
Alguien sabe como puedo hacer mi solución más eficiente?


#2

¡Hola!

Una recomendación: para crear tipos utilizá siempre que se puede typedef en lugar de #define. Así:

typedef long long tint;

typedef siempre tiene ventaja sobre #define ya que el compilador así entiende explícitamente que se está creando un nombre nuevo para el tipo, y lo trata como un nombre de tipo acorde, mientras que #define crea un reemplazo sintático directo. Así por ejemplo, tint(x-y) se puede hacer si usamos el typedef, pero si hicimos el #define lo cambia por long long(x-y) que no funciona (porque el compilador esperaría (long long)(x-y)).

Dicho eso, tu solución de número combinatorio es en general exponencial en n y k. Como acá solo la usás con k = 2, no es tan catastrófico pero igualmente va a tomar un tiempo de ejecución del estilo de n^2 o n^3, donde n sería acá (i+1)^2. Eso toma demasiado tiempo.

La razón de por qué esa recursión termina siendo más cara de lo que uno podría pensar está explicada en la wiki acá, junto con la técnica de programación dinámica que se puede usar para hacer recursiones eficientes:

http://wiki.oia.unsam.edu.ar/algoritmos-oia/programacion-dinamica

Allí se explica con el ejemplo de Fibonacci, pero la situación es similar.

Ahora bien, volviendo a tu caso particular: Solo utilizás n \choose 2, y no un combinatorio arbitrario cualquiera. En este caso es mejor usar la fórmula directamente: {n \choose 2} = \frac{n(n-1)}{2}.

En general la fórmula es (aunque no siempre conviene usarla, pero acá sí):

{n \choose k} = \frac{n (n-1) \cdots (n-k+2) (n-k+1)}{k!}


#3

Gracias por la repuesta!
Le cambié eso y anduvo.