infoarena

Aici puteţi discuta despre problema Semne (http://infoarena.ro/problema/semne).

S nu are limita?

Suma tuturor numerelor a

Deci S poate fi si negativ, nu?

DA

am obtinut 50 p dar n-am nici o idee pentru 100 p.  #-o hint...?  :?

Random :)

ai putea oferi mai multe detalii?  :-k

:))  \:D/ This is so much fun... am scris un algoritm aproape random :))=)) am reusit sa iau maxim 20 pcte...  You were joking asai? :)) oricum.. mai trimit inca de cel putin 10 ori...too much fun, e ca si cum ai primi cadouri de craciun, nu sti ce iti poate aduce urmatoru submit.

[later edit] OMG chiar nu glumeai, m-am mai jucat cu sursa, si am luat 80pcte :o incredible :P

Faci un random destept. Asta e si solutia oficiala :).

Done  =D> Thx for tips ppl. Altfel ramaneam la 75

Imi ziceti si mie plz cam ce inseamna "random destept"?? Ca nu prea am mai rezolvat probleme de genu asta. :?

O rezolvare corecta intotdeauna din punct de vedere matematic are complexitatea mult prea mare. Pentru ca programul tau sa se incadreze in timp incearca un algoritm randomizat ( care sa se bazeze pe calcule aleatoare ). De exemplu ai putea genera aleator numere pana gasesti solutia. Bineinteles nici aceasta nu e o solutie prea desteapta. Poti incerca alti algoritmi, tot bazati la un anumit punct pe generarea unor numere aleatoare.

Cate sanse ai sa iei de doua ori consecutiv 100 p cu un astfel de algoritm ? :)

Ok, mersi.
Marius Stroe: Pai daca faci un random cu adevarat destept iei 100 mereu.  :thumbup:

daca iti pastrezi seed-ul de random , ai sanse.

Problema se poate rezolva si fara random cu ajutorul unui hash :P Ca sa vedeti ca exista si anti-ciucuieli. (Anti-ciucuiala = abordare corecta din punct de vedere matematic a unei probleme si care ia punctaj maxim, in ciuda faptului ca problema a fost propusa doar pentru ciucuieli)

Ai demonstrat tu ca ai destula memorie pentru solutia ta indiferent de test? Sau te-ai bazat pe faptul ca testele sunt generate aleator si pentru anumite grupe de numere ai o gramada de submultimi cu aceeasi suma? Caz in care tot ciucuiala se cam numeste programul...

E ceva recursiv in toata chestia cu random? Nu puteti da mai multe detalii, va rog..

Nu, nu e nimic recursiv. Doar muti numere dintr-o multime in alta ca nebunu :)

Intr-adevar, calcul de memorie nu mi-am facut. Si cred ca e destul de greu. Dar m-am bazat pe niste observatii probabilistice. Nu este o intamplare ca exista foarte multe submultimi cu aceeasi suma. Acest lucru nu e din cauza generarii aleatoare a testelor.
Sa consideram toate posibilitatile de a lua 2 numere din cele N pentru a le fixa cate un semn. Numarul de posibilitati pentru a face acest lucru este 2*N*(N-1), deoarece putem lua 2 elemente X si Y in N*(N-1)/2 moduri, avand pentru fiecare mod unul din urmatoarele cazuri:
1. +X +Y
2. +X -Y
3. -X +Y
4. -X -Y
Intrucat fiecare element X satisface conditia 1<=X<=5.000.000, suma algebrica a 2 astfel de elemente va satisface conditia -10.000.000<=S<=10.000.000. Deci, cele 2*N*(N-1) sume se vor "inghesui" pe 20.000.000 de pozitii. In cazul unui test maxim (N=50.000), surplusul (numarul de sume algebrice care se repeta) este de cel putin 4.979.900.000. Asadar, doar considerand sumele formate din 2 numere, numarul de repetii este foarte mare.
Desigur, e posibil sa existe teste extreme si pe care solutia mea sa le pice din cauza memoriei. Ce am vrut eu sa subliniez este ca rezolvarea mea este corecta matematic, nefolosind random. Intr-adevar, exista si rezolvari corecte care folosesc generari de numere aleatoare (de exemplu quicksort cu pivot aleator), numai ca din discutia de mai sus am inteles ca "randomul destept" nu este una din acestea. :peacefingers:

Iau 70 din cauza faptului ca folosesc rand() % n sau nu am algoritm bun? Exista ceva mai rapid decat rand() % n? random(n) am tot incercat si nu reusesc sa-l fac sa mearga.. Am rulat exemplul din help si da eroare..

Poate cineva sa explice mai pe larg o idee de implementare folosind un random 'destept' ?  #-o

^ subscriu.. nu ma prind nicicum.. dati macar pe privat o idee putin mai detaliata, va rog...

Cred ca e bun algoritmul meu, rand() % n mi se pare a fi incet, iau 90 totusi... Lucrezi cu un vector caractertistic: nr[ i ] = 1, daca i apartine multimii cu +, sau 0, in caz contrar... Mai tii si o suma care reprezinta configuratia curenta.. si tu tot generezi cate un numar random si il treci in alta multime pe cel generat daca e optim... Am facut si fara conditie, pur si simplu il schimbam pe cel generat.. si luam 70...

Poate ar trebui sa faci asa incat sa fii sigur ca de fiecare data alegi un numar cu semnul pe care ti-l doresti.

Intre timp nu exista ceva mai rapid decat rand() % n, simt ca sunt aproape :P

Ai putea sa-mi explici putin ce intelegi prin "daca e optim"? Eu iau 65 de puncte cu o solutie care doar genereaza si skimba semnul...

Imi explica cineva cum  fac random ca nu am mai facut niciodata si nu shtiu cum se face  :'(

ms, acuma am inteles si eu

Pai random inseamna sa alegi semnul pt un anumit numar, in mod aleatoriu. Schimbi semne, pana cand dai de raspunsul corect. Daca l`ai gasit, atunci te opresti si afisezi rezultatul. Poti folosi functia rand()%n . Succes!  :)

Un pic mai pe larg:

Pentru a genera numere aleatorii, folosesti functia rand() din headerul <cstdlib>

Pentru a genera numere random diferite la fiecare executie a programului, poti sa incluzi headerul <ctime> si inainte de a apela functia rand(), sa apelezi srand(time(0)) (o singura data in tot programul).

Pentru a genera numere random intr-un anumit interval [0, n), folosesti rand() % n.

Succes!

Iau 5 puncte (http://infoarena.ro/job_detail/333642?action=view-source) pe ea pentru ca imi da numai primul test... A little hint please?

P.S : Enuntul e criminal. Imi place mult problema. :peacefingers:

Un mic hint: se poate reduce problema la un fel de "Subset sum problem(http://en.wikipedia.org/wiki/Subset_sum_problem (http://en.wikipedia.org/wiki/Subset_sum_problem))".

Are cineva o sursa care intra in timp pe testul

Nu este sursa mea dar intra in timp pe acest test: http://www.infoarena.ro/job_detail/53475?action=view-source