Exo cargo

Bonjour,

L'exo cargo me rend fou. Il y a une question que j'aimerais poser a quelqu'un l'ayant réussi totalement :

Mon approche a été de faire un "algorithme complet à temps quelconque", ce qui me donne :
* soit je laisse l'algo se terminer, et la je temps est dépassé a partir du test 5 ou 6.
* soit j'introduis un timer, et je stoppe l'execution de l'algo avant la fin des 10 secondes, et la le dernier test ne va pas.

Ma question : est-ce que mon approche est bonne, et je dois chercher a optimiser les contraintes dans mon algo ? Ou bien je me plante complètement de direction, et il existe une solution non-exponentielle ?

Merci d'avance.

J'ai planché bien deux semaines sur le problème en essayant 5 ou 6 solutions bien différentes, toutes assez rapides mais ne passant pas certains tests. :S Finalement, il y en a une qui a marché, mais que je ne soupçonnais pas fonctionner quand j'y ai pensé (d'ailleurs, peut-être qu'un dixième test bien pensé la ferais se tromper, je n'en sais rien).

Peut-être qu'optimiser les contraintes te ferais passer les tests (je n'en sais rien, je n'ai pas ton code sous les yeux), mais pour moi, la solution que j'ai trouvé était loin des techniques auxquelles on pense dès le début.

Sauf erreur grossière d'analyse de ma part, il existe une solution non-exponentielle.

Moi j'ai deux algos pour l'instant...
Le premier est en fait un algo qui donne une réponse approchée. Je passe très facilement tous les tests au niveau temps, mais le 5° foire au niveau du résultat (les 8 autres sont bons :O).
Et puis le deuxième algo avec une jolie fonction récursive qui, bien que j'ai passé 2h à chercher où je pouvais l'améliorer et à ajouter quelques conditions, passe toujours pas : temps dépassé à partir du 6° test.

J'ai commencé aujourd'hui, j'ai une solution récursive en Python qui dépasse le temps au test 6. Au passage, pour le voir, j'utilise un test du type :

if not n in [2,4,5,20]:
print n
exit(0)

Sinon, la page des tests se charge indéfiniment, j'ai l'impression qu'il n'y a pas de limite de temps sur les programmes Python.

La complexité exacte ext de n parmi 2n, ou au mieux n-1 parmi 2n-1, ce qui donne :
u(n)=1/2*((2n!)/n!²)
Je n'ai pas trouvé d'équivalent simple, mais je crois que c'est une exponentielle assez forte: exp(n)=o(u(n))
il y a peut etre un équivalent de la forme u(n)\~exp(a*n) (a vue de nez a\~=sqrt(2)) ie u(n)\~=4.11\^n

oO, tu arrives à passer les tests avec une complexité pareille??
n parmi 2n c'est violemment pas polynomial ce truc... pour N=200 trucs ça m'étonnerais que ça passe... pour info, 200 parmi 400, ça fait 10295250013541443297297588032040198675721092538107764823484905957\\
5923332372651958598336595518976492951564048597506774120,
sauf erreur...

J'ai pas dit que je passais les tests, j'ai juste dit que l'algorithme est en complexité pire qu'une exponentielle. D'ailleurs, pour avoir une idée, il n'y a qu'à faire le calcul avec la formule de stirling :
n!\~sqrt(4*Pi*n)*(n/e)\^n
ce qui donne quelque chose en exp(n\^3/2) (ce qui est énorme)

moi j'ai une solution non exponentielle mais il y a un truc bizarre normalement on a
Exemple 2
en entrée ...
4
1000 2 3 4 5 6 7 2000
en sortie ...
991

et moi en sortie j'ai :
2000 - (1000 +2 + 3 + 4 + 5 +6 +7)=2000 -1027 = 973
je pense pas avoir trouvé un algo plus performant que les gars de prologin \^\^ mais je comprends pas mon erreur ...
le calcul n'est pas juste en mettant 2000 d'un coté et le reste de l'autre ?

Attention, il faut séparer les 2*N conteneurs en deux groupes de N conteneurs chacun. Ici, tu sépares en un groupe de 1 conteneur, et l'autre avec 7 conteneurs, ce qui est incorrect.

C'est clair que le fait de séparer en 2 rangées de N poids fait toute la difficulté de l'exercice.

mmmh a ouais donc j'avais pas compris la consigne >.moi j'ai essayé de les repartir pour qu'il soit le plus équilibrer ...
bon je vais testé avec la vrai consigne

Merci a tous pour vos réponses !

Après amélioration (au niveau des contraintes), si je laisse mon algo se terminer je dépasse le temps imparti sur deux tests (6 et 9). Si j'utilise un timer, je passe les 8 premiers tests (mais pas le 9e).

J'ai discuté avec une personne ayant réussi l'exo qui m'a conseillé de m'orienter sur la programmation dynamique, et la j'ai trouvé une solution qui marche, mais je ne puis jurer de sa validité (je sens que ma modélisation est louche).

Pour le calcul de la complexité, je ne peux pas vous aider, je suis nul en maths...

@+

Cet algo me titille.
J'avais fait deux programmes pour le Q.C.M de sélection mais au final je n'ai envoyé aucuns des deux puisqu'ils ne fonctionnaient pas.

Le premier était sûrement l'approche la plus intuitive, à savoir, trier les conteneurs puis rangés les conteneurs un par un. Seulement, il répond pas aux consignes pour certains rangements.
Le second, j'ai bidouillé un de mes programmes qui parcourait les sous ensembles d'un référentiel. Comme j'aurais du m'en douter ; bien trop lent.

Si quelqu'un peut m'aiguiller (sans parler de complexité, à part linéaire, quadratique et exponentiel c'est du charabia pour moi) par message privé ou sur ce sujet, ce serait bien aimable ;)

et la j'ai trouvé une solution qui marche, mais je ne puis jurer de sa validité (je sens que ma modélisation est louche).

En effet, ce n'est pas parce qu'un algorithme par exemple passe les tests qu'il est correct. Ainsi, j'ai un code très rapide et qui utilise très peu de mémoire, qui passe tous les tests de prologin et qui donnerait (à ce que quelqu'un m'a dit et à qui j'avais communiqué le code) la réponse correcte sur un million de cas et qui pourtant selon moi est incorrect ou en tous cas mathématiquement non prouvé (même si je n'ai pas de contre-exemple).

Pareil pour moi Candide. J'ai trouvé parmi toutes mes tentatives une solution très efficace qui passe les 9 tests, mais je suis sûr qu'en y réflechissant bien il y a un test qui la refuserait.

Le problème, c'est que cet exercice est difficile même à la main. A partir d'un certain nombre de containers (et pas si élevé qu'on pourrait le croire), trouver l'agencement parfait soi-même prend beaucoup de temps. Donc trouver des contre-exemples dans ce cas là... :S

Je te l'ai envoyé par message privé, oui.
[/joke] ;-p

C'est stupide... J'ai cherché partout comment lire mes MP, et n'ai pas trouvé...

Que m'as tu envoyé au juste ? (je ne demande pas de solution toute faite)

Désolé, je blaguais justement sur le fait que ce site n'a pas de fonctionnalité de message privé \^\^"... je n'ai pas ta réponse, désolé.