Résultats du TI-Concours 2017

[Epharius]

Il ne veut pas l'avouer mais noenadal voulait un autre algorithme plus performant pour son site de tetris-battles mais il a été déçu personne ne l'a surpassé.
Une prochaine fois...

[m@thieu41]

I'm stupid

Pour moi on pouvait faire des matrices 40*99 sans problème... C'est "juste" 4 listes remplies à bloc quoi...
En fait on ne pouvait faire aucun précalcul, tout stocker de façon brute comme tu l'as fait avec 2 listes nous amène déjà au bord de la mémoire x)
Tant pis c'était marrant à coder


Quelle a été l'approche de Ruadh ?

[noelnadal]

Si on supprime la liste L1 après avoir construit le "polynôme", ça libère pas mal de place, déjà.
Autre optimisation possible, fusionner L2 et L3 pour ne faire qu'une seule liste (stocker 10001*L2(i)+L3(i) par exemple ).

Ruadh a fait un truc assez simple (similaire aux autres), mais très bien implémenté. Le mieux serait qu'il publie son code.

[Ruadh]

Je l'ai publié ici : http://ti-pla.net/a965495
A chaque itération, je stock le dernier élément de L1 et je l'enlève de la liste en diminuant la dimension. Ensuite je l'ajoute à tous les autres éléments restants de la liste et je stock ça dans une autre liste. Finalement je compare cette liste à L2(i) et L3(i) pour tout i et j'ajoute la somme à L4(i).

[m@thieu41]

Du coup noel ta solution est en O(Mlog(M) + PM) c'est ça ? (M=maxL1)

Bien vu le coup de stocker plusieurs info dans la même case ^^
Avec ça y doit y avoir moyen de stocker le segment tree en entier, et, avec ta génération, de tomber à une complexité en O(Mlog(M) + Plog(M)).

[noelnadal]

Si je ne fais pas d'erreur, la complexité exacte est O(N+M) pour construire le polynôme, O(Mlog(M)) pour faire les calculs dessus, O(M) pour calculer les sommes partielles et O(P) pour calculer toutes les requêtes. Soit un truc dans le genre O(Mlog(M) + N + P).

Ceci est mon 2000ème message.

[m@thieu41]

Oui effectivement, on peut calculer les sommes partielles c'est plus simple, bien vu

[loupiot]

bien joué à tous
belle initiative malgré le peu de participants
promis, la prochaine fois je suis de la partie

[Dark coco]

Bien joué à tous ☺
Je veux bien une explication du sujet 2

[Dark coco]

Non je rigole c'est le sujet 3 qui faut surtout m'expliquer