Problemas [Seleccao 2008]

[skiller10]

Heys,

Hoje decidi voltar aos problemas de treino das ONI, e pela segunda vez tive run-time error e não consigo saber porque :s já perguntei na plataforma e nao tive resposta, alguem me pode dar uma ajuda?

Problema A - O cartaz do google: (RunTimeError 93pontos)

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <string>
#define MAX 10000010
using namespace std;

      bool primes[MAX+10];
      string bigger, straux;

void pre(void){
         unsigned int raiz = (unsigned int) sqrt(MAX);  
     primes[0] = primes[1] = false;
     for(unsigned int i=2; i<MAX; i++)
         primes[i] = true;
     for(unsigned int i=2; i<=raiz; i++)
         if(primes[i])
             for(unsigned int j=i*2; j<MAX; j+=i)
                 primes[j] = false;   
     return;
}

int main(void){
        unsigned int qdigs, qprimes=0, num;    
        
    cin >> qdigs;    
    while(cin >> straux){
         bigger.append(straux);  
    }

    pre();
    
    for(unsigned int i=0; i<=(unsigned int)(bigger.size()-qdigs); i++){
        if(bigger[i]=='0'){
            continue;
        }
        straux = bigger.substr(i, qdigs);
        num = (unsigned int) atoi(straux.c_str());
        if(primes[num]){
            qprimes ++;
        }
    }

    cout << qprimes << endl;
    return 0;
}

Problema E - Primometro: (RunTimeError 65pontos)

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <vector>
#define MAX 3000
using namespace std;

struct CASE{
    int N, K;
};

struct SOL{
    int knap[MAX+100];
};

    int C;
    bool crivo[MAX+100];
    vector <int> primos;
    CASE aux;
    vector <CASE> ins;
    vector <SOL> dp;
    SOL sock;

void input(void){
    cin >> C;
    for(int i=0; i<C; i++){
        cin >> aux.N >> aux.K;
        if(aux.K > aux.N) aux.K = aux.N;
        ins.push_back(aux);
    }
    return;
}

void gerar_primos(void){
         unsigned int raiz = (unsigned int) sqrt(MAX);
     crivo[0] = crivo[1] = false;
     for(unsigned int i = 2; i <= MAX; i ++)
         crivo[i] = true;
     for(unsigned int i = 2; i <= raiz; i ++)
         if(crivo[i])
             for(unsigned int j = (i*2); j <= MAX; j += i)
                 crivo[j] = false;
    for(unsigned int i = 2; i <= MAX; i ++)
        if(crivo[i])
            primos.push_back(i);
    return;
}

void calcular(void){
    int qpr = primos.size();
    sock.knap[0] = 1;
    for(int i = 1; i <= MAX; i ++)
        sock.knap[i] = 0;
    dp.push_back(sock);
    for(int i = 0; i < qpr; i ++){
        for(int j = (MAX - primos[i]); j >= 0; j --)
            sock.knap[(j + primos[i])] += sock.knap[j];
        dp.push_back(sock);
    }
    return;
}

void solve(void){
    gerar_primos();
    calcular();
    return;
}

void output(void){
    for(int i = 0, indice = 0; i < C; i ++, indice = 0){
        while(ins[i].K >= primos[indice])
            indice ++;
        cout << dp[indice].knap[(ins[i].N)] << endl;
    }
    return;
}

int main(void){
    input();
    solve();
    output();
    return 0;
}

Acho que a lógica com que estou a fazer é a correcta mas deve-me estar a falhar algo, basicamente estou a usar uma especie de memoization com knapsack.

[mogers]

Não custa nada colocares o link para os enunciados...

No 1º tás a fazer o erro comum de misturar indevidamente ints com unsigned ints. Basta experimentares um input como

5

13

No 2º, ter esses structs Case e Sol parece-me altamente desnecessário. Complicação desnecessária k prejudica a leitura do código. Podes simplesmente processar cada caso directamente. Não há necessidade nenhuma de os guardar.

O rte mais provavel parece array out of bounds.

btw, não vejo memoization nenhum nesse código..

[skiller10]

Nao coloquei links para os enunciados porque naos os encontrei fora do mooshak :s

Obrigado, ja tive os 100pontos no A 🙂

(Removo o código do post ou deixo?)

Ainda não percebi muito o conceito de memoization, tenho que treinar bem isso 😄

Processar directamente como? Eu guardei porque depois é mais fácil de gerir os resultados obtidos e só necessito de gerar uma única vez, em vez de para cada caso fazer o knapsack do 0. Vou tentar para já "descomplicar" o código.

Já agora como se faz uma declaração de vector de matrizes, não deveria ser algo como:

vector <int[30][30]> vt;

Não obtenho erro na declaração, mas quando tento adicionar algo é que são elas :x

[Localhost]

Ainda não percebi muito o conceito de memoization, tenho que treinar bem isso

Quando resolves um problema com DP resolves o problema em estilo bottom-up (de baixo para cima). Com memoization resolves em top-down (de cima para baixo) o que vai fazer com que recalcules algumas coisas. Com memoization limitas-te a guardar o resultado de uma determinada chamada. Se já calculaste esse valor utilizas, noutro caso calculas.

Um exemplo simples para perceber isto é o shortest path com DFS. Se já passaste por um nó vais obrigatoriamente já ter calculado a distância desse nó ao teu destino, então não necessitas de recalcular esse valor, simplesmente deves utilizá-lo.

[mogers]

Processar directamente como? Eu guardei porque depois é mais fácil de gerir os resultados obtidos e só necessito de gerar uma única vez, em vez de para cada caso fazer o knapsack do 0. Vou tentar para já "descomplicar" o código.

Lês os dados de cada caso de teste e calculas logo, fazes o output e depois lês o caso de teste seguinte.

Já agora como se faz uma declaração de vector de matrizes, não deveria ser algo como:

vector <int[30][30]> vt;

Não obtenho erro na declaração, mas quando tento adicionar algo é que são elas :x

isso não funciona. na prática isso é basicamente equivalente a vector <int * > vt.  Quando depois tentas usar os apontadores guardados no vector dessa maneira, estes já são inválidos. Eu evitaria ao máximo usar apontadores nesses casos, comete-se erros muito facilmente e é complicado de debuggar

Eu diria para criares uma estrutura de dados ou usar um vector de matrizes, mas isso fica meio estranho

vector< vector<vector<int> > > vectorMatrizes ; // que complicação :s

struct Tipo {
   int mat[30][30];
   // outros campos
};
vector< Tipo > vt

[mogers]

Btw isso de não saberes onde encontrar os enunciados é muito mau :|  Só usas os problemas do mooshak para praticar?

http://www.dcc.fc.up.pt/oni/2011/index.cgi?page=problemas tem imensos problemas de edições anteriores. Os concorrentes nem lêm o site :|

[skiller10]

Acho que o código está bastante mais simples mas contínuo a obter só 65 pontos, só que agora com WA :s já fiz vários casos de teste e todos de dão correctamente :S

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <vector>
#define MAX 3000
using namespace std;

struct KNAP{
    int cfg[MAX];
};

/**/vector <int> primos; //Vector com todos os números primos necessários;
/**/vector <KNAP> knaps; //Vector com o knapsack ao nível que os números primos irão ser adicionadas;
/**/KNAP k_aux;

//Função para gerar primos através do crivo:
void gerar_primos(void){
         int raiz = (int) sqrt(MAX);
         bool crivo[MAX+1];
    //Inicializar o crivo:
    crivo[0] = crivo[1] = false;
    for(int i = 2; i <= MAX; i ++)
        crivo[i] = true;
    //Fazer o crivo:
    for(int i = 2; i <= raiz; i ++)
        if(crivo[i])
            for(int j = (i*2); j <= MAX; j += i)
                crivo[j] = false;
    //Percorrer o crivo à procura dos primos e guarda-los no vector:
    for(int i = 2; i <= MAX; i ++)
        if(crivo[i])
            primos.push_back(i);
    //Voltar ao main:
    return;
}

//Função para fazer o knapsack:
void dotheknap(void){
    //Inicializar a configuração do knapsack e guarda-la no vector pois é o momento em que ainda nenhum primo foi adicionado,
    //necessário para quando o K for menor do que 2;
    k_aux.cfg[0] = 1;
    for(int i = 1; i <= MAX; i ++)
        k_aux.cfg[i] = 0;
    knaps.push_back(k_aux);

    //Ir adicionando os números primos e guardando as configurações do knapsack:
    for(int i = 0; i < (int) primos.size(); i ++){
        for(int j = (MAX - primos[i]); j >= 0; j --)
            k_aux.cfg[(j + primos[i])] += k_aux.cfg[j];
        knaps.push_back(k_aux);
    }
    //Voltar ao main:
    return;
}

//Função para procurar o indice da configuração de knap a ser utilizada:
int searchid(int K){
        int index = 0;
    for(int i = 0; i < (int) primos.size(); i++)
        if(K >= primos[i])
            index ++;
        else
            break;
    return index;
}

//Função principal:
int main(void){
        int C, N, K;

    gerar_primos();
    dotheknap();

    cin >> C;
    for(int i=0; i<C; i++){
        cin >> N >> K;
        if(K > N) K = N;
        cout << knaps[searchid(K)].cfg[N] << endl;
    }
    return 0;
}

[Pedro Ribeiro]

skiller, o que te dá por exemplo o caso:

1

3000 3000

[skiller10]

Está-me a dar 0, vou ver o que se passa :s

EDIT: Problema resolvido, estava a estoirar a variável :s Thanks ;D