Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: Zebughil .. nice one  (Citit de 6657 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
ditzone
Vizitator
« Răspunde #25 : Noiembrie 23, 2005, 11:38:37 »

Rezolvarile greedy nu au obtinut mai mult de 30-40 de puncte... Tocmai din cauza asta s-au dat 3 subteste pentru a pica diferite greedyuri.
Ceea ce se discuta aici era faptul ca multi nu inteleg de ce rezolvarile lor greedy nu sunt bune.
Memorat
Zeus
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #26 : Noiembrie 23, 2005, 11:50:34 »

Asa zici tu ? Eh, tre' sa te contrazic :p

Citat
Rezolvarile greedy nu au obtinut mai mult de 30-40 de puncte... Tocmai din cauza asta s-au dat 3 subteste pentru a pica diferite greedyuri.
Ceea ce se discuta aici era faptul ca multi nu inteleg de ce rezolvarile lor greedy nu sunt bune.


Eu nu m-am referit numai la rezolvari greedy, ci si la solutii back, solutii cu verificare de permutari etc. Am 3 citate de solutii incorecte dpdv algoritmic, sau dpdv al complexitatii din acest thread care au luat mai mult de 30-40 puncte.

1)
Citat
eu am facut problema ca si cristi, plus cu conditia sa verificam sa nu folosim mai mult de best camioane. unde best reprezinta numarul cel mai bun de camioane gasit. Un bloc nou incercam sa il punem in fiecare din camioanele dinainte, sau intr-unul nou. Se cerceteaza toate cazurile deci nu ma prind de ce e asta greedy. Si inca o observatie (i might be wrong, Razz). Se poate de sortat initial in ordine crescatoare!
Dupa parerea mea... daca sortezi crescator, camioanele se umplu mai greu deci primul best are sanse mari sa fie destul de mic, si mai apoi nu va mai trebui sa exploram prea in adancime! Am luat maximul asa, de ce ziceti ca nu merge?
p.s. initial best este n, logic.


El zice ca a luat 'maxim asa', eu il cred :lol:, deci avem un contraexemplu deja

2)
Citat
Pai, la zebughil mergea intr-adevar un fel de back... cu adancimea maxima n.
De fapt e generare de permutari, numai ca are mult mai putin de n!
Adica punem primul element in multimea 1, al doilea in 1 si 2, al treilea in 1,2,3 s.a.m.d. Dar ca sa nu ne ajungem la n! adica sa facem verificarilela dupa ce am grupat toate n blocuri in camioane, vedem la momentul dat daca putem adauga sau nu. Asta reduce simtitor timpul.
Adica pastram intr-o matrice greutatea curenta a unui camion. La inserarea unui bloc vedem, daca acesta poate fi inserat sau nu in camionul i.
am facut asa si am luat 100.


Si el ia 100

3)
Citat
un back de 90 de puncte e asta:
caut binar nr. minim de camioane, pt un astfel de numar am sum = suma
greutatilor din camionul i.
Pe rand, incerc sa plasez pietrele in camioanele in care pot, adik z[k] + sum <= G (k e indicele pietrei curente). Cand am ajuns la pozitia N si am reusit sa o plasez si pe asta e clar ca am obtinut solutie. Daca nu obtin solutie, caut un numar mai mare de camioane.


El a luat 90, tot mai mult ca 30-40.

O sugestie ar fi fost sa ridicati limita pt. N. Solutia mea este (2^N) * N, si cum sunt operatii pe biti, putea intra lejer cu N = 20 in 0.4 secunde pe subtest. Asta ar fi daunat mult backurilor.

S-ar putea sa gresesc eu, dar mie mi se pare dubios sa iei mai mult de 50-60 puncte cu un back .. Rolling Eyes
Memorat

There is only power and those too weak to seek it.
u-92
Vizitator
« Răspunde #27 : Noiembrie 23, 2005, 12:12:04 »

inca ceva.. nu am luat 90 in concurs cu back`ul ala fiindca mi-a fost frica sa-l trimit, am luat 30 cu un greedy
Memorat
ditzone
Vizitator
« Răspunde #28 : Noiembrie 23, 2005, 12:19:14 »

Eu am zis doar ca nu s-au dat mai mult de 30-40 de puncte pe solutiile greedy.. Concurentii respectivi au facut back..
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #29 : Noiembrie 23, 2005, 15:41:35 »

s-a luat si 60 cu greedy. nu eu, dar cunosc.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines