π
<-
Chat plein-écran
[^]

Résultats du TI-Concours 2017

En ligne

Résultats du TI-Concours 2017

Message non lude noelnadal » 21 Mai 2017, 16:59

Il y a un peu moins de trois semaines s'achevait la sixième édition du TI-Concours.

À présent, voici (enfin) les résultats ! :D

Petit résumé du concours

Le samedi 25 mars dernier, trois sujets ont été publiés. Chacun d'entre eux portait sur un thème différent (jeu, algorithmique, optimisation), et il fallait en faire au moins deux sur trois en 30 jours.

Peu avant la fin, le concours a été prolongé d'une semaine. Au final, nous avons reçu six participations valides, plus une septième qui n'a pas été retenue car ne comportant qu'un seul programme. Pour rappel, l'an dernier il y avait eu 7 participations dans cette catégorie, mais il était beaucoup plus facile d'obtenir une participation valide, étant donné qu'il suffisait de traiter une des 7 (courtes) questions. Ainsi, on peut estimer que les sujets ont eu plus de succès cette année, d'autant plus que je n'ai personnellement pas reçu de critique négative vis-à-vis de ces derniers, si ce n'est qu'ils étaient plus difficiles que d'habitude. :P

Les six participants ont traité exactement deux sujets : quatre ont fait le premier, six le deuxième, deux le troisième.

Résultats de l'épreuve 1

L'épreuve 1 consistait en la réalisation d'un jeu. Le joueur devait incarner STV, un super-héros de Bourg-la-Reine TI-Planet venu sauver le monde de l'invasion des technolapins. En fait, derrière ce scénario apocalyptique se cachait en fait un jeu de mémoire, qui devait être codé par les participants, tout en gardant le thème de départ. :p

Globalement, tous les programmes respectaient les consignes. La différence s'est faite sur des critères tels que l'originalité, l'esthétisme, la fluidité, la prise en main...

1) mgeorger (87)
2) Wistaro (79)
3) m@thieu41 (77)
4) cheuble (69)

mgeorger remporte donc un autocollant TI-Planet pour cette première place dans l'épreuve 1. :bj:

Résultats de l'épreuve 2

L'épreuve 2 proposait le problème d'algorithmique suivant : TI-Bot organise un tournoi entre les membres de TI-Planet pour déterminer qui fait les meilleures blagues sur le tchat. Chaque spectateur est intéressé par les matches (en un contre un) dont le niveau attendu est compris dans un certain intervalle. Comment déterminer pour chaque spectateur le nombre de matches différents possibles susceptibles de l'intéresser ?

Il y a eu quelques dégâts sur cette épreuve. Seuls trois participants sur 6 sont parvenus à passer tous les tests, les trois autres ayant codé un programme qui provoque (plus ou moins souvent) des erreurs de mémoire. Chose assez regrettable, personne n'est parvenu à trouver l'astuce géniale, qui permettait d'obtenir un algorithme assez rapide. :D

1) Ruadh (100)
2) Wistaro (63.13)
3) Dark_Coco (53.33)
4) m@thieu41 (36.87)
5) mgeorger (8.67)
6) cheuble (7.33)

Désolé grosged, je n'ai pas fait tourner ton programme, mais à la lecture du code il passait tous les tests aussi. :D

Bravo donc à Ruadh, dont la solution battait largement les autres en termes de vitesse d'exécution, même s'il ne m'a pas battu ( :troll: ). Il remporte un autocollant TI-Planet grâce à cette première place.

Résultats de l'épreuve 3

L'épreuve 3 demandait aux participants d'aider notre cher rédacteur Alvoko, réputé pour dessiner des oeuvres d'une qualité remarquable. Surchargé de commande à cause de sa notoriété, le but était de déterminer à qui et où envoyer des colis, afin de maximiser son bénéfice.

Malheureusement, cette épreuve fut un échec pour les deux participants qui s'y sont essayés. En effet, les deux programmes provoquaient des erreurs sur la quasi-totalité des tests.

