Jump to content

Recommended Posts

Posted

Boas,

Antes de mais um conselho, nas constantes (MAX, SQRT_MAX) mete sempre um pouco mais do que o necessário.

Estive a ver o teu código e notei um pequeno erro, onde tens:

for(j=n_sqrt*i; j<n_sqrt*(i+1) && j<=N; j++)

Deveria estar:

for(j=n_sqrt*i; j<n_sqrt*(i+1) && j<N; j++)

Talvez isso possa estar a causar algum erro e daí o TLE pois pelo que vi deveria passar no tempo. Contudo há algumas coisas que poderiam ser optimizadas. Corrige este erro e caso continues com TLE diz. O(n sqrt n) é suficiente para os 100 pontos.

"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.."

  • Replies 137
  • Created
  • Last Reply

Top Posters In This Topic

Posted

Continua nos 62 TLE.

Warrior, penso que o problema não seja o casting, lembrei-me de ir ver a solução do xtrmo que está aqui no fórum e ele pareceu não ter problemas com isso..

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted (edited)

Não, eu ainda no outro dia fiz com sqrt n e deu 100.

15
400 500 122 123 312 300 312 312 213 12 311 123 1 0 15
10
5 6
5 7
5 8
5 9
5 10
6 15
6 14
6 13
7 12
1 4

Experimenta isso.

Edit

Isso diz TLE e se calhar podes também ter WAs mas aquilo só avisa do erro mais importante (TLE). Pelo menos acho que o Mooshaq funciona assim, é melhor alguém clarificar isso.

Edited by SirDave

Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!

Posted
312 5
312 5 7
312 5 7 8
312 5 7 8
312 5 7 8
312 7 8
312 7 8
312 7 8
312 7 8
500 2

Não é um teste muito manhoso esse :b .. Anyway, já fiz com alguns testes onde inf e sup são iguais e fiz outros testes também triviais e funcionou direito, se calhar estou a ter wrong answer nos testes maiores (ainda não experimentei nenhum teste muito grande), mas não percebo onde estará o erro.

vou deixar o código actual:

//EX.A - QUALIFICAÇÃO 2009

#include <stdio.h>
#include <math.h>
#define MAX 50010
#define SQRT_MAX 240

int N, F, inf, sup, n_sqrt, maxi;
int alturas[MAX], maximos[sQRT_MAX], n_indices[sQRT_MAX], indices_max[sQRT_MAX][sQRT_MAX];

int max(int a, int b)
{
if(a>b) return a;
return b;
}

void pre_process()
{
int i, j;
for(i=0; i<=n_sqrt; i++)
{
	maximos[i] = 0;
	for(j=n_sqrt*i; j<n_sqrt*(i+1) && j<N; j++) // && j<N -> para não passar o limite caso o ultimo bloco não tenha n_sqrt posições
	{
		maximos[i] = max(maximos[i], alturas[j]);

		if(indices_max[i][0] == -1)
		{
			indices_max[i][0] = j;
			n_indices[i] = 1;
		}
		else if(alturas[j] == alturas[indices_max[i][n_indices[i]-1]])
		{
			indices_max[i][n_indices[i]] = j;
			n_indices[i]++;
		}
		else if(alturas[j] > alturas[indices_max[i][n_indices[i]-1]])
		{
			indices_max[i][0] = j;
			n_indices[i] = 1;
		}

	}
}	
}

void process()
{
int i, j, bucket, limite, bucket_limite;
maxi = 0; //maior altura

/* bucket fronteira A */
bucket = inf / n_sqrt;
limite = (bucket+1)*n_sqrt;

for(i=inf; i<limite && i<=sup; i++)
	maxi = max(maxi, alturas[i]);	

/* buckets interiores */
bucket_limite = sup / n_sqrt;
for(j=bucket+1; i<bucket_limite; j++, i = i+n_sqrt)
	maxi = max(maxi, maximos[j]);

/*buckets fronteira B*/
for(; i<=sup; i++)
	maxi = max(maxi, alturas[i]);

return;
}

void sol()
{
int i, j, k, bucket, limite, bucket_limite;

printf("%d", maxi);

/* bucket fronteira A */
bucket = inf / n_sqrt;
limite = (bucket+1)*n_sqrt;

for(i=inf; i<limite && i<=sup; i++)
	if(alturas[i] == maxi)
		printf(" %d", i+1);

/* buckets interiores */
bucket_limite = sup / n_sqrt;
for(j=bucket+1; i<bucket_limite; j++, i = i+n_sqrt)
	if(alturas[indices_max[j][0]] == maxi)
		for(k=0; k<n_indices[j]; k++)
			printf(" %d", indices_max[j][k]+1);


/*buckets fronteira B*/
for(; i<=sup; i++)
	if(alturas[i] == maxi)
		printf(" %d", i+1);

printf("\n");
return;
}

int main()
{
int i, j;

//inicializar n_indices e indices_max
for(i=0; i<SQRT_MAX; i++)
{
	n_indices[i] = 0;
	for(j=0; j<SQRT_MAX; j++)
		indices_max[i][j] = -1;
}

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

n_sqrt = sqrt(N);	
pre_process();	

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

	process();
	sol();
}

return 0;
}

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted

E tens a certeza que isso funciona para casos em que o A e o B estão no mesmo bucket?

Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!

Posted (edited)

E tens a certeza que isso funciona para casos em que o A e o B estão no mesmo bucket?

Nos testes que fiz funcionou, mas por via das dúvidas fui agora fazer esse teste com o input de exemplo, e também funcionou.

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted

Em testes aleatorios que criei, o teu programa responde certo. No entanto, demora ~6 segundos no caso máximo, enquanto que o meu é instantâneo.

vou olhar melhor para o teu código, mas sugiro que construas a lista de indices logo no process

"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.

Posted

Em testes aleatorios que criei, o teu programa responde certo. No entanto, demora ~6 segundos no caso máximo, enquanto que o meu é instantâneo.

vou olhar melhor para o teu código, mas sugiro que construas a lista de indices logo no process

Olha que é bem capaz de ser isso (pode é haver mais coisas), eu no meio construí no process (aliás, preprocess).

Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!

Posted (edited)

Não o fiz já no pre_process?

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted
       /*buckets fronteira B*/
       assert(sup-i <= n_sqrt);
for(; i<=sup; i++)
               maxi = max(maxi, alturas[i]);

O assert é accionado, ou seja, tás a percorrer mal os buckets e este ultimo for percorre mais de sqrt(N) elementos.

"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.

Posted

Não o fiz já no pre_process?

Ah, parece que sima final, o indices_max é criado no preprocess.

Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!

Posted

Não o fiz já no pre_process?

Eu referia-me a lista de indices da resposta. Ou seja, fazeres o sol() logo no process()

"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.

Posted (edited)

       /*buckets fronteira B*/
       assert(sup-i <= n_sqrt);
   for(; i<=sup; i++)
               maxi = max(maxi, alturas[i]);

O assert é accionado, ou seja, tás a percorrer mal os buckets e este ultimo for percorre mais de sqrt(N) elementos.

Não tinha dado por ela daquele erro, estava ali a fazer uma condição sem nexo nenhum no for que percorre os buckets interiores 😄 ..

Já consegui os 100, aleluia ahah, Obrigado ao pessoal todo que ajudou!

Eu referia-me a lista de indices da resposta. Ou seja, fazeres o sol() logo no process()

Vou alterar isso, também 😉

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted

Não tinha dado por ela daquele erro, estava ali a fazer uma condição sem nexo nenhum no for que percorre os buckets interiores 😄 ..

Já consegui os 100, aleluia ahah, Obrigado ao pessoal todo que ajudou!

Vou alterar isso, também 😉

Parabéns 🙂

Agora, tão importante como teres resolvido o problema, é melhorares o código para que seja tão pequeno quanto possível (mantendo-o organizado em funções e afins), eliminando essas coisas desnecessárias.

"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.

Posted

Parabéns 🙂

Agora, tão importante como teres resolvido o problema, é melhorares o código para que seja tão pequeno quanto possível (mantendo-o organizado em funções e afins), eliminando essas coisas desnecessárias.

É o que estou a fazer 😉 , obrigado

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted

E se depois, por curiosidade, quiseres comparar com o meu código, estás à vontade:

https://gist.github.com/davidgomes/ec99925cfa43c8c695e2 (aquilo do 123456 é um dirty hack muito manhoso)

gosto sempre de ver a solução de outros concorrentes 😉 , vou dar uma espreitadela.

Já agora, @Warrior, a propósito da função memset, como é que a uso para arrays bidimensionais?

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Posted (edited)

Sem ter a certeza absoluta, mas ainda ontem o Vegetais disse-me que não interessa. Usas o memset normalmente (memset(array, 0, sizeof array)) que ele limpa tudo.

Edited by SirDave

Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!

Posted (edited)

Um array bidimensional é guardado da mesma forma que um array com 1 dimensão, todas as posições seguidas na memória.

Quando fazem

int v[100];

v[5]; // traduzido em: v + 5*sizeof(int)

int m[100][50];

m[2][3]; // traduzido em: m + 2* 50 * sizeof(int) + 3 * sizeof(int),
// 2* 50 porque é a 2ª linha e em C/C++ os arrays bidimensionais são guardados linha-a-linha,
// 50 colunas da 1ª linha, 50 colunas da 2ª linha, etc.

// o "sizeof m" dá o tamanho da matriz em bytes.
// Como a matriz é guardada em posições seguidas da memória, limpa tudo.
memset( m, 0 , sizeof m);
Edited by mogers

"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.

Posted (edited)

Sem ter a certeza absoluta, mas ainda ontem o Vegetais me disse que não interessa. Usas o memset normalmente (memset(array, 0, sizeof array)) que ele limpa tudo.

O que é que não interessa? O uso do memset?

Usas o memset normalmente (memset(array, 0, sizeof array)) que ele limpa tudo.

Obrigado

Um array bidimensional é guardado da mesma forma que um array com 1 dimensão, todas as posições seguidas na memória.

Quando fazem

int v[100];

v[5]; // traduzido em: v + 5*sizeof(int)

int m[100][50];

m[2][3]; // traduzido em: m + 2* 50 * sizeof(int) + 3 * sizeof(int),
// 2* 50 porque é a 2ª linha e em C/C++ os arrays bidimensionais são guardados linha-a-linha,
// 50 colunas da 1ª linha, 50 colunas da 2ª linha, etc.

// o "sizeof m" dá o tamanho da matriz em bytes.
// Como a matriz é guardada em posições seguidas da memória, limpa tudo.
memset( m, 0 , sizeof m);

Obrigado

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

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
×
×
  • 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.