Tous les concours d'algorithmique et de programmation

Bah mince, tout le monde a des sales bugs!
C'est quoi qui bug pour toi?

Bon calice j'ai du envoyer mon code à la mauvaise adresse. Ca va vite me lourder cette affaire xD

Pour ceux qui ne se sont pas inscrits par pure flemme (pensant que les énoncés seraient affichés publiquement), est-ce vous pourriez dire quel est le problème ? (sans recopier l'énoncé, juste expliquer ce qu'il faut chercher, sinon vous tomberiez sous l'interdiction de recopier l'énoncé)
Merci d'avance !

Ben en gros il faut équilibrer un vecteur.
Sinon je sais pas si c'est interdit ou pas, mais pour ceux qui disent avoir des bugs, vous pouvez poster un exemple d'input qui vous fait planter ?

C'est ce que je réclame depuis tout à l'heure, mais personne de concerné ne semble passer par là...

Il faut faire attention aux « contraintes » aussi :
1

@Equinoxe : https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0B_KLvnMd4WGiOGYzYWJhMjctODczMC00NTI0LTlmY2YtM2QxOTk2NDg2NzYy&hl=en_US&authkey=CLOg2f8E

Paul nous l'aurait dit si c'était interdit. :P
Donc j'en profite pour reprendre l'exemple de Jules :
7
1 2 3 4 5 6 7
qui doit donner 6 et non 9.
De toute façon personne ira en finale en soumettant maintenant, et je ne vois vraiment pas quelles optimisations faire à part lancer l'algo 2 fois pour ne pas stocker l'entrée et utiliser des char.
Donc tous les codes seront sûrement semblables, dur de faire une finale avec une telle sélection, ça sera probablement un tri dans les 30ers qui ont soumis.

pour cette entrée, j'obtient
6
0 : (1, 2, 3, 4, 5, 6, 7)
1 : (2, 2, 3, 4, 5, 6, 6)
2 : (3, 2, 3, 4, 5, 6, 5)
3 : (4, 2, 3, 4, 5, 6, 4)
4 : (4, 3, 3, 4, 5, 5, 4)
5 : (4, 4, 3, 4, 5, 4, 4)
6 : (4, 4, 4, 4, 4, 4, 4)

Pour ceux qui n'ont pas le sujet, on a un tableau d'entiers et on veut que la valeur de toutes les cases soit la même en un minimum d'itération. À chaque itération, chaque case peut transférer une unité à un voisin.

