197 Semne

[•domino]

Aici puteţi discuta despre problema Semne.

[•wefgef]

S nu are limita?

[•filipb]

Suma tuturor numerelor a

[•pauldb]

Deci S poate fi si negativ, nu?

[•filipb]

DA

[•varuvasi]

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

[•pauldb]

Random

[•varuvasi]

ai putea oferi mai multe detalii? 

[•flo_demon]

)  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 incredible

[•wefgef]

Faci un random destept. Asta e si solutia oficiala .

[•flo_demon]

Done  Thx for tips ppl. Altfel ramaneam la 75

[•CezarMocan]

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

[•filipb]

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.

[•Marius]

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

[•CezarMocan]

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

[•thestick]

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

[•stef2n]

Problema se poate rezolva si fara random cu ajutorul unui hash 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)

[•andreitheo87]

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...

[•peanutz]

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

[•CezarMocan]

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

[•stef2n]

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...

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.

[•peanutz]

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..

[•cos_min]

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

[•Dastas]

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

[•peanutz]

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...