Jump to content
Sign in to follow this  
skiller10

ONI 2010 Final - B

Recommended Posts

skiller10

Boas,

Resolvi este problema: http://www.dcc.fc.up.pt/oni/problemas/2010/final/probB.html com bfs e obtive 75 pontos TLE. Tentei hoje avançar para a solução dos 100 pontos, já conseguir transformar os losangos para rectângulos e construi a matriz de somas, mas ainda não percebi bem como a utilizar visto que há pontos que nem sequer têm correspondência na matriz original, alguém me pode dar uma explicação desta parte sff?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

Ja viste http://www.dcc.fc.up.pt/oni/problemas/2010/final/discussao/solB.html ? Acho que a explicação dá para perceber.

O não ter correspondência.. faz como eu: desenha umas matrizes ;)


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

Estive agora a desenhar e já consegui perceber como funciona ;D depois de sair do estágio já vou codificar


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
skiller10

Bem tive agora um tempinho e acabei o problema mas tenho TLE aos 60 pontos :s

A minha ideia basicamente foi:

Iniciliazar a matriz de somas a 0.

Ao ler ir vendo de havia arvore naquele sitio e, se sim, "preencher" na matriz de somas.

Depois ir colocando o ponto superior do losango em cada coordenada e ver a progressão que dava apartir desse ponto.

Para o fazer verificava primeiro a maxima progressao possivel sem ultrapassar os limites do mapa.

E fazer o calculo para ver se existia alguma arvore dentro.

Ir progredindo o canto inferior do losango para baixo enquanto fosse possivel.

Pensei em criar uma matriz para guardar as novas coordenadas de cada ponto, será que vai ajudar?

#include <iostream>
#include <stdlib.h>
#include <math.h>
#define MAX 2500 //Dimensão máxima da matriz de somas;
using namespace std;

    int L, C; //Dimensões do Mapa
    int NT; //Dimensão da matriz de somas;
    int bigger=0, big_coluna, big_linha; //Soluções;
    int matriz[MAX][MAX]; //Matriz de somas;
    char ocup; //Auxiliar de input;

//Verificar se o interior do losango está vazio:
bool empty(int a_x, int a_y, int b_x, int b_y){
    return ((matriz[b_x][b_y] - matriz[(a_x-1)][b_y] - matriz[b_x][a_y-1] + matriz[a_x-1][a_y-1]) == 0);
}

//Construção da matriz de somas:
void preencher(int linha, int coluna){
    for(int i = linha; i <= NT; i ++)
        for(int j = coluna; j <= NT; j ++)
            matriz[i][j] ++;
    return;
}

//Ver losango máximo apartir do ponto superior:
int solve(int cab_x, int cab_y){
    int cau_x = cab_x; //Cauda do losango (x);
    int cau_y = cab_y; //Cauda do losango (y);
    int max_v = 1, max_h = 1; //Limites laterais e horizontais;
    int max_prog; //Margem de progressão do losango;
    int prog = 0; //Maior losango possivel;

    //Calcular progressão maxima:
    max_v = (cab_y <= (C-cab_y+1)) ? cab_y : (C-cab_y+1);
    max_h = (int) ceil((L - cab_x + 1)/2.0);
    max_prog = (max_v <= max_h) ? max_v : max_h;

    //Se a progressão maxima for menor ou igual que o maior losango actual não adianta continuar:
    if(max_prog <= bigger)
        return 0;

    //Ver progressão que o losango consegue fazer:
    while(prog < max_prog && empty((cab_x + C - cab_y), (cab_x + cab_y - 1), (cau_x + C - cau_y), (cau_x + cau_y - 1))){
        prog ++;
        cau_x += 2;
    }

    return prog;
}

int main(void){
    //Inicializar a matriz de somas:
    for(int i = 0; i < MAX; i ++)
        for(int j = 0; j < MAX; j ++)
            matriz[i][j] = 0;
    //******************************

    cin >> C >> L; //Leitura das dimensões do mapa;
    NT = (L + C - 1); //Calcular dimensões da matriz de somas;

    //Leitura do mapa e construção da matriz de somas:
    for(int i = 1; i <= L; i ++)
        for(int j = 1; j <= C; j ++){
            cin >> ocup;
            if(ocup == 'A')
                preencher((i + C - j),(i + j - 1));
        }
    //*************************************************

    //Resolver:
        int grow = 0;
    for(int i = 1; i <= L; i ++)
        for(int j = 1; j <= C; j ++){
            grow = solve(i, j);
            if(grow > bigger){
                bigger = grow;
                big_linha = i;
                big_coluna = j;
            }
        }

    //Imprimir resultado:
    cout << bigger << endl; //Imprimir maior losango possivel;
    cout << big_coluna << " " << big_linha << endl; //Imprimir local onde irá ser colocado esse losango;

    return 0;
}

