036 Cutii

[•fluffy]

Aici puteţi discuta despre problema Cutii.

[•LordAnta]

Cutiile pe care le alegem trebuie a fiu in ordinea data in fisier sau putem sorta sirul dat???

[•SergiuH]

Daca vrei sa torturezi procesorul cu calcule inutile, poti sa nu le sortezi. Eu nu prea vad o solutie in timp fara o sortare.

[•LordAnta]

Mai da-ti va rog un test  la problema ca incepe sa ma enerveze!!!

[•faust]

Imi merge pentru orice test de-al meu. Si totusi 0 puncte.  
Va rog, macar 1-2 teste sa ma verific.

[alexjj]

se pare ca solutia foloseste fie AIB(arbori indexati binari) fie arbori de intervale. prima metoda pentru cazul de 3 dimensiuni foloseste N^3 memorie (3500 * 3500 * 3500 !) si are complexitate logn ^3 adica, pentru 3500 cam N/2 (nimic mai bun decat dinamica clasica);

la arbori de intervale mie greu sa vad o implemenare pentru 3 dimensiuni.

[•domino]

se pare ca solutia foloseste fie AIB(arbori indexati binari) fie arbori de intervale. prima metoda pentru cazul de 3 dimensiuni foloseste N^3 memorie (3500 * 3500 * 3500 !) si are complexitate logn ^3 adica, pentru 3500 cam N/2 (nimic mai bun decat dinamica clasica);

la arbori de intervale mie greu sa vad o implemenare pentru 3 dimensiuni.

Pai sortezi dupa prima dimensiune si ai redus la 2 dimensiuni. N^2 memorie acum ai nevoie, se poate si mai putin cu un hash.

[•Cosmin]

Problema se poate rezolva in O(n) memorie si O(N sqrt(n)) timp daca folositi KD trees.

[alexjj]

doar miam dat cu parerea din infimele mele cunostinte de info ....

[•Cosmin]

Vrem sa te ajutam deci nu are rost sa te oftici.
Ideea la rezolvarea problemei e urmatoarea:
  Sortezi dupa z cutiile, acuma daca ai o cutie de indice i si una de indice j cu i < j atunci cutia i se poate cuibari in cutia j daca x < x[j] si y < y[j]. O rezolvare in O(n^2) ar fi simpla cu programare dinamica, astfel best ar fi lungimea celui mai lung sir de cutii cuibarite in care cutia din exterior e cutia i, dar o asemenea rezolvare e clar ca nu ar intra in timp.  best = max(best[j] | j<i , x[j] < x , y[j] < y) + 1 Pentru a rezolva problema ne gandim la dimensiunile cutiilor x si y ca niste puncte in plan iar la best ca si valoarea punctelor respective si asa am ajuns la o  problema de range search (adica o cautare pe intervale). Deci problema noastra se transforma in folosirea unei structuri de date ce contine puncte si valori pentru puncte, in care putem insera puncte si putem raspunde repede la intrebari de genul care este valoarea maxima a unui punct din structura noastra cu proprietatea ca x_punct < x_dat si y_punct < y_dat. Pentru ca dimensiunile cutiilor sunt in intervalul 1 .. N putem folosi pentru asta structura de AIB bidimensional, cu query time de O(log^2 n). Alte structuri care le-am putea folosi ar fi arbori de intervale, quad trees sau kd trees, toate trei structuri de date folosite in rezolvarea problemelor de ortogonal range search (cautare pe domenii ortogonale).

[•LordAnta]

Tot ce trebuie sa faci la problema e sortare crescatoare dupa care aplici subsir crescator maximal!!! Si am luat 100 asa!!!

[•greco]

Da, numai ca unii nu fac pentru puncte ci pentru a invata ceva util...
Daca stii programarea aia dinamica penala mai bine faci AIB in 2 dimensiuni... e mai util.  

[•Cosmin]

