Imprimă pagina - Zebughil .. nice one

Titlul: Zebughil .. nice one
Scris de: Bunau Florin din Noiembrie 19, 2005, 14:54:09

Nu stiu daca sunt reguli impotriva topicurilor de genu asta:P da se pare ca mai sunt.
Prob o fo faina :P ..si din cate am observat si comuna la grupele X, XI-XII
Am ramas dezamagit ca nu mi-o iesit :-({|= si surprins de ce nu...
Multzi au patzit asa...

Daca atzi facuto cum atzi facuto? si de ce nu e bine asa: (prea mult pana se posteaza articol)

de ex. eu am considerat asa: a = nr minim de camioane spre a transporta greutatea i. (obtinuta din insumarea greutatii pietrelor selectate)

cu o dinamica de genu:

Cod:


  for (int i = 1; i <= n; ++i)
    {
        for (int j = G*n - z[i]; j; --j)
        {
            if (a[j])
            {
                if (z[i] + j <= a[j]*G)
                    k = 0;
                else k = 1;
                if (a[j+z[i]] > a[j] + k || a[j+z[i]] == 0)
                    a[j+z[i]] = a[j] + k;
            }       
        }    
        if (!a[z[i]]) a[z[i]] = 1;
    }

si rasounsul era in a unjde s suma greutatii pietrelor... si G cat poate duce un camion

hmm.. de ce nu e bine...? daca puteti da ceva idei despre cum se rezolva sau de ce nu e bine asa i would aprieciate it :mrgreen:

si un test consnsistent daca se poate..pls....macar primul...sau oricare...mor daca nu aflu cum se rezolva... ](*,) ](*,) ](*,)

Titlul: Zebughil .. nice one
Scris de: andreit1 din Noiembrie 19, 2005, 15:48:39

Dinamica se foloseste doar dupa ce ai demonstrat( sau e evident) ca este si buna. Ceea ce faci tu acolo mi se pare ceva cam greedy mai degraba... Problema se putea rezolva de max chiar si cu backtracking, in locul unei dinamici nesigure...
Un test( oarecare) care poate te va convinge ca nu e bun programu tau:
17 100
12 16 14 18 17 19 10 18 16 14 9 6 3 4 2 10 1
17 9
8 9 9 9 5 9 9 9 1 3 3 3 4 9 8 9 1
17 10
10 8 5 4 4 3 8 5 7 2 5 4 2 7 4 3 2
Mie imi da 2,12,9.

Titlul: Zebughil .. nice one
Scris de: Marius Stroe din Noiembrie 19, 2005, 16:53:43

Algoritmul meu suna cam asa: am obtinut Greedy + cautare binara (sirul este sortat descrescator) un numar de submultimi, apoi am incercat cu un BKT sa imbunatatesc! 8 teste au mers, inclusiv cel al lui andreit1. De ce nu am luat si primele doua teste nu stiu... :(

Titlul: Zebughil .. nice one
Scris de: andreit1 din Noiembrie 19, 2005, 17:56:23

Solutia greedy nu iti da intotdeauna solutia optima. Si inca o chestia... un back bine facut iti da intotdeauna rezultatul bun( daca il lasi sa mearga pana la capat). Uite-te si peste solutiile oficiale daca vrei niste solutii mai destepte.

Titlul: Zebughil .. nice one
Scris de: Bunau Florin din Noiembrie 19, 2005, 18:35:27

Da tot 2, 12 9 imi da si mie...
am cerut un test din cele oficiale daca se poate...
si am ramas surprins ca ai spus ca e greedy :lol: :eyebrow:

wow... no offence...da e dinamica 100% :lol: :lol: :lol: :lol: :shock:
deci am putea primi un test?

Titlul: Zebughil .. nice one
Scris de: andreit1 din Noiembrie 19, 2005, 18:43:02

E regula de nu stiu cand... NU SE DAU TESTELE OFICIALE!
Cand despre dinamica ta... Ce dinamica e aia cand nu obtii rezultatul bun intotdeauna? Programarea dinamica presupune si corectitudine... Altfel parerea mea e ca tot greedy e.

Titlul: Zebughil .. nice one
Scris de: Bunau Florin din Noiembrie 19, 2005, 18:57:02

o well daca nu se dau teste ... sorry...topic closed din partea mea

Titlul: Zebughil .. nice one
Scris de: cristi8 din Noiembrie 19, 2005, 22:21:02

tot vorbiti de back, ca se lua maxim cu back.. cum faceati back-ul, ca eu cand m-am gandit nu mi-a venit nici o idee.

Titlul: Zebughil .. nice one
Scris de: u-92 din Noiembrie 19, 2005, 22:33:40

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.

Titlul: Zebughil .. nice one
Scris de: cristi8 din Noiembrie 19, 2005, 22:38:28

:idea: aaaa, back() d-ala ca-n manualul de clasa 10a..

..era mai misto cu permutari cum e prezentat in articol :P

Titlul: Zebughil .. nice one
Scris de: andreit1 din Noiembrie 19, 2005, 22:59:54

Doar ca algoritmul cu permutari este O(N!) pur... Ca sa nu mai cauti binar puteai sa faci asa... Considerai la inceput un singur camion, in care puneai greutatea 1. Si dupa ai la fiecare pas( pentru fiecare greutate) incercai sa il pui in unul din camionele anterioare sau singur intr-un camion noi. Cam asta e algoritmul... cu cateva chestii in plus scadea foarte mult sunt N!.

Titlul: Zebughil .. nice one
Scris de: Lucescu Andrei Bogdan din Noiembrie 21, 2005, 10:54:22

Am facut si eu problema cu programare dimamica si pe moment solutia mi s-a parut buna dar cred ca am uitat ceva si am luat numa 10 p am sa ma mai uit peste problema si am sa vad daca pot sa o fac sa mearga
practic ce faceam :
luam vectorul cu greutait si incercam sa aflu pe rand la ficare bucata cu care din cele precedente dadea o suma cat mai mare fara sa treaca peste limita maxima si blocu primea valoarea sumei , si retineam intr-un vector predecesorul lui
pe urma din vectoru blocurilor cautam cea mai buna solutie si ii marcam elementele ca vizitate , faceam asta pana erau transportate toate blocurile
solutia are dificultate n*n dar la unele teste imi iese cu un tir in plus (la majoritatea nu da din trei unu nu merge) cre ca am uitat eu o posibilitate , voi credeti ca am vreo sansa sa o fac 100%??

Titlul: Zebughil .. nice one
Scris de: ditzone din Noiembrie 21, 2005, 11:00:40

Nu ai sanse sa obtii punctaj maxim cu o astfel de solutie "greedy"
Ia de exemplu testul

Cod:


6 100
33 33 33 60 60 60

tu vei obtine raspunsul 4 deoarece initial vei baga 33 33 33 intrun camion si vei mai folosi inca 3 pentru a transporta si pietrele de 60. Raspunsul optim este 3 deoarece se transporta cate un 33 cu un 60. (daca am inteles eu bine ce faceai....)

Titlul: Zebughil .. nice one
Scris de: VladS din Noiembrie 21, 2005, 17:53:58

Problema e NP-completa asa ca nu exista algoritmi polinomiali. Deci dinamicile alea care de fapt sunt greedy nu sunt corecte.

Titlul: Zebughil .. nice one
Scris de: Mihaela Verman din Noiembrie 21, 2005, 18:45:10

Eu zic asa.
1. sortam vectorul descrescator
2. pornim de la 1 pana la n si incercam sa "cumplam" elementul i cu multimea cu suma maxima (ne uitam la tot ce se afla inaintea lui i) de pana acum.
That's it!

Pentru ca nu am fost tocmai explicita.. ar veni ceva de genul:

Cod:



{initializari etc etc}
for i:=1 to n do
 multime[i]:=i;


for i:=1 to n do
begin
  max:=0;
  pozmax:=0;
  for j:=1 to i-1 do
    if (max<suma[j]) and (suma[j]+v[i]<=volCamion) then
       begin
          max:=suma[j];
          pozmax:=j;
       end;
end;
  
{si-acuma, daca e cazul, facem uniunea de multimi. scuzati-ma dar am cam multa treaba in seara asta si recunosc, mi-e si cam lene sa scriu}

[/code]

Titlul: Zebughil .. nice one
Scris de: cristi8 din Noiembrie 21, 2005, 21:14:31

tu n-auzi ca nu se poate face corect polinomial ?? ce nu intelegi ?! :P

Titlul: Zebughil .. nice one
Scris de: Adrian Vladu din Noiembrie 22, 2005, 11:37:58

ati putea incerca sa va uitati pe solutia oficiala 8)
http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

Titlul: Zebughil .. nice one
Scris de: Andrei din Noiembrie 22, 2005, 18:38:07

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 ca sa mearga si mai repede: Avem asa, daca numarul de camioane curente e mai mare decat best (nr cel mai mic de camioane care a fost determinat pana acum ca solutie, nu neaparat cea mai buna), atunci exit;
initinial best este egal cu n.

Titlul: Zebughil .. nice one
Scris de: Rus Cristian din Noiembrie 22, 2005, 19:57:43

mai fratilor...voi ziceti ca nu se poate cu greedy...da eu am incercat totusi...sunt greu de cap...am incercat asa...sortez greutatile descrescator...pun primu bloc in primu camion...si apoi...verific fiecare greutate daca nu poate fi pusa in vreunul din camioanele dinainte, in caz afirmativ, pun blocul in primul camion in care incape..si daca nu incape in nici unul...o pun in alt camion...asta ar fi rezolvarea...de ce nu e buna?...pls...dati si mie un exemplu...ca tot nu ma prind...iau numa 40 de pct...restu...WA...si imi intra in 0.02 secunde...cel mai mult...mie mi se pare buna rezolvarea...

Titlul: Zebughil .. nice one
Scris de: Tiberiu-Lucian Florea din Noiembrie 22, 2005, 21:15:41

Daca vi s-a spus un lucru, de ce insistati la infinit ? Problema asta e NP-completa, si NU se poate rezolva cu greedy. E clar lucrul asta.

Nu te astepta sa-ti dam contraexemple la solutiile tale, pentru ca cu exemplele poti realiza un singur lucru: sa spui ca o solutie e proasta daca nu le trece. NU si invers. Ok ?

Titlul: Zebughil .. nice one
Scris de: Andrei din Noiembrie 22, 2005, 21:24:39

cristy si greco:
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, :P). 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.

Titlul: Zebughil .. nice one
Scris de: Tiberiu-Lucian Florea din Noiembrie 22, 2005, 21:27:30

Daca ai luat maxim nu inseamna ca ai rezolvat-o. Inseamna ca ai facut o rezolvare pe care au mers testele.

Titlul: Zebughil .. nice one
Scris de: ditzone din Noiembrie 22, 2005, 21:47:23

Freeyourmind... ceea ce ai facut tu incearca toate posibilitatile... este backtracking.. Ceea ce a facut cristy este greedy pentru ca el cand plaseaza o piatra intr-un camion nu mai incearca si in altul.. si nu va obtine mereu solutia optima..
Incercati sa vedeti si solutiile de la: http://info.devnet.ro/articole.php?page=art&art=74&artpage=5

Titlul: Zebughil .. nice one
Scris de: Andrei din Noiembrie 22, 2005, 21:51:53

ok, thx de observatii. eu intr-adevar credeam ca cristi incearca in toate camioanele anterioare. :thumbup:
si observatia lui greco e binevenita. :)

Titlul: Zebughil .. nice one
Scris de: Catalin Tiseanu din Noiembrie 23, 2005, 11:28:13

Pai asta denota teste proaste spre f. proaste, daca se poate lua maxim cu rezolvari din astea dubioase. Erau 3 subteste pe test, era destul de usor sa pici rezolvari din astea. Macar pe un test, sa stie lumea ca solutia lor nu e corecta :lol:

Incep sa inteleg propunerea ginfo ca sa existe teste submitate de concurenti ...

Titlul: Zebughil .. nice one
Scris de: ditzone din 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.

Titlul: Zebughil .. nice one
Scris de: Catalin Tiseanu din Noiembrie 23, 2005, 11:50:34

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

Citat

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

Si el ia 100

3)

Citat

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

Titlul: Zebughil .. nice one
Scris de: u-92 din 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

Titlul: Zebughil .. nice one
Scris de: ditzone din 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..

Titlul: Zebughil .. nice one
Scris de: Andrei Grigorean din Noiembrie 23, 2005, 15:41:35

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => preONI 2006 => Subiect creat de: Bunau Florin din Noiembrie 19, 2005, 14:54:09