Tentei agora com a dica de testar apenas os losangos com tamanho superior ao maior ate ao momento e fiquei com 35 pontos TLE. Decidi fazer também o calculo das coordenadas e guardar o mesmo para evitar futuros calculos e continuo com 35 pontos TLE.

#include <iostream>
#include <stdlib.h>
#include <math.h>
#define MAX 2500 //Dimensão máxima da matriz de somas;
using namespace std;

    int L, C; //Dimensões do Mapa
    int NT; //Dimensão da matriz de somas;
    int bigger=0, big_coluna, big_linha; //Soluções;
    int matriz[MAX][MAX]; //Matriz de somas;
    int coord[MAX][MAX][2]; //Coordenadas nas matriz de somas;
    char ocup; //Auxiliar de input;

//Verificar se o interior do losango está vazio:
bool empty(int a_x, int a_y, int b_x, int b_y){
    return ((matriz[b_x][b_y] - matriz[(a_x-1)][b_y] - matriz[b_x][a_y-1] + matriz[a_x-1][a_y-1]) == 0);
}

//Construção da matriz de somas:
void preencher(int linha, int coluna){
    for(int i = linha; i <= NT; i ++)
        for(int j = coluna; j <= NT; j ++)
            matriz[i][j] ++;
    return;
}

//Ver losango máximo apartir do ponto superior:
int solve(int cab_x, int cab_y){
    int max_prog;
    //Calcular progressão maxima e verificar se é possivel um losango maior que o melhor:********
    int max_v = 1, max_h = 1;
    max_v = (cab_y <= (C - cab_y + 1)) ? cab_y : (C - cab_y + 1);
    max_h = (int) ceil((L - cab_x + 1) / 2.0);
    max_prog = (max_v <= max_h) ? max_v : max_h;
    if(max_prog <= bigger){
        return 0;
    }
    //*******************************************************************************************

    int cau_x = cab_x + bigger + 2;
    int cau_y = cab_y;
    int prog = bigger;

    //Verificar se é possível o rectângulo com tamanho a seguir ao maior até ao momento, se nao for, devolver 0:
    if(empty(coord[cab_x][cab_y][0], coord[cab_x][cab_y][1], coord[cau_x][cau_y][0], coord[cau_x][cau_y][1])){
        prog ++;
        cau_x += 2;
    }
    else{
        return 0;
    }
    //**********************************************************************************************************

    //Ver progressão que o losango consegue fazer:*********************************************************************************
    while(prog < max_prog && empty(coord[cab_x][cab_y][0], coord[cab_x][cab_y][1], coord[cau_x][cau_y][0], coord[cau_x][cau_y][1])){
        prog ++;
        cau_x += 2;
    }

    return prog;
}

int main(void){
    //Inicializar a matriz de somas:*********************************************************
    for(int i = 0; i < MAX; i ++)
        for(int j = 0; j < MAX; j ++)
            matriz[i][j] = 0;
    //***************************************************************************************

    cin >> C >> L;
    NT = (L + C - 1);

    //Montar coordenadas para a matriz de somas:*********************************************
    for(int i = 1; i <= L; i ++)
        for(int j = 1; j <= C; j ++){
            coord[i][j][0] = i + C - j; //x;
            coord[i][j][1] = i + j - 1; //y;
        }
    //***************************************************************************************

    //Leitura do mapa e construção da matriz de somas:***************************************
    for(int i = 1; i <= L; i ++)
        for(int j = 1; j <= C; j ++){
            cin >> ocup;
            if(ocup == 'A')
                preencher(coord[i][j][0], coord[i][j][1]);
        }
    //****************************************************************************************

    //Calcular maior losango possivel:*******************************************************
    int grow = 0;
    for(int i = 1; i <= L; i ++)
        for(int j = 1; j <= C; j ++){
            grow = solve(i, j);
            if(grow > bigger){
                bigger = grow;
                big_linha = i;
                big_coluna = j;
            }
        }
    //****************************************************************************************

    //Imprimir resultado:**********************************************************************
    cout << bigger << endl;
    cout << big_coluna << " " << big_linha << endl;

    return 0;
}


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.