SRM 504.5‏

Paul ou alex3er pour m'expliquer ce 0.5 ?
Ou d'autres bien sûr. :)
Peut-être que ça se déroule en deux temps ?? Peu probable enfin bon.

Bah c'est un clin d'oeil à H2G2!
Sinon: C'est pas le match 504 qui avait bugué? Les changements de classements ont même été annulés.

Tiens, TLN participe.
Ce sera son deuxième SRM et il est trop fort d’abord.

Je suis surtout un peu rouillé en ce moment xD
Y a qu'à voir le score minable que j'ai fait au 1er round de qualif pour le TCO : TLE sur le premier problème :D

Ah je croyais que tu avais oublié de participer et que tu t'étais seulement inscrit \^\^

Edit: Ah oui effectivement :p

Edit: Bonne chance

Edit: Tu pourras m'expliquer après la fin du concours pourquoi mon code ne marche pas pour le 1000-points? Il est super court, et marche pour les 3 premiers exemples, mais pas pour le 4ème.... Je mettrai sur ideone si t'es d'accord.

Qu'est ce que ça m'enerve de perdre des points en lançant des challenges à des codes naifs dont la complexité est extremement loin de la complexité optimale....

Ahah, moi j'ai lancé 3 challenge, dont 1 seul a été successful xD
Au final j'ai rien gagné ni perdu donc. Mais bon le mec pour le pb 1 qui se contente de faire « while (jackpot) { array[0]++; array.sort(); } » et où tu te dis que ça passe sur l'input maximal ... ben c'est un peu triste quoi \^\^

Le même .... J'ai challengé deux mecs qui avaient fait ça, mais pas exactement pareil, ben rien à faire...

Et sinon, j'ai fait de la merde.... (le 2 était tout con et je suis allé chercher compliqué. Par contre pour le 3???? J'ai pas compris pourquoi ça passait pas...)

Vous pensez que du O(N²logN) avec N:o :o
50*50*6=15 000

Bah en fait c'est plutot du KNlogN , avec KDonc au max 282 000 000 à la place de 47 000 000
Et puis... Je trouve qu'ils auraient dû baisser les limites de temps. Les problèmes à 250 points c'est toujours des trucs super simples, mais là c'était bien pire que d'habitude. D'ailleurs, je m'en vais de ce pas donner une mauvaise note à ce problème.

C'est moi ou aujourd'hui tout était facile? Les codes de la division 1 sont 5 fois plus courts que d'habitude! (surtout le dernier)

Oui c'est du O(k*n*log(n)) si tu codes comme un pieds. Même en distribuant naïvement et en évitant de refaire un shuffle à chaque fois on peut s'en sortir en O(k + n*log(n)) (faire une liste des "paliers" + donner un jeton au dernier élément du premier palier à chaque fois). Il y aussi moyen de faire ça en O(Δ + n*log(n)) où Δ = max(money) - min(money), le plus grand écart entre les quantités d'argents possédées par les différents amis.

Ainsi on s'abstrait du facteur k dans l'algorithme, ce qui est avantageux quand on est rendu au point où tous les amis ont la même quantité d'argent (on sait comment répartir ce qu'il nous reste en un seul coup). C'est pour ça que j'aurai bien aimé qu'on ait eu des limites plus larges \^\^

D'un autre côté la solution que j'ai codée a planté à cause d'une connerie sur les indices ... je vous avais dis que j'étais rouillé =)

J'ai été étonné que tu n'aie pas donné de solution pour le 500, il était très simple ( bon, je l'ai raté, mais parce que j'ai merdouillé).
Et pour moi, j'ai trouvé que le KN pour le 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

 sort(money.begin(),money.end());
      int c2=0;
      for(int c=0;c < jackpot;c++)
      {
        while(c2 > 0&&money[c2] > money[c2-1])
          c2--;
        while(c2 < money.size()-1&&money[c2] > =money[c2+1])
          c2++;
        money[c2]++;
      }
      return money;

TLN : on peut surtout le faire en O(N) si le sujet ne demandait pas les poids triés ;)

2 s à 2.3 GHz... effectivement le gros bourrin était limite. :/

Mais euh! Je pige pas, c'est quoi l'algo en O(N)?

Si l'algo ne demandait pas les poids triés il aurait surtout été impossible de répondre de manière déterministe en cas d'égalité pour les amis les plus pauvres. Ou alors dire qu'il y a au plus 2\^k vecteurs de réponse possible pour une certaine configuration donnée, avec k compris entre 0 et n, mais je ne sais pas s'ils font des juges spéciaux quand un problème peut avoir plusieurs solutions.

L'algo en O(N) doit sûrement utiliser les matrices. :P
(Je précise que je n'ai pas fait le SRM d'aujourd'hui.)

Hmmm ... Qu'est-ce que "SRM" ? Le premier résultat google tombe sur des t-shirts et le deuxième sur ça : http://www.commentcamarche.net/contents/entreprise/srm.php3
Ce qui signifie ... Que ce n'est pas ce que je cherche.

Un petit indice sur l'endroit où aller pour trouver ces problèmes ? \^\^

Top coder

OK, merci. Je vais essayer de comprendre le site, souhaitez-moi bon courage, il y en a de partout, pire que dvpz à première vue ... x)

Je trouve leur site web merdique à Topcoder. Honnêtement les infos sont planquées n'importe où, il faut ouvrir 3 menus déroulant pour atterrir sur une page avec des explications datant de 2003, etc.

Je veux bien croire que « TopCoder is revolutionizing the software design and development process by tapping in to our unlimited global community to work for you. », mais en tout cas c'est pas le web design qu'ils révolutionnent.

Enfin bref, les liens utiles pour commencer c'est :
* Infos sur les SRM : http://apps.topcoder.com/wiki/display/tc/Algorithm+Overview
* Infos sur le fonctionnement de l'arène : http://apps.topcoder.com/wiki/display/tc/The+Algorithm+Competition+Arena
* Infos sur les plug-in que tu peux utiliser avec l'arène (parce que par défaut c'est un peu pauvre) : http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins
* À la fin de chaque match, tu pourras retrouver une correction et analyse ici : http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
* Ainsi que des stats sur ta propre room et le classement sur tout le match ici : http://www.topcoder.com/stat?c=round_overview

Le dernier point est utile pour aller voir le code des autres après un match, pour voir sur quelles entrées tu t'es fait challengé avec succès ou non, et pourquoi, ainsi que de voir sur quelles entrées tu as (éventuellement) échoué lors de la phase "System test".

Et aussi, pour t'éviter de chercher, pour lancer l'applet java de l'arène, tu peux aussi cliquer sur le lien "O(n)" dans le menu en haut à gauche.