1) Ruadh (8)
2) Dark_Coco (5)

Malgré tout, Ruadh est bien premier une nouvelle fois, et remporte donc un autre autocollant TI-Planet.

Résultats finaux

Cette année, comme tous les sujets n'étaient pas obligatoires, il avait été décidé dès le début que les scores seraient harmonisés, afin que des participants qui auraient traité un sujet plus difficile ne soient pas pénalisés. Il est clair que ce n'est pas la solution miracle, et vous pouvez si vous le souhaitez donner votre avis sur la pertinence d'un tel choix. On pourra, ou non, continuer ainsi pour des éditions ultérieures.

Une autre chose : cette année, il n'y avait plus de finale. Regrettez-vous cette disparition ? Ou une seule "manche" comme cette année convient ? N'hésitez pas à faire part de vos remarques (constructives).

Toujours est-il que le classement final de cette édition du TI-Concours 2017 est le suivant.

Image Première place : Ruadh

Image Deuxième place : Wistaro

Image Troisième place : mgeorger

Quatrième place : m@thieu41

Cinquième place : Dark_Coco

Sixième place : cheuble


Show/Hide spoilerAfficher/Masquer le spoiler
Image


Félicitations à Ruadh, qui remporte donc pour la deuxième fois le TI-Concours ! :#tritop#:
Il peut dès à présent contacter les administrateurs de TI-Planet pour réclamer le lot de son choix (descendre un peu pour la liste des lots). L'autre lot ira à Wistaro, deuxième du TI-Concours 2017. :bj:

Pour rappel, tous le monde ayant obtenu un score strictement positif, les six participants reçoivent un compte premium TI-Planet. :bj:

Merci à tous pour votre participation, et, je l'espère, à l'année prochaine ! :bj:
Avatar de l’utilisateur
noelnadalEcrivain
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Prochain niv.: 34.7%
 
Messages: 2252
Images: 0
Inscription: 10 Mar 2011, 00:00
Localisation: France, Melun (77)
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INRIA Paris
Twitter/X: nadalnoel
Facebook: noel.nadal1
GitHub: noelnadal

Re: Résultats du TI-Concours 2017

Message non lude grosged » 21 Mai 2017, 17:02

sincères félicitations !
Avatar de l’utilisateur
grosgedVIP++
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 30.2%
 
Messages: 770
Images: 75
Inscription: 14 Sep 2011, 12:29
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: Résultats du TI-Concours 2017

Message non lude critor » 21 Mai 2017, 17:04

Félicitations aux gagnants, ainsi qu'à tous les participants ! :D
Image
Avatar de l’utilisateur
critorAdmin
Niveau 19: CU (Créateur Universel)
Niveau 19: CU (Créateur Universel)
Prochain niv.: 41.4%
 
Messages: 41455
Images: 14353
Inscription: 25 Oct 2008, 00:00
Localisation: Montpellier
Genre: Homme
Calculatrice(s):
MyCalcs profile
YouTube: critor3000
Twitter/X: critor2000
GitHub: critor

Re: Résultats du TI-Concours 2017

Message non lude Wistaro » 21 Mai 2017, 17:10

Bravo à tous le monde!

Je veux bien connaître ton astuce miracle noelnadal :D

Honnêtement, j'étais loin d'imaginer avoir cette place.
Sur le sujet 2, je trouvais mon algo lent, et les autres (Ruadh, Mathieu....) me parlait de leur solution qui semblait beaucoup plus rapide que la mienne...
Désolé donc noelnadal d'avoir été peut-être un peu énervant vers la fin, j'étais quasi-certain de finir dans les derniers à cette épreuve, et donc au classement global...
Nouveau sur le site, Anonymous ? Avant de poster sur le chat et sur le forum, n'oublie pas de lire les règles. En cas de problème, tu peux m'envoyer un message, je réponds rapidement.

Liens utiles:
Image
Découvre mes programmes et mon site!
Avatar de l’utilisateur
WistaroSuper Modo
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 87.5%
 
