Problema A ONI

[polska]

Boas pessoal, eu vou participar nas ONI, e devido a isso fui tentando resolver os problemas do servidor de estudo da ONI...

E realizei o problema A da qualificação 2009 ... Ao enviar, o meu programa estava correcto, mas no entanto apenas 68%, não 100%... A minha prof falou-me da eficiência do programa... E tentou-me ajudar modificando o programa.. Mas mesmo assim o resultado manteve-se, então mandei uma pergunta ao juri, este mesmo respondeu-me também falando da eficiência...

Então, mais uma vez, a minha prof tentou-me ajudar, e falou-me da pesquisa binária, já que o prog faz arrastamentos de vector e assim, e então modificou o meu programa, utilizando a pesquisa binária para me indica a posição onde devo colocar o numero no vector, sendo então melhorada a eficiência, pois em vez de recorrer a pesquisa sequência do meu vector com 100000 posições, utiliza a pesquisa binária e depois para remover e adicionar torna-se mais fácil também... Contudo!.. O programa ainda desceu a percentagem, de 68%. para 56%...

Alguma idea do que fazer???

#include <stdio.h>
#include <string.h>
//#include <stdlib.h>

int v[100000],ultimo=0;

int PesquisaBinaria (int chave)
{
     int inf = 0; //Limite inferior      (o primeiro elemento do vetor em C é zero          )
     int sup = ultimo-1; //Limite superior    (termina em um número a menos 0 à 9 são 10 numeros )
     int meio;
     while (inf <= sup) 
     {
        meio = inf + (sup-inf)/2;
	if (chave < v[meio])
               sup = meio-1;
        else
               inf = meio+1;
     }

     return sup+1;   // não encontrado
}



void adiciona(int energia){


int pos=PesquisaBinaria(energia);



for(int i=ultimo;i>pos;i--){
	v[i]=v[i-1];
}
v[pos]=energia;
ultimo++;

/*for(int i=0;i<ultimo;i++){
	printf("%d ",v[i]);
}
printf("\n");*/
}

void retiraMAX(){
printf("%d\n",v[ultimo-1]);
ultimo--;
}

void retiraMIN(){

printf("%d\n",v[0]);
for(int i=0;i<ultimo;i++){
	v[i]=v[i+1];
}

ultimo--;
}


int main(){
int A,R,E;
char p[5];
scanf("%d %d",&A,&R);
for(int i=1;i<=A+R;i++){
	scanf("%s",p);
	if(strcmp(p,"BAK")==0){
		scanf("%d",&E);
		adiciona(E);
	}
	if(strcmp(p,"MAX")==0){
		retiraMAX();
	}
	if(strcmp(p,"MIN")==0){
		retiraMIN();
	}
}
//system("pause");
return 0;
}

[pikax]

esse problema e' o A da ONI 2011

[skiller10]

Que estruturas de dados conheces?

[HappyHippyHippo]

está mito pesado pela razão que o adicionar um elemento ao vector pode ser mesmo muito pesado:

se tiveres 999 elementos no vector e fores adicionar o menor, terás de mover todos os elementos do vector uma posição para a frente

Que estruturas de dados conheces?

[xtrm0]

Ao utilizares a pesquisa binaria mantens a mesma complexidade, ja que tens de mover sempre a array toda para cima quando a adicionas.

[polska]

A minha prof disse que a pesquisa binária é o método mais eficiente, por isso é que eu disse que o prog se iria tornar mais eficiente..

Que estruturas de dados conheces?

Ao que vos referis com estruturas de dados?

[HappyHippyHippo]

isto :

http://en.wikipedia.org/wiki/Binary_tree

[skiller10]

Binary Trees são um exemplo, mas existem muitas mais... Acho que deves começar por aprender filas, pilhas, binary tress..

[polska]

Ah! A minha prof falou-me disso, das árvores binárias e tudo, mas não me ensinou nada disso, nem nenhuma das que referiste sei...

Eu tou no 10º, ainda é cedito.. xD , mas aprendendo isso, conssigo uma maior eficácia nos programas?

[skiller10]

Cada problema é um problema. Se leres o 2º artigo da academia ONI podes reparar que existem vários tipos de problemas.

[polska]

claro, o meu deu Time Limit Exceeded, mas o jurí disse que tudo tinha haver com a eficiência do programa..

"Tens "Time Limit Exceeded" porque o teu programa não tem a eficiência necessária para teres os 100 pontos. As Olimpíadas são um concurso de carácter algorítmico e para ter os 100 pontos tipicamente não chega ter um algoritmo correcto. É necessário que seja eficiente, ou seja que passe dentro dos limites temporais e de memória dados. Se quiseres tentar perceber como este problema poderia ser feito para 100 pontos podes por exemplo usar o fórum."

[JoaoSantos95]

Eu usei uma priority queue, é uma pilha com a particularidade de ordenar logo os valores que tu metes para dentro dela.

http://www.cplusplus.com/reference/stl/priority_queue/ - tens ai a página dela no site cplusplus, não é difícil de usar, basta entenderes bem o top, o push e o pop para resolveres este exercício mas claro, convém saberes as restantes funções no caso de precisares de usar isto no futuro.

Dica: Pensa no caso de ser pedido o mínimo, alguma dúvida já sabes

[pikax]

Da' uma vista de olhos no topico das ONI do ano passado encontras la' boas resolucoes http://www.portugal-a-programar.pt/index.php?showtopic=42003

[xtrm0]

Se utilizasses o mesmo algoritmo em c++ com um vector com inserts, deixavas de ter esse problema de efeciencia (acho eu).

[Dr_Lion]

Em vez de usares vectores experimenta usar listas ligadas, ou biligadas.

A eficiência das duas varia consoante as tarefas que pretendas executar.

Por exemplo para removeres um elemento a meio de uma lista biligada é tranquilo, encontras o valor, e com os ponteiros que apontam para o nó anterior e seguinte, obtens esses nós, e alteras no nó anterior o ponteiro para o nó seguinto, passando a ser o valor que tinha o nó que vais remover. No nó seguinte ao que ias remover, alteras o ponteiro para o nó anterior ao que removeste.

Para efectuares este processo numa lista ligada, terias que andar com variáveis manhosas para garantires que tinhas a posição anterior sem teres que percorrer a lista outra vez, o facto de percorreres a lista mais do que uma vez (para a mesma tarefa) é um factor que reduz  a eficiencia desta.

Normalmente com os truqes que usas na implementação duma lista ligada para a percorreres apenas uma vez, acaba por reduzir na mesma a eficiência da utilização da lista ligada "com truqes" em relação a uma lista biligada.

Ainda assim uma lista ligada "com truqes" é mais eficiente que uma lista ligada normal para tarefas de inserção/remoção de objectos.