Oi.
Eu estou usando um vetor de referência para não precisar recalcular os valores que já foram uma vez calculados.
Com base no enunciado, fiz meu vetor de tamanho 1.000.000, mas pra alguns números (como 1819) o ciclo é tão grande que passa do 1.000.000. E pior: eu acho que provavelmente o Juiz está usando algum número de teste que passa do 1.000.000.
Só que no meu computador, tentar aumentar esse vetor pra 10.000.000 de ints (aproximadamente 80mb) dá segmentation fault de primeira e o gdb não me informa muita coisa sobre o que está acontecendo:
Program received signal SIGSEGV, Segmentation fault.
0x0804846f in main () at 3n.c:47
47 ref[n] = -1;
(47 é a linha onde inicializo o vetor de referências com -1)
Alguém fez sem esse vetor de referência e o programa roda num tempo bom? Alguém usou o vetor de referência de um tamanho suficiente para os testes do Juiz aceitarem o programa?
Eu tb usei um vetor com 1000000 de posicoes para nao precisar recalcular os ciclos abaixo de 1000000. O problema eh que se voce for calcular o ciclo de 999999 voce ira passar muito de 1000000. Por isso voce precisa verificar quando voce deve armazenar o tamanho do ciclo (sempre que for para um numero <= 1000000). Quanto a sua SegFault, das duas uma: Se for um vetor declarado (nao malocado) da segfault pq ele deve ser alocado na pilha do C, que costuma ter apenas 8mb. Se voce malocar, provavelmente 80mb passa do limite de memoria do juiz.
Mais uma coisa: Eu vi um programa que resolve este mesmo problema mas sem um vetor de referencia. Para resolver de 1 a 1000000 ele levou tempo na casa dos minutos, o que torna a solucao inviavel pois o juiz so permite algo proximo a 10 segundos.
Espero ter ajudado.
Mais uma coisa: Eu vi um programa que resolve este mesmo problema mas sem um vetor de referencia. Para resolver de 1 a 1000000 ele levou tempo na casa dos minutos, o que torna a solucao inviavel pois o juiz so permite algo proximo a 10 segundos.
Espero ter ajudado.
A solução mais trivial passa pelo juiz com tempo em torno de 7 segundos. A bateria de testes do juiz não deve considerar todas as entradas possiveis. Ele deve fazer uma amostra.
Em resposta à Andre Jucovsky Bianchi
Re: Tarefa 1: Vetor de referência
Dois lances que podem ajudar nesse sentido:
- Como o pessoal colocou, vetores muito grandes precisam ser alocados dinamicamente. Mas pense estatisticamente: você precisa guardar *todos* os cálculos prévios? Considere que os números menores ocorrem com mais freqüência (como parte de ciclos maiores), e guarde apenas os resultados até um certo ponto - eu consegui um ranking razoável no UVa (579 / 24116) guardando apenas 100.000 resultados (e acho que ainda dava pra otimizar, mas o foco não era esse).
- O enunciado garante que "no operation overflows a 32-bit integer" - note que nada é dito a respeito de sinal deste integer (perdi um bom tempo nisso)