Messages: 3152
Images: 37
Inscription: 25 Fév 2013, 16:21
Localisation: Toulouse
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: Ingénieur en électronique
YouTube: Wistaro
Twitter/X: Wistaro
GitHub: Wistaro

Re: Résultats du TI-Concours 2017

Message non lude Ruadh » 21 Mai 2017, 17:14

Félicitations à tous les participants !
Avatar de l’utilisateur
RuadhPremium
Niveau 13: CU (Calculateur Universel)
Niveau 13: CU (Calculateur Universel)
Prochain niv.: 37.5%
 
Messages: 38
Inscription: 11 Jan 2016, 23:19
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

En ligne

Re: Résultats du TI-Concours 2017

Message non lude noelnadal » 21 Mai 2017, 17:27

Alors l'astuce géniale, je vais vous en parler un petit peu. :p
Je précise que c'est une astuce qui rend l'algorithme asymptotiquement plus rapide, et donc, dans certains cas, l'algorithme de Ruadh par exemple fait l'affaire, notamment lorsque L1 prend des valeurs assez grandes.

Considérons la liste L4 (par exemple), définie comme suit : L4(i) est le nombre de participants dont le niveau est (i-1). On met (i-1) au lieu de i pour ne pas oublier les gens qui sont au niveau 0. À noter qu'une liste ne contient qu'au plus 999 éléments, donc il fallait typiquement en utiliser une deuxième pour stocker ce qui débordait.

En fait, on va considérer cette liste L4 comme un polynôme P(X) = L4(1) + L4(2)X + L4(3)X^2 + ... + L4(M)X^(M-1), avec M = dim(L4). Maintenant, si on calcule P(X) * P(X), puis que, pour chaque indice 1≤i≤M, on retranche L4(i)*L4(i) - (L4(i)*(L4(i)-1))/2 (qu'on peut simplifier, mais c'est pour que vous compreniez après) au coefficient 2i du polynôme résultant, alors, vous remarquerez que chaque coefficient j du résultat est égal au nombre de matches possibles de niveau j. :D

Ensuite, pour que le programme soit réellement efficace, il fallait multiplier le polynôme par lui-même de manière rapide. On pouvait par exemple utiliser l'algorithme de Karatsuba (https://fr.wikipedia.org/wiki/Algorithme_de_Karatsuba), ou, si vous êtes courageux, l'algorithme utilisant la Transformée de Fourier Rapide, en plus efficace asymptotiquement, mais assez compliqué à comprendre et à coder. Dans les deux cas, il fallait implémenter un algorithme récursif en TI-Basic (e)z80, ce qui n'est pas si facile que ça... :P

Après, on pouvait utiliser la technique des sommes partielles pour répondre à chaque spectateur en temps constant.

À noter que je n'ai pas eu le courage d'implémenter la méthode avec la Transformée de Fourier Rapide. Je ne suis même pas sûr qu'elle ait un meilleur score, vu qu'il faut en théorie atteindre des valeurs de N assez élevées pour que ça ait un intérêt.

Notez aussi que pour stocker le polynôme résultant, il faut utiliser au moins deux listes, ce qui complique l'implémentation. Mais bon, vous aviez presque 37 jours, et aussi, on pouvait utiliser des matrices... ;)
Avatar de l’utilisateur
noelnadalEcrivain
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Prochain niv.: 34.7%
 
Messages: 2252
Images: 0
Inscription: 10 Mar 2011, 00:00
Localisation: France, Melun (77)
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INRIA Paris
Twitter/X: nadalnoel
Facebook: noel.nadal1
GitHub: noelnadal

Re: Résultats du TI-Concours 2017

Message non lude Wistaro » 21 Mai 2017, 17:39

Je pas sûr d'avoir bien compris ton algo..
Quel rapport entre la FFT et la multiplication rapide de polynômes..?
Nouveau sur le site, Anonymous ? Avant de poster sur le chat et sur le forum, n'oublie pas de lire les règles. En cas de problème, tu peux m'envoyer un message, je réponds rapidement.