Da am si eu un prieten care a luat 100 asa, dar asta probabil pentru ca testele nu sunt perfecte ... depinde cum ai optimizat programul, e foarte greu sa dai teste la o problema si sa stii sigur ca numai solutia inteligenta poate lua punctaj mare iar bulanelile sa ia sub 50 de puncte si de aia rezolvari ca a ta se mai strecoara cateodata,  daca se mai intampla  sa faci o problema grea fara sa prinzi ideea buna bravo tie, dar daca te bazezi pe genu asta de rezolvari la ONI nu cred ca o ai prea  mult de castigat.

[alexjj]

apreciez mult explicatia. trec la implementare imediat !

[alexjj]

am implementat. deci :

1. sortez dupa x (nare importanta, nu ?);

2. incepand de la cea mai mica valoare tratez pe portiuni avand acelasi x si prima data calculez maximul ce se poate obtine cu fiecare (interogand cu y-1,z-1)  apoi trebuie sa adaug si portiunea aceasta de x la AIB.
si matricea ar trebui initializata cu zero caci pot sa am ceva de genu 1 2 2,   2 1 1 ,  3 3 3  shi maximul ar fi 3, daca se tot aduna la AIB.

si cand interoghez calculez max_obtinut_pentru_portiunea_precedenta + interogare (y-1,z-1). shi eviden nu intra in timp datorita initializarii cu 0 (not even with memset ).

 

[•domino]

am implementat. deci :

1. sortez dupa x (nare importanta, nu ?);

2. incepand de la cea mai mica valoare tratez pe portiuni avand acelasi x si prima data calculez maximul ce se poate obtine cu fiecare (interogand cu y-1,z-1)  apoi trebuie sa adaug si portiunea aceasta de x la AIB.
si matricea ar trebui initializata cu zero caci pot sa am ceva de genu 1 2 2,   2 1 1 ,  3 3 3  shi maximul ar fi 3, daca se tot aduna la AIB.

si cand interoghez calculez max_obtinut_pentru_portiunea_precedenta + interogare (y-1,z-1). shi eviden nu intra in timp datorita initializarii cu 0 (not even with memset ).

 

Pai curatarea nu o faci cu memset ca ar fi N^2 ci faci aceeasi functie de update doar ca de data asta curata... N*lg N deci.

[VladS]

Chiar nu e nevoie de AIB, RMQ etc,; ia 100 si solutia naiva de la subsir daca sortezi mai intii.

[•Cosmin]

Tu ai vazut ce am zis de bulaneli mai sus?

[•cristy]

auziti..ce i-ati facut la algoritmul ala de subsir crescator ca mie imi iese din timp...deci complexitatea este este n^2, nu? cel putin asa e la sirul clasic... (cam numa pe ala il stiu ) si asta face pt 3500 de elemente in 6 secunde si ceva...daramite pt 100 de astfel de determinari    deci..imi explicati si mie pls cum se face, ca la un incepator cum sunt...va rog sa ma scuzati

[VladS]

La subsir e complexitatea e n*(n-1)/2.

[•Sergiu]

Complexitatea la subsir e n*(n-1)/2 dar se poate reduce destul de mult daca se foloseste un vect. auxiliar in care pe pozitia v se memoreaza lungimea maxima a subsirului gasit pana atunci. Si se foloseste acest vect. pt a opri al doilea for  la timp.  Si in felul acesta ies 100 pct fara nici un arbore indexat binar.

[•Cosmin]

Pt subsir crescator de lungime maxima exista algoritmi de complexitate O(n log n), pentru un asemenea algoritm poti sa te uiti in cartea lui Francu "Psihologia concursurilor de programare".

[•cristy]

multumesc sergiule, mi s-a "repezit" mult programul...da tot nu am suta...tot 40...da ms oricum...

[VladS]

Pacat ca nu am cartea.

Cosmin, poti pune undeva pe forum subsir in  n log n sau sa imi trimiti un e-mail. Te rog.

[•Sergiu]

Eu am luat 100 pct. cu aceasta optimizare si cu sortare quicksort, dar daca foloseam sortare liniara iesea si mai rapid.