Vengo a publicar de vuelta, para ver si alguien me da una mano para mejorar la solución que hice para el problema Pyramid II. Copio mi código y paso a explicar un poco lo que quise hacer:
Código
#include <iostream>
#include <cstdio>
#define forn(i,N) for(int i=0;i<N;i++)
using namespace std;
int pmA, pmB; /// pyramid dimensions
int chC, chD; /// chamber dimensions
int bfM, bfN; /// battlefield dimensions
int field [2000][2000];
int pyramidHash[2000][2000];
int chamberHash[2000][2000];
int result[2][2];
void hashPyramid(){
int posX=0, posY=0;
int actualWidth = 0;
int sum = 0;
while (actualWidth < pmA ){
forn(i,pmB){
sum += field[actualWidth][i];
}
actualWidth++;
}
pyramidHash[posX][posY] = sum;
posX++;
forn(i,(bfN-pmB)+1){
if (i!=0)
posX=0;
if(posY==0){
forn(j,(bfM-pmA)){
forn(k,pmB){
sum += field[posX+pmA-1][posY+k];
sum -= field[posX-1][posY+k];
}
pyramidHash[posX][posY] = sum;
posX++;
}
}
int newRowSumUp=0;
int newRowSumDown=0;
if(posY>0){
sum = pyramidHash[posX][posY-1];
forn(k,pmA){
newRowSumUp += field[k][posY-1];
newRowSumDown += field[k][posY+pmB-1];
}
pyramidHash[posX][posY] = (sum-newRowSumUp)+newRowSumDown;
posX++;
forn(j,(bfM-pmA)){
sum = pyramidHash[posX][posY-1];
newRowSumUp += field[posX+pmA-1][posY-1];
newRowSumUp -= field[posX-1][posY-1];
newRowSumDown += field[posX+pmA-1][posY+pmB-1];
newRowSumDown -= field[posX-1][posY+pmB-1];
pyramidHash[posX][posY] = (sum-newRowSumUp)+newRowSumDown;
posX++;
}
}
posY++;
}
}
void hashChamber(){
int posX=0, posY=0;
int actualWidth = 0;
int sum = 0;
while (actualWidth < chC ){
forn(i,chD){
sum += field[actualWidth][i];
}
actualWidth++;
}
chamberHash[posX][posY] = sum;
posX++;
forn(i,(bfN-chD)+1){
if (i!=0)
posX=0;
if(posY==0){
forn(j,(bfM-chC)){
forn(k,chD){
sum += field[posX+chC-1][posY+k];
sum -= field[posX-1][posY+k];
}
chamberHash[posX][posY] = sum;
posX++;
}
}
int newRowSumUp=0;
int newRowSumDown=0;
if(posY>0){
sum = chamberHash[posX][posY-1];
forn(k,chC){
newRowSumUp += field[k][posY-1];
newRowSumDown += field[k][posY+chD-1];
}
chamberHash[posX][posY] = (sum-newRowSumUp)+newRowSumDown;
posX++;
forn(j,(bfM-chC)){
sum = chamberHash[posX][posY-1];
newRowSumUp += field[posX+chC-1][posY-1];
newRowSumUp -= field[posX-1][posY-1];
newRowSumDown += field[posX+chC-1][posY+chD-1];
newRowSumDown -= field[posX-1][posY+chD-1];
chamberHash[posX][posY] = (sum-newRowSumUp)+newRowSumDown;
posX++;
}
}
posY++;
}
}
void getResult(){
int bestRes = 0;
int maxX = (bfM-pmA)+1;
int maxY = (bfN-pmB)+1;
forn(i,maxY){
forn(j,maxX){
for (int k=i+1;k<(pmB + i) - (chD);k++){
for (int l=j+1;l<(pmA + j) - (chC);l++){
int res = pyramidHash[j][i] - chamberHash[l][k];
if ( res > bestRes ){
bestRes = res;
result[0][0] = j+1;
result[1][0] = i+1;
result[0][1] = l+1;
result[1][1] = k+1;
}
}
}
}
}
}
int main(){
cin >> bfM >> bfN >> pmA >> pmB >> chC >> chD;
forn(i,bfN){
forn(j,bfM){
cin >> field[j][i];
}
}
hashPyramid();
hashChamber();
getResult();
cout << result[0][0] << " " << result[1][0] << endl << result[0][1] << " " << result[1][1] << endl;
return 0;
}
La idea básica del problema es encontrar la posicion de una pirámide y la de una habitación dentro de ella para las cuales la resta entre la altura total de la pirámide menos la altura total de la habitación sea lo mas grande posible.
No se me ocurrió otra forma que probando todas las posibilidades, pero hice un par de cosas para optimizar eso. Primero que nada, “hashee” cada posición posible de la pirámide e hice lo mismo con la habitación, de manera que para cada posición posible se obtiene el valor de la suma de todos los casilleros que contiene. Así, hacer esto:
“… la resta entre la altura total de la pirámide menos la altura total de la habitación …”
tiene una complejidad mucho menor.
Además, el hash lo hice con una ventana deslizante bidimensional. Se comienza obteniendo la altura total de, por ejemplo, la pirámide en la posición (0,0) y se guarda ese valor en una tabla que almacena todos los “hash”. Después, se hashea la pirámide un casillero a la derecha, entonces se toma el hash recién calculado, se le restan los valores de los casilleros que la pirámide ya no ocupa (en este caso, la columna a su izquierda) y se le suman los valores de los casilleros que empieza a ocupar (la columna a su izquierda). Me pareció que de esta manera era mejor que recorriendo todos los casilleros que quiero “hashear”.
Espero que se haya entendido! Esta solución devuelve 66 puntos en el juez de COJ, resolviendo bien todos los casos hasta que tira TimeOut desde un caso en adelante. No hace falta que vean el código, capaz no es muy lindo (y hay código repetido). Pero me gustaría que al menos me encaminen para encontrar una solución mejor (o mejorar la que ya hice).
Muchas gracias!