Liens utiles:
Image
Découvre mes programmes et mon site!
Avatar de l’utilisateur
WistaroSuper Modo
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 87.5%
 
Messages: 3152
Images: 37
Inscription: 25 Fév 2013, 16:21
Localisation: Toulouse
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: Ingénieur en électronique
YouTube: Wistaro
Twitter/X: Wistaro
GitHub: Wistaro

En ligne

Re: Résultats du TI-Concours 2017

Message non lude noelnadal » 21 Mai 2017, 17:58

Wistaro a écrit:Je pas sûr d'avoir bien compris ton algo..
Quel rapport entre la FFT et la multiplication rapide de polynômes..?


Il existe un algorithme quasi-linéaire en temps de multiplication de polynôme utilisant la FFT.
Avatar de l’utilisateur
noelnadalEcrivain
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Prochain niv.: 34.7%
 
Messages: 2252
Images: 0
Inscription: 10 Mar 2011, 00:00
Localisation: France, Melun (77)
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INRIA Paris
Twitter/X: nadalnoel
Facebook: noel.nadal1
GitHub: noelnadal

Re: Résultats du TI-Concours 2017

Message non lude m@thieu41 » 21 Mai 2017, 18:47

Bravo à tout le monde ! :)

Considérons la liste L4 (par exemple), définie comme suit : L4(i) est le nombre de participants dont le niveau est (i-1). On met (i-1) au lieu de i pour ne pas oublier les gens qui sont au niveau 0. À noter qu'une liste ne contient qu'au plus 999 éléments, donc il fallait typiquement en utiliser une deuxième pour stocker ce qui débordait.

En fait, on va considérer cette liste L4 comme un polynôme P(X) = L4(1) + L4(2)X + L4(3)X^2 + ... + L4(M)X^(M-1), avec M = dim(L4). Maintenant, si on calcule P(X) * P(X), puis que, pour chaque indice 1≤i≤M, on retranche L4(i)*L4(i) - (L4(i)*(L4(i)-1))/2 (qu'on peut simplifier, mais c'est pour que vous compreniez après) au coefficient 2i du polynôme résultant, alors, vous remarquerez que chaque coefficient j du résultat est égal au nombre de matches possibles de niveau j. :D


Du coup pour stocker P², il faut 4 listes :p

C'est assez ressemblant à ce que j'ai fait (j'ai essayé de faire un segment tree (avec des matrices pour les dépassements de mémoire... beurk)), sauf que tu gagnes du temps sur la génération, moi sur la récupération des valeurs.


Argh des erreurs mémoire ? Quand ça ? :'(


Quelle était la stratégie des autres ?
Avatar de l’utilisateur
m@thieu41Premium
Niveau 11: LV (Légende Vivante)
Niveau 11: LV (Légende Vivante)
Prochain niv.: 71.3%
 
Messages: 230
Inscription: 20 Juin 2013, 14:24
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: TS

En ligne

Re: Résultats du TI-Concours 2017

Message non lude noelnadal » 21 Mai 2017, 19:16

Concrètement la taille de ta matrice [A] dépendait de max(L1), et pour des valeurs élevées, ça me faisait une erreur mémoire. Typiquement, pour max(L1) = 1337, t'avais une matrice de taille 55*98, un truc comme ça... :P

La plupart des gens ont opté pour une approche naïve, plus ou moins bien implémentée, qui consistait à regarder pour chaque match distinct et chaque requête s'il fallait incrémenter le résultat ou pas. Ça mettait pas mal de temps à tourner, il faut le dire... :P
Avatar de l’utilisateur
noelnadalEcrivain
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Prochain niv.: 34.7%
 
Messages: 2252
Images: 0
Inscription: 10 Mar 2011, 00:00
Localisation: France, Melun (77)
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INRIA Paris
Twitter/X: nadalnoel
Facebook: noel.nadal1
GitHub: noelnadal

Suivante

Retourner vers News Divers

Qui est en ligne

Utilisateurs parcourant ce forum: Noeap et 27 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
857 utilisateurs:
>833 invités
>19 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)