skiller10 Posted March 26, 2013 at 05:10 AM Report #500402 Posted March 26, 2013 at 05:10 AM 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.."
polska Posted March 26, 2013 at 01:25 PM Report #500450 Posted March 26, 2013 at 01:25 PM 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.
SirDave Posted March 26, 2013 at 02:29 PM Report #500458 Posted March 26, 2013 at 02:29 PM (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 March 26, 2013 at 02:30 PM by SirDave Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!
polska Posted March 26, 2013 at 03:06 PM Report #500463 Posted March 26, 2013 at 03:06 PM 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.
SirDave Posted March 26, 2013 at 03:08 PM Report #500464 Posted March 26, 2013 at 03:08 PM 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!
polska Posted March 26, 2013 at 03:14 PM Report #500467 Posted March 26, 2013 at 03:14 PM (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 March 26, 2013 at 03:16 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
mogers Posted March 26, 2013 at 03:29 PM Report #500468 Posted March 26, 2013 at 03:29 PM 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.
SirDave Posted March 26, 2013 at 03:30 PM Report #500469 Posted March 26, 2013 at 03:30 PM 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!
polska Posted March 26, 2013 at 03:38 PM Report #500471 Posted March 26, 2013 at 03:38 PM (edited) Não o fiz já no pre_process? Edited March 26, 2013 at 03:38 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
mogers Posted March 26, 2013 at 03:38 PM Report #500472 Posted March 26, 2013 at 03:38 PM /*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.
SirDave Posted March 26, 2013 at 03:40 PM Report #500473 Posted March 26, 2013 at 03:40 PM 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!
mogers Posted March 26, 2013 at 03:50 PM Report #500476 Posted March 26, 2013 at 03:50 PM 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.
polska Posted March 26, 2013 at 04:04 PM Report #500481 Posted March 26, 2013 at 04:04 PM (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 March 26, 2013 at 04:04 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
mogers Posted March 26, 2013 at 04:18 PM Report #500482 Posted March 26, 2013 at 04:18 PM 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.
polska Posted March 26, 2013 at 04:23 PM Report #500483 Posted March 26, 2013 at 04:23 PM 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.
SirDave Posted March 26, 2013 at 04:28 PM Report #500484 Posted March 26, 2013 at 04:28 PM 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) Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!
polska Posted March 26, 2013 at 05:34 PM Report #500505 Posted March 26, 2013 at 05:34 PM 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.
SirDave Posted March 26, 2013 at 05:35 PM Report #500506 Posted March 26, 2013 at 05:35 PM (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 March 26, 2013 at 06:12 PM by SirDave Be nice to see your eyes, blink them from time to time to relax your retina when using the computer. Blink now!
mogers Posted March 26, 2013 at 05:47 PM Report #500508 Posted March 26, 2013 at 05:47 PM (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 March 26, 2013 at 05:49 PM 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.
polska Posted March 26, 2013 at 06:06 PM Report #500510 Posted March 26, 2013 at 06:06 PM (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 March 26, 2013 at 06:08 PM by polska Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now