ONI'2013

Localhost · March 6, 2013 at 07:27 PM

Já foi aberto o site das ONI'2013. Inscrevam-se, aconselho a todos!

ONI'2013 - Site Oficial

HappyHippyHippo · March 6, 2013 at 08:46 PM

eu vou me inscr .....

espera, eu não estou no secundário ... isso foi à 18 anos atrás ... darn ...

bem, fica para os mais novos 😄

polska · March 6, 2013 at 11:12 PM

eu vou me inscr .....

espera, eu não estou no secundário ... isso foi à 18 anos atrás ... darn ...

bem, fica para os mais novos 😄

ahahah 😄

Bem, podem contar de certeza com a minha inscrição!

Edited March 6, 2013 at 11:19 PM by polska

SirDave · March 8, 2013 at 05:47 PM

Eu já me inscrevi!

polska · March 8, 2013 at 06:26 PM

Eu já me inscrevi!

Somos dois 😄

Localhost · March 8, 2013 at 11:57 PM

Está tudo muito parado!

SirDave · March 19, 2013 at 11:56 AM

Já abriram os servidores de treino no Mooshaq, mas está tudo muito parado, sim.

Edited March 19, 2013 at 11:56 AM by SirDave

mogers · March 19, 2013 at 09:48 PM

A altura de treinar é agora para ter tempo de aprender alguma coisa.

Se precisarem de ajuda nos exercícios digam.

polska · March 20, 2013 at 02:10 PM

Já está mais mexido, a didaxis leva alunos como o caraças! É isso que é preciso 🙂

polska · March 20, 2013 at 07:18 PM

Já agora, este foi o primeiro problema que tentei fazer no servidor de treino das qualificações, tive TLE (33%) ..

Não esperava nem de perto os 100% com a minha solução, mas esperava pelo menos os 50%, a minha ideia é ordenar as alturas de forma crescente, e ordenar também os números de ordem, sendo que se as alturas forem iguais ordeno os números de ordem de forma decrescente, isto porque depois quando recebo os intervalos pretendidos, percorro as alturas do fim para o início e quando encontrar um número de ordem que se encontre nesse intervalo posso logo imprimir a altura (porque sei que é a maior possivel nesse intervalo), e posso imprimir o número de ordem porque está ordenado crescentemente.. E depois continuo o loop até encontrar o próximo prédio que se encontre no intervalo mas que a altura seja diferente da primeira imprimida (a maior) .. Será que é o quick sort que está a atrasar a solução, ou não estou a encarar de forma correcta o problema?

//QUALIFICAÇÃO 2009 - PROBLEMA A: DUBAI

#include <stdio.h>

int alturas[50000], numeros_ordem[50000];

void quick_sort(int esq, int dir)
{
       int i = esq, j = dir, tmp;
       int pivot = alturas[(i+j)/2];
       int pivot_indice = numeros_ordem[(i+j)/2];

       /* divisória */
       while(i<=j)
       {

               while(alturas[i]<pivot || (alturas[i]==pivot && numeros_ordem[i]>pivot_indice)) //se quiser ordenar indices pela ordem crescente -> while(alturas[i]<pivot || (alturas[i]==pivot && numeros_ordem[i]<pivot_indice))
                       i++;
               while(alturas[j]>pivot || (alturas[j]==pivot && numeros_ordem[j]<pivot_indice)) //se quiser ordenar iidices pela ordem crescente -> while(alturas[j]>pivot || (alturas[j]==pivot && numeros_ordem[j]>pivot_indice))
                       j--;        

               if(i<=j)
               {
                   tmp = alturas[j];
                   alturas[j] = alturas[i];
                   alturas[i] = tmp;

                   tmp = numeros_ordem[j];
                   numeros_ordem[j] = numeros_ordem[i];
                   numeros_ordem[i] = tmp;

                   i++; j--;
               }
       };

       /* recursividade */
       if(j > esq)
               quick_sort(esq, j);
       if(i < dir)
               quick_sort(i, dir);
}

int main()
{
   int N, i, j, F, inf, sup, found, max;

   scanf("%d", &N);
   for(i=0; i<N; i++)
   {
       scanf("%d", &alturas[i]);
       numeros_ordem[i] = i+1;
   }

   quick_sort(0, N-1);

   scanf("%d", &F);
   for(i=0; i<F; i++)
   {
       scanf("%d %d", &inf, ⊃);

       found = 0;
       for(j=N-1; j>=0; j--)
       {
           if(numeros_ordem[j] >= inf && numeros_ordem[j] <= sup)
           {
               if(found == 0)
               {
                   found = 1;
                   max = alturas[j];
                   printf("%d %d", max, numeros_ordem[j]);
               }
               else if(alturas[j] == max)
                   printf(" %d", numeros_ordem[j]);
               else
               {
                   printf("\n");
                   break;
               }
           }
       }
   }

   return 0;
}

Edited March 20, 2013 at 07:23 PM by polska

mogers · March 20, 2013 at 07:40 PM

Nota: o mooshak só reporta o erro mais grave. Se tens wrong answers e TLE, o judge reporta TLE.

Teres o \n dentro do ciclo não é boa ideia. se as alturas forem todas iguais, não imprimes o \n

Na prática, ordenar só se ajuda se tiveres sorte com o input. Se tens 200 alturas e se se pede só da 100 à 110, podes estar a percorrer todas nesse ciclo. Assim, não vale a pena ordenar

PS: acho muito bem aprenderes o quick sort e a sua implementação, mas na prática é muito melhor aprender a usar o sort() do c++.

// warning: codigo escrito directamente no forum sem testar.
#include <algorithm> // sort
using namespace std;

// assim
int alturas[MAX], numeros_ordem[MAX] , indices[MAX]; // inicialmente, indices = {0,1,2,3,... N-1}

bool compara(int i, int j) {
 if (alturas[i] == alturas[j])
	 return numeros_ordem[i] < numeros_ordem[j];
return alturas[i] < alturas[j];
}
int main() {
// popular alturas[], numeros_ordem[] e indices[]
sort( indices , indices + N, compara );
// indices[i] = indice do i-ésimo (altura, numero_ordem) mais pequeno
}

// ou
pair<int, int> alturas[MAX];  // par com first = altura , second = numero de ordem

int main() {
// popular alturas
sort( alturas, alturas + N );
// alturas[i].first = altura, altura[i].second = numero de ordem, do i-ésimo (altura, numero_ordem) mais pequeno
}

Edited March 20, 2013 at 07:41 PM by mogers

polska · March 20, 2013 at 08:15 PM

Hummm realmente não me lembrei do caso do '\n' ! Vou corrigir isso!

Eu no início pensei se devia ou não ordenar, mas acabei por faze-lo .. Eu só não uso o sort do c++ porque não estou muito acostumado a misturar C com C++, se bem que sei que não tem mal nenhum e que usar o sort não é complicado.. Mas também tinha dúvida na função de comparar, antes de implementar o quick sort eu ia usar o qsort da stdlib, mas eu não sabia como fazer a função de comparar para quando os indices fossem iguais.. Mas é igual à maneira como fizeste nesse código para o sort certo?

mogers · March 20, 2013 at 08:20 PM

Não, o qsort é um pouco diferente. A função de comparação a usar no qsort tem de receber void*, enquanto que na versão em C++ não.

http://stackoverflow.com/questions/327893/how-to-write-a-compare-function-for-qsort-from-stdlib

voltando ao problema em causa, se procurares no forum encontras discussões sobre soluções acerca do problema. visto que este problema necessita de técnicas menos comuns, acho que deves lê-las.

edit: é importante referir que o sort() da <algorithm> implementa um algoritmo que garante O(N log N), isto é, não tem O(N^2) como worst-case como a qsort (que usa o quick sort).

Edited March 20, 2013 at 08:24 PM by mogers

HappyHippyHippo · March 20, 2013 at 08:51 PM

atirei este código ao gcc e correu bem (número de ordenações = 0)

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

#define MAX_BUILDINGS 50000
#define MAX_PHOTOS 50000

#define INPUT_FILE "input.txt"

typedef struct
{
   int height;
   int shadow;
   int shadowing;
} Building;

int main()
{
   Building buildings[MAX_BUILDINGS];
   int n_buildings;
   int n_photos;
   int min, max;
   int i, j;

   FILE * fd = NULL;

   memset(buildings, 0, sizeof(Building) * MAX_BUILDINGS);

   if ((fd = fopen(INPUT_FILE, "r")) == NULL)
   {
       fprintf(stderr, "Erro de abertura do ficheiro de input\n");
       return EXIT_FAILURE;
   }

   if (fscanf(fd, "%d", &n_buildings) != 1) {
       fprintf(stderr, "Erro de leitura do numero de edificios\n");
       fclose(fd);

       return EXIT_FAILURE;
   }

   for (i = 0; i < n_buildings; i++)
   {
       if (fscanf(fd, "%d", &buildings[i].height) != 1) {
           fprintf(stderr, "Erro de leitura da altura do edificio %d\n", i);
           fclose(fd);

           return EXIT_FAILURE;
       }

       j = i - 1;
       while (j >= 0 && buildings[j].height < buildings[i].height)
       {
           j = buildings[j].shadow; // edit : performance
       }

       buildings[i].shadow = j;

       if (buildings[j].height == buildings[i].height)
       {
           buildings[j].shadowing = i;
       }
   }

   if (fscanf(fd, "%d", &n_photos) != 1) {
       fprintf(stderr, "Erro de leitura do numero de fotos\n");
       fclose(fd);

       return EXIT_FAILURE;
   }

   for (i = 0; i < n_photos; i++)
   {
       if (fscanf(fd, "%d %d", &min, &max) != 2) {
           fprintf(stderr, "Erro de leitura dos limites da fotografia\n");
           fclose(fd);

           return EXIT_FAILURE;
       }
       min--;
       max--;

       j = max;
       while (buildings[j].shadow > min)
       {
           j = buildings[j].shadow;
       }

       printf("%d", buildings[j].height);
       while (j != 0)
       {
           printf(" %d", j + 1);
           j = buildings[j].shadowing;
       }
       printf("\n");
   }

   fclose(fd);

   return EXIT_SUCCESS;
}

existe alguma maneira de eu verificar que classificação teria com este código ?

Edited March 20, 2013 at 09:22 PM by HappyHippyHippo

mogers · March 20, 2013 at 09:27 PM

Funciona para o exemplo mas não me parece correcto. Exemplo

A resposta deveria ser "2 1 2" mas dá "2 2".

Uma abordagem dessas toma tempo O(N^2) logo na construção do shadow, com um array crescente de alturas. Por isso teria no máximo uns 50 a 60 pontos acho eu.

HappyHippyHippo · March 20, 2013 at 09:35 PM

Funciona para o exemplo mas não me parece correcto. Exemplo
2
2 2
1
1 2
A resposta deveria ser "2 1 2" mas dá "2 2".

sim, com uma correcção esse problema é resolvido, até porque já sei a razão 😄

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

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

#define MAX_BUILDINGS 50000
#define MAX_PHOTOS 50000

#define INPUT_FILE "input.txt"

typedef struct
{
int height;
int shadow;
int shadowing;
} Building;

int main()
{
Building buildings[MAX_BUILDINGS];
int n_buildings;
int n_photos;
int min, max;
int i, j;

FILE * fd = NULL;

memset(buildings, 0, sizeof(Building) * MAX_BUILDINGS);

if ((fd = fopen(INPUT_FILE, "r")) == NULL)
{
	fprintf(stderr, "Erro de abertura do ficheiro de input\n");
	return EXIT_FAILURE;
}

if (fscanf(fd, "%d", &n_buildings) != 1) {
	fprintf(stderr, "Erro de leitura do numero de edificios\n");
	fclose(fd);

	return EXIT_FAILURE;
}

for (i = 0; i < n_buildings; i++)
{
	if (fscanf(fd, "%d", &buildings[i].height) != 1) {
		fprintf(stderr, "Erro de leitura da altura do edificio %d\n", i);
		fclose(fd);

		return EXIT_FAILURE;
	}

	j = i - 1;
	while (j >= 0 && buildings[j].height < buildings[i].height)
	{
		j = buildings[j].shadow; // edit : performance
	}

	buildings[i].shadow = j;

	if (buildings[0].height == buildings[i].height)
	{
		buildings[j].shadowing = i;
	}
}

if (fscanf(fd, "%d", &n_photos) != 1) {
	fprintf(stderr, "Erro de leitura do numero de fotos\n");
	fclose(fd);

	return EXIT_FAILURE;
}

for (i = 0; i < n_photos; i++)
{
	if (fscanf(fd, "%d %d", &min, &max) != 2) {
		fprintf(stderr, "Erro de leitura dos limites da fotografia\n");
		fclose(fd);

		return EXIT_FAILURE;
	}
	min--;
	max--;

	j = max;
	while (buildings[j].shadow >= min)
	{
		j = buildings[j].shadow;
	}

	printf("%d", buildings[j].height);
	printf(" %d", j + 1);

	j = buildings[j].shadowing;
	while (j != 0)
	{
		printf(" %d", j + 1);
		j = buildings[j].shadowing;
	}
	printf("\n");
}



fclose(fd);

return EXIT_SUCCESS;
}

---------------

Uma abordagem dessas toma tempo O(N^2) logo na construção do shadow, com um array crescente de alturas. Por isso teria no máximo uns 50 a 60 pontos acho eu.

faz bem as contas ...

Edited March 20, 2013 at 09:46 PM by HappyHippyHippo

polska · March 20, 2013 at 09:37 PM

Eu agora que vejo, estava a ser mesmo estúpido . eu tenho os limites, um for de limite inferior ao superior chega para fazer o mesmo que eu fiz com tanta ordenação.. ai jesus, estou maluco 😁 . Mas já estive a ver essas tais técnicas, vou melhorar isto!

mogers · March 20, 2013 at 09:41 PM

faz bem as contas ...

Não tenho os testes do treino e o treino só está disponivel aos concorrentes. Pelo enunciado, uma solução com essa complexidade temporal cumpria o requisito dos 50%, talvez consiga um pouco mais, daí talvez os 60 pontos.

Edited March 20, 2013 at 09:41 PM by mogers

mogers · March 20, 2013 at 10:08 PM

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

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

#define MAX_BUILDINGS 50000
#define MAX_PHOTOS 50000

#define INPUT_FILE "input.txt"

typedef struct
{
int height;
int shadow;
int shadowing;
} Building;

int main()
{
Building buildings[MAX_BUILDINGS];
int n_buildings;
int n_photos;
int min, max;
int i, j;

FILE * fd = NULL;

memset(buildings, 0, sizeof(Building) * MAX_BUILDINGS);

if ((fd = fopen(INPUT_FILE, "r")) == NULL)
{
	fprintf(stderr, "Erro de abertura do ficheiro de input\n");
	return EXIT_FAILURE;
}

if (fscanf(fd, "%d", &n_buildings) != 1) {
	fprintf(stderr, "Erro de leitura do numero de edificios\n");
	fclose(fd);

	return EXIT_FAILURE;
}

for (i = 0; i < n_buildings; i++)
{
	if (fscanf(fd, "%d", &buildings[i].height) != 1) {
		fprintf(stderr, "Erro de leitura da altura do edificio %d\n", i);
		fclose(fd);

		return EXIT_FAILURE;
	}

	j = i - 1;
	while (j >= 0 && buildings[j].height < buildings[i].height)
	{
		j = buildings[j].shadow; // edit : performance
	}

	buildings[i].shadow = j;

	if (buildings[0].height == buildings[i].height)
	{
		buildings[j].shadowing = i;
	}
}

if (fscanf(fd, "%d", &n_photos) != 1) {
	fprintf(stderr, "Erro de leitura do numero de fotos\n");
	fclose(fd);

	return EXIT_FAILURE;
}

for (i = 0; i < n_photos; i++)
{
	if (fscanf(fd, "%d %d", &min, &max) != 2) {
		fprintf(stderr, "Erro de leitura dos limites da fotografia\n");
		fclose(fd);

		return EXIT_FAILURE;
	}
	min--;
	max--;

	j = max;
	while (buildings[j].shadow >= min)
	{
		j = buildings[j].shadow;
	}

	printf("%d", buildings[j].height);
	printf(" %d", j + 1);

	j = buildings[j].shadowing;
	while (j != 0)
	{
		printf(" %d", j + 1);
		j = buildings[j].shadowing;
	}
	printf("\n");
}



fclose(fd);

return EXIT_SUCCESS;
}

Isso parece-me apenas um hack para a posição 0.

Deveria dar "2 2 3 4 5" mas dá "2 2".

Posso continuar a criar casos de teste, mas não me parece que essa abordagem vá no bom caminho...

Este tutorial explica uma técnica possível para resolver o problema.

HappyHippyHippo · March 20, 2013 at 10:18 PM

Isso parece-me apenas um hack para a posição 0.

Código :

5

1 2 2 2 2

1

1 5

Deveria dar "2 2 3 4 5" mas dá "2 2".

Posso continuar a criar casos de teste, mas não me parece que essa abordagem vá no bom caminho...

... criei um erro ao alterar o código antigo, estava a ver algo e fiz bronca ...

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

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

#define MAX_BUILDINGS 50000
#define MAX_PHOTOS 50000

#define INPUT_FILE "input.txt"

typedef struct
{
int height;
int shadow;
int shadowing;
} Building;

int main()
{
Building buildings[MAX_BUILDINGS];
int n_buildings;
int n_photos;
int min, max;
int i, j;

FILE * fd = NULL;

memset(buildings, 0, sizeof(Building) * MAX_BUILDINGS);

if ((fd = fopen(INPUT_FILE, "r")) == NULL)
{
	fprintf(stderr, "Erro de abertura do ficheiro de input\n");
	return EXIT_FAILURE;
}

if (fscanf(fd, "%d", &n_buildings) != 1) {
	fprintf(stderr, "Erro de leitura do numero de edificios\n");
	fclose(fd);

	return EXIT_FAILURE;
}

for (i = 0; i < n_buildings; i++)
{
	if (fscanf(fd, "%d", &buildings[i].height) != 1) {
		fprintf(stderr, "Erro de leitura da altura do edificio %d\n", i);
		fclose(fd);

		return EXIT_FAILURE;
	}

	j = i - 1;
	while (j >= 0 && buildings[j].height < buildings[i].height)
	{
		j = buildings[j].shadow; // edit : performance
	}

	buildings[i].shadow = j;

	if (buildings[j].height == buildings[i].height) // <- isto não era para alterar !!!!
	{
		buildings[j].shadowing = i;
	}
}

if (fscanf(fd, "%d", &n_photos) != 1) {
	fprintf(stderr, "Erro de leitura do numero de fotos\n");
	fclose(fd);

	return EXIT_FAILURE;
}

for (i = 0; i < n_photos; i++)
{
	if (fscanf(fd, "%d %d", &min, &max) != 2) {
		fprintf(stderr, "Erro de leitura dos limites da fotografia\n");
		fclose(fd);

		return EXIT_FAILURE;
	}
	min--;
	max--;

	j = max;
	while (buildings[j].shadow >= min)
	{
		j = buildings[j].shadow;
	}

	printf("%d", buildings[j].height);
	printf(" %d", j + 1);

	j = buildings[j].shadowing;
	while (j != 0)
	{
		printf(" %d", j + 1);
		j = buildings[j].shadowing;
	}
	printf("\n");
}

fclose(fd);

return EXIT_SUCCESS;
}

Este tutorial explica uma técnica possível para resolver o problema.

não é minha intenção resolver como todos os outros, é fazer exactamente diferente dos outros ...

e se achas que resolver isto me faz grande diferença, estás muito enganado 😄 estou simplesmente a espairecer do trabalho ...

Sign In

ONI'2013

Recommended Posts

Localhost

Top Posters In This Topic

Top Posters In This Topic

Popular Posts

Localhost

HappyHippyHippo

polska

SirDave

polska

Localhost

SirDave

mogers

polska

polska

mogers

polska

mogers

HappyHippyHippo

mogers

HappyHippyHippo

polska

mogers

mogers

HappyHippyHippo

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information