Le problème est beaucoup plus facile que ce à quoi je m'attendais mais ce concours m'aura donné l'occasion d'apprendre le C++ (pour ça les squelettes C++ des exos de prologin m'ont bien aidé).

Et merde... Pourquoi je renvoie 9 moi aussi?

Ah d'accord, j'ai pigé....

xD , finalement , beaucoup ont fait des fautes pour un exo tout con...

@Thomas : comme ça ?
unsigned short sp=0; // Somme partielle sur tab[0:i]
unsigned nb_ite=0; // Nombre d'itération
for(unsigned char i=0; i\<N-1; ++i){
sp+=tab[i];
nb_ite = std::max\<unsigned short>(nb_ite, std::abs(sp - expected*(i+1)));
}

Moi l'input qui me fait fail, c'est
0 3 0

Je le resoud en un tour, alors que normalement il en faux 2 (une case peux pas donner a gauche et a droite >le truc trop rageant

Sinon, moi je resoud votre probleme en 6 tour sans soucis.

Moi c'est bon pour le 0 3 0 :p

« Je le resoud en un tour, alors que normalement il en faux 2 (une case peux pas donner a gauche et a droite >→ Ah oui bien vu. Bon ben je n'aurai pas d'iPad2 alors ... :p
Dommage, mon code était si joli ... =) (et surtout on avait une formule simple pour calculer le nombre max d'itérations en O(n)).

EDIT : Ouai non finalement ça en prend pas long pour recalculer facilement le nombre d'itération à utiliser. Par contre le code qui fait l'équilibrage en est devenu bin moche ... :s

PS : Par contre les gens désolé de vous décevoir, mais ça m'étonnerait qu'utiliser des char à la place des int n'accélère en quoi ce que soit votre programme. Tout du moins avec de si faibles contraintes s'il y a des différences elles seront tellement insignifiante que ça ne vous changera rien.

Je me demande si ta formule simple n'est pas la même bidon que la mienne. :P
Oui, de toute façon on ne sera pas évalué sur le temps puisqu'il reste négligeable dans tous les cas, je parlais de la mémoire bien sûr.

Perso je résous l'entrée la plus grosse en 12 ms avec 4n+O(1) octets de mémoire donc le multithreading sans prendre en compte le nombre de cœurs, ce n'est pas très utile. :D

4n de mémoire ? Perso je n'utilise que deux vecteurs de taille n. Je pourrai réduire à 1 seul, mais ça complexifierait pas mal le code. Et même sur un vecteur de taille 64, je reste à 9ms de temps d'exécution. Whaou tu parles d'une amélioration par rapport à 12ms ... xD

Je pense pas qu'utiliser 2 fois moins de mémoire soit un critère pertinent de performance du programme. Tant que ça reste du O(n) avec une constante raisonnable (

Et j'utilise moins de mémoire que TLN puisque je n'utilise pas de vector, un bon pour cent d'économisé. :)
Enfin, mon code soumis est faux.

TLN > Il se peut aussi que ce soit simplement un seul vecteur de int, sur une machine 32 bits. =°

Thomas > Faux, un vector ce n'est pas un pourcent de plus, c'est O(1) de plus : dans ma version de la STL >>

####snip####
[ekinox@leortable \~]\$ cat tmp.cpp
#include

int main(int, char**) {
std::vector vec;
vec.push_back(1);
vec.push_back(2);
return 0;
}
[ekinox@leortable \~]\$ g++ -g tmp.cpp
[ekinox@leortable \~]\$ gdb a.out
GNU gdb (GDB) 7.2
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-unknown-linux-gnu".
For bug reporting instructions, please see:
...
Reading symbols from /home/ekinox/a.out...done.
(gdb) b 7
Breakpoint 1 at 0x400914: file tmp.cpp, line 7.
(gdb) r
Starting program: /home/ekinox/a.out

Breakpoint 1, main () at tmp.cpp:7
7 return 0;
(gdb) p vec
\$1 = { >> = {_M_impl = { > = { \<__gnu_cxx::new_allocator> > = { }, }, _M_start = 0x603030,
_M_finish = 0x603038, _M_end_of_storage = 0x603038}}, }
(gdb)
####snap####
Donc mon vector prend simplement, par rapport à un tableau normal :
- _M_impl ; qui n'est qu'un objet interne, std::vector est donc un proxy >> un compilateur avec -O2 l'optimise
- _M_start ; le début du stockage en interne : c'est le pointeur qu'on stocke directement lorsqu'on a un tableau
- _M_finish ; l'octet après le dernier alloué
- _M_end_of_storage ; l'octet après le dernier utilisé : il est stocké de la même façon qu'on stocke la taille du vector ; il s'obtient par _M_start + taille_tableau
Au final, seuls 4 octets de plus sont pris par un vector : _M_end_of_storage.
Et on pourrait considérer que l'écart entre _M_end_of_storage et _M_finish est perdu, mais une utilisation judicieuse de reserve / resize permet d'éviter ça.
Donc on peut utiliser les vector en :
- Gagnant de la place par rapport à un tableau de taille statique (sauf dans le cas où la taille demandée est celle maximum)
- Gagnant le transport de la variable taille et l'oubli probable de delete, et enfin la RAII-itude par rapport à un tableau à coups de new / delete

Bref, un vector bien utilisé, c'est que du bénéfice ! =D

Oui enfin, il faut patcher le code de la fonction reserve, sinon tu ne peux pas diminuer sa taille :/