GCJ round 1C
dim, 23/05/2010 - 11:01 — Sekler
Je propose de discuter de ce round ici, plutôt que dans les pages lointaines d'un autre topic.
Bon biensur, il ne faut pas s'échanger de réponses pendant l'épreuve parce que je suis sur que Google va trouver ce topic ^^.
Sinon, début imminent!
Bon courage!
- Vous devez vous identifier ou créer un compte pour écrire des commentaires
Suivez-nous !
Les partenaires grâce à qui Prologin peut exister :
Raaaaaaaaaaaaah, ça me tue !
Entre le tab[15] pour 15 tests commençant à 1 et finissant à 15 qui m'a coûté 15 points (lecture en tab[15] en dehors du tableau, quelle idée de numéroter les tests en partant de 1), et l'utilisation d'int au lieu de long long qui m'ont coûté 22 points... Je bouclais infini à cause de ça... sur kubuntu mon rpogramme prenait 45 Go de mémoire d'après sysmonitor. Du coup hop, rapide reboot sur xp à 4 minutes de la fin du temps, idem. Le temps que je voie que je boucle infini, que je change le truc, évidemment les 8 minutes étaient écoulées...
Du coup Là je suis 822°, et pas vraiment la motivation de faire le 3...
200 places de perdues pour une erreur à la con comme ça. Morale : si on a un programme qui doit tourner en moins de 5 secondes, ne pas le laisser tourner 5 minutes en espérant !
Edit : 858° : -36 places en 2 minutes, ça promet...
Bon je suis vraiment nul en maths, j'ai pas trouvé la formule magique pour l'exo 2.
Ha ha :D
http://img7.imageshack.us/img7/456/formuler.png
Ne vous inquiétez pas, les gens, la phrase de TLN n'était pas une implication de droite à gauche :) (c'est juste lui qui est nul en mathématiques).
Edit : De gauche à droite, donc.
Président Prologin 2012
Perso, j'ai même pas compris les tests pour le B.
Au final, j'aurais fait le A-small et large des trois sessions, mais aucun B et aucun C. :( C'est d'un calibre au-dessus de moi le GCJ, j'vais en rester à Prologin.
Merci Jill-Jênn pour cette image, mais je sais encore lire des codes source =)
Au moins j'ai fini dans les 200 premiers pour le round C, moi. A croire que les meilleurs sont vraiment partis dans les round A et B xD (enfin je parle pas des torches qui finissent encore les 3 pb en moins d'une heure hein).
Ca va être juste chaud pour le round 2. J'espère qu'il y aura plus de graphes et moins d'arithmétique :p
Pikrass → En cherchant à t'expliquer, je me suis rendu compte que je ne comprenais pas vraiment le problème, j'ai juste compris ce qu'il fallait faire xD
*cherche*
Edit : Ah voilà. Tu sais que le site supporte L visiteurs ou moins, tu sais qu'il ne supporte pas P visiteurs ou plus, mais entre les deux tu ne sais pas. Tu peux juste le savoir pour un X que tu choisis. Et en fait, tu cherches a tel que a est supporté mais pas a.C. Et tu veux être sûr de trouver a en le moins d'étapes possible. Pour être sûr de le trouver, il faut envisager le pire cas.
Par exemple, pour L = 24, P = 97, C = 2.
Tu testes 48. Si 48 n'est pas supporté, alors a = 24 convient. Un test suffit.
Si 48 est supporté, ben tu es embêté vu que tu ne sais pas si 96 l'est ou pas. Il faut deux tests.
Si 96 est supporté, a = 96 conviendra. S'il n'est pas supporté, a = 48 conviendra.
En fait, c'est comme une dichotomie, sauf qu'au lieu de la moyenne arithmétique, on utilise la moyenne géométrique : √(m × n).
En fait, on cherche le plus petit k tel que (P/L)^(1/2^k) ≤ C.
Président Prologin 2012
Bah j'avais compris les tests où il y avait les explications, mais j'ai jamais trouvé la stratégie optimale pour L=1, P=1000, C=2, ni pour L=50, P=700, C=2. :-/
A noter qu'il y a des analyses (avec solutions) des différents problèmes abordés disponibles sur le site :
http://code.google.com/codejam/contests.html
Et étrangement, pour le pb C, je m'en suis sorti avec un algo' en O(m²n²) :p
Pikrass → OK mais maintenant, tu as compris le coup de la dichotomie multiplicative ?
Edit : LOOL TLN, regarde ce qui est écrit sur le site : « If we do that, we will have a O(m²*n²) algorithm, which is too slow. »
Président Prologin 2012
Après avoir lu l'analyse, c'est beaucoup plus clair. :p
En gros, il aurait fallu que je mette tout ça sous forme d'équations/inéquations. Mais j'suis pas encore assez atteint pour résonner avec des maths dès que je vois un problème. :D (contrairement au forum d'xkcd, mwarf)
Après avoir lu l'analyse, je me suis dit qu'il faudrait que j'aprenne l'anglais :p
Edit : LOOL TLN, regarde ce qui est écrit sur le site : « If we do that, we will have a O(m²*n²) algorithm, which is too slow. »
Ben justement, c'est pour ça que j'ai dis que je m'en suis quand même sorti avec un tel algo' banaste :p
Enfin j'ai dû mettre 2-3 min à calculer le large input, ce qui est effectivement trop lent, mais m'a quand même permis de submit =)
« Après avoir lu l'analyse, je me suis dit qu'il faudrait que j'aprenne l'anglais :p »
apprenne*
Apprends le français, déjà :D
Moi j'ai trouvé la solution du B, apparemment, mais int au lieu de long long, et paf mon rpogramme qui devait tourner en 2 secondes maxi bouclait indéfiniment. Avec kubuntu qui m'indiquait que ça utilisait 49 Go de mémoire =O
Bref, sur cette petite erreur, j'ai perdu 500 places et justement ma place pour le tour d'après.
Vivement l'année prochaine !
La prochaine fois utilise des num' en caml :p
Tiens d'ailleurs je sais même pas s'il y a des entiers de précision arbitraire en C++. Sans doute =/
Non, pas d'entiers de précision arbitraire en C++, même pas dans le nouveau draft que je sache… Il n'y a que les user-defined literals (n3092 2.14.8) qui pourraient nous simplifier un peu la vie dans le codage des « Bignum ».
Mais [troll] le C++ c'est bon, mangez en.
Thou hast angered me.
A wide-angle disintegration beam hits you!
Pikrass → raisonner* xD
Artifère → Alors, 45 ou 49 Go ? Décide-toi :D Et puis perso je n'avais que des int.
Président Prologin 2012
:( je n'ai eu le temps de participer à aucun des 3 1ers rounds :(
Haha, la faute de pikrass est pire que la mienne ( enfin, je pense... (donc je suis)). Dommage artix...
Teuh teuh teuh, "aprenne", c'est au moins aussi moche, voire plus, que "résonner".
Mouais, tout est relatif.
Moi une fois sur une copie de maths, j'avais marqué "on résonne par récurrence sur n ...", et j'avais pas compris la remarque en rouge du prof' "comme un tambour ?" ... °°
Adad ?
http://mpsi3.thiers.free.fr/perles/maths2.jpg
Président Prologin 2012
Non, Wigneron =)