ONI 2009 - Qualificação - Problema A

[Joao brandao]

Boas pessoal, estava a resolver um exercicio das olimpiadas de 2009 e com a minha submissao apenas obtive 62 pontos. A questão que coloco é se me podem ajudar a melhorar o algoritmo em si dando outras ideias de fazer o mesmo exercicio ou pegar na resoluçao que se encontra ai em baixo e melhor um pouco.

Enunciado: http://www.dcc.fc.up.pt/oni/problemas/2009/qualificacao/probA.html

#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
     vector <int>vect;
     vector <unsigned int>maiores;
      int num,prenum,c,f,np,maior=-1;
cin>>np;
for(int i=1;i<=np;i++)
{
        cin>>num;
        vect.push_back(num);
}
        cin>>prenum;
        for(int j=1;j<=prenum;j++)
        {
        cin>>c>>f;
        for(int i=c-1;i<=f-1;i++)
        {   
           if(vect[i]>=maior)
           {
             if(vect[i]>maior)
             {
               maior=vect[i];
               maiores.clear();
             }
             if(vect[i]==maior)
             maiores.push_back(i);
           }
        }
        cout<<maior;
        maior=-1;
        for(unsigned int i=0;i<=maiores.size()-1;i++)
        {
          cout<<" "<<maiores[i]+1;
        }
        cout<<endl;
        maior=-1;
        maiores.clear();
        }
    return 0;
}

[pmg]

Nao pensei muito a serio no problema.

Ve la se consegues fazer com que passes no array das alturas dos edificios sequencialmente, uma so vez.

Talvez ordenar as fotos pelo primeiro edificio ajude ...

[Joao brandao]

acho que nao daria da maneira que disses te :-S visto que ele mais tarde vai te dizer de que posiçao a posiçao quer os predios.

Tipo, ele indica te 4(x) ao 7(y) e tu tens de ver no array da posiçao x ate a y o maior.. dai nao dar para ordenar

[pmg]

Tens o array das alturas dos predios, por exemplo: 350 150 200 400 831 450 200 350 100 350

O que eu dizia era para percorreres o array de alturas sequencialmente e calculares a altura maxima para cada foto: assim so passarias em cada edificio uma vez.

Mais ou menos assim para as fotos (4 a 7), (6 a 9), e (2 a 5):

Edificio 1: nao e preciso para nada

Edificio 2: foto 3: max 150 @ 2

Editifio 3: foto 3: max 200 @ 3

Edificio 4: foto 1: max 400 @ 4 --- foto 3: max 400 @ 4

Edificio 5: foto 1: max 831 @ 5 --- foto 3: max 831 @ 5

Edificio 6: foto 1: nao muda max --- foto 2: max 450 @ 6

Edificio 7: foto 1: nao muda max --- foto 2: nao muda max

Edificio 8: foto 2: nao muda max

Edificio 9: foto 2: nao muda max

Edificio 10: nao e preciso para nada

Agora imprimes os resultados

Foto 1 -- 831 @ 5

Foto 2 -- 450 @ 6

Foto 3 -- 831 @ 5

[Warrior]

Peço desculpa não te dar uma resposta mais concreta, mas sinto alguma dificuldade entre apontar um caminho e resolver-te o problema.

Deixo-te um link:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Volta a avisar se te sentires perdido.

[Joao brandao]

okok, obrigada pela ajuda. vou tentar percebe o que é que o gajo no topcoder quer dizer para depois tentar resolver dessa forma. 😉 se precisar de ajuda coloco outra vez um post neste topico

[JoaoSantos95]

Podes associar a cada altura a sua posição e depois fazeres uma ordenação, percorres o vetor ordenado até que a posição (do edifício na foto) da posição do vetor onde te encontras esteja compreendida entre os intervalos dados

Exemplo:

10

350 150 200 400 831 450 200 350 100 350

a cada um desses valores das a sua posição na foto:

831 corresponde ao 5;

450 corresponde ao 6;

400 corresponde ao 4;

350 corresponde ao 1, 8, 10;

200 corresponde ao 3, 7;

150 corresponde ao 2;

100 corresponde ao 9;

Ordenas o teu vetor e ele fica: 831 450 400 350 350 350 200 200 150 100

                     

Percorres o vetor ordenado e se a posição a que ele corresponde estiver entre os intervalos dados então podes imprimir, tens também de verificar se os valores que vêm a frente são iguais a ele e se estão entre os intervalos dados, se isso ocorrer então tens de imprimir a sua posição também.

[Joao brandao]

mesmo assim acho que dessa maneira iria passar do tempo disponivel com valores grandes(excesso de tempo ao executar o programa).

A maneira mais facil de se fazer isto e menos complicada era arranjar maneira de passar apenas 1 vez no ciclo dos valores.

[xtrm0]

Eu quando o ano passado treinava, resolvi da seguinte forma:

1(preprocessamento)- Guardar a melhor fotografia para as fotografias que pertencas a conjuntos na forma [224n,224(n+1)[, n€N. Ou seja, guarda a melhor fotografia para os blocos:

0, 224

225, 448

...

na array M[225]

2- Para cada fotografia, calculas o maior edificio, utilizando o préprocessamento:

2.1-Ex1:

Imagina que queriam a melhor fotografia entre 3, 2248;

Entao, podias aproveitar os cálculos que já tinhas feito e fazer (nota que a seguinte notacao não representa nenhuma linguagem de programacao em especifico):

ans = std::max(E[3...224],M[1...9],E[2240...2248]);

Assim, apenas tens de fazer (sqrt(N)+448)*F calculos para o pior caso, o que passa no tempo.

Edit: Enganei-me no numero de edificios.

[Warrior]

O algoritmo do João Santos obteria TLE nos casos maiores. Já agora, segundo o que explicaste é indiferente ordenar ou não.

João Brandão: leste o artigo que coloquei?

[Joao brandao]

ja comecei a ler, ainda é um bocado dificil aquilo :-S mas com um bocado de pratica e voltar a ler, chega-se la.

[Warrior]

As soluções para 100 pontos dos problemas das ONI são, normalmente, bastante complicadas. Muito poucos alunos universitários os conseguiriam resolver, portanto não se sintam mal quando encontram uma solução mais difícil do que o que estavam à espera.

Resta ler, reler e implementar.