infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:36:45


Titlul: 036 Cutii
Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:36:45
Aici puteţi discuta despre problema Cutii (http://infoarena.ro/problema/cutii).

Titlul: 036 Cutii
Scris de: Anton Alexandru din Noiembrie 17, 2004, 20:31:30
Cutiile pe care le alegem trebuie a fiu in ordinea data in fisier sau putem sorta sirul dat??? :?:

Titlul: 036 Cutii
Scris de: Hlihor Sergiu din Noiembrie 18, 2004, 00:05:55
Daca vrei sa torturezi procesorul cu calcule inutile, poti sa nu le sortezi. Eu nu prea vad o solutie in timp fara o sortare.

Titlul: 036 Cutii
Scris de: Anton Alexandru din Ianuarie 13, 2005, 13:10:27
Mai da-ti va rog un test  la problema ca incepe sa ma enerveze!!!

Titlul: Teste
Scris de: Alexandru Andrei din Februarie 25, 2005, 02:46:37
Imi merge pentru orice test de-al meu. Si totusi 0 puncte.  :(
Va rog, macar 1-2 teste sa ma verific.

Titlul: 036 Cutii
Scris de: alexjj din Februarie 25, 2005, 11:46:28
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.

Titlul: 036 Cutii
Scris de: Mircea Pasoi din Februarie 25, 2005, 13:06:33
Citat din mesajul lui: 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.


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.

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Februarie 25, 2005, 17:03:35
Problema se poate rezolva in O(n) memorie si O(N sqrt(n)) timp daca folositi KD trees.

Titlul: 036 Cutii
Scris de: alexjj din Februarie 25, 2005, 18:05:29
doar miam dat cu parerea din infimele mele cunostinte de info ....

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Februarie 25, 2005, 19:12:47
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).

Titlul: 036 Cutii
Scris de: Anton Alexandru din Februarie 25, 2005, 20:12:44
Tot ce trebuie sa faci la problema e sortare crescatoare dupa care aplici subsir crescator maximal!!! Si am luat 100 asa!!!

Titlul: 036 Cutii
Scris de: Tiberiu-Lucian Florea din Februarie 25, 2005, 20:17:19
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.  :shock:

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Februarie 25, 2005, 21:45:15
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.

Titlul: 036 Cutii
Scris de: alexjj din Februarie 27, 2005, 18:15:16
apreciez mult explicatia. trec la implementare imediat !

Titlul: 036 Cutii
Scris de: alexjj din Februarie 27, 2005, 22:14:52
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 :-k ).

 ](*,)

Titlul: 036 Cutii
Scris de: Mircea Pasoi din Februarie 27, 2005, 22:50:15
Citat din mesajul lui: 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 :-k ).

 ](*,)


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.

Titlul: 036 Cutii
Scris de: VladS din Februarie 27, 2005, 23:13:38
Chiar nu e nevoie de AIB, RMQ etc,; ia 100 si solutia naiva de la subsir daca sortezi mai intii.

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Februarie 27, 2005, 23:49:50
Tu ai vazut ce am zis de bulaneli mai sus?

Titlul: 036 Cutii
Scris de: Rus Cristian din Martie 23, 2005, 15:33:29
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  :roll:  deci..imi explicati si mie pls cum se face, ca la un incepator cum sunt...va rog sa ma scuzati :mrgreen:

Titlul: 036 Cutii
Scris de: VladS din Martie 23, 2005, 17:14:34
La subsir e complexitatea e n*(n-1)/2.

Titlul: 036 Cutii
Scris de: Sergiu din Martie 23, 2005, 17:35:46
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.

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Martie 23, 2005, 18:46:01
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".

Titlul: 036 Cutii
Scris de: Rus Cristian din Martie 23, 2005, 19:17:26
multumesc sergiule, mi s-a "repezit" mult programul...da tot nu am suta...tot 40...da ms oricum...

Titlul: 036 Cutii
Scris de: VladS din Martie 23, 2005, 19:27:47
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.

Titlul: 036 Cutii
Scris de: Sergiu din Martie 23, 2005, 20:16:04
Eu am luat 100 pct. cu aceasta optimizare si cu sortare quicksort, dar daca foloseam sortare liniara iesea si mai rapid.

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Martie 24, 2005, 13:33:24
TYTUS: Nu am cartea la mine si nici codul la o problema care am rezolvat-o in O(n log n) nu l-am mai gasit, oricum dupa ONI probabil va aparea un articol pe tema asta pe info.devnet. Pana atunci poti sa citesti ideea din linkul asta: http://www.answers.com/main/ntquery;jsessionid=fa1iqujmfas8?method=4&dsid=2222&dekey=Patience+sorting&gwp=8&curtab=2222_1&sbid=lc02b

Titlul: 036 Cutii
Scris de: raxvan oprea din Mai 19, 2005, 20:39:07
Am o rezolvare care foloseste clase de obiecte si nu pot sa o valorific deoarece evaluatorul nu suporta. Ce sa fac k sa imi pastrez rezolvarea si sa fac sa mearga.
In acesta clasa redefinesc operatorii tocmai cauza erori.

Titlul: 036 Cutii
Scris de: Dima Alex din Mai 19, 2005, 22:00:10
evaluatorul suporta clase. ai grija cand trimiti rezolvarea sa pui 'c++' ... daca nu asta e problema, inseamna ca nu ai scris cod bun.

Titlul: 036 Cutii
Scris de: vladut.forum din August 30, 2005, 18:11:24
auleu, nustiu ce v-ati aprins asa, mie mi se pare logica faza cu Subsir maximal,
1. Se cere numarul maxim de cutii ce pot fi selectate din cele N astfel incat ele sa poata fi “cuibarite�
2. Se stie ca o cutie se poate pune in alta doar daca toate dimensiunile ei sunt strict mai mici cele ale cutiei in care va fi bagata.
cei drept daca dimensiunile nu tb sa fie strict mai mici, atunci se complica subsirul nostru, tb sortat mai "adanc"...
zice sa alegi niste cutii astfel incat sa le bagi una in alta, ceea ce te duce la sortare dupa o dimensine, si normal zice ca dimensiunile tb sa fie strict mai mici, deci te duce fix la subsir descrescator maximal...
nustiu daca am explicat corect, da mie in minte mi se pare cotrecta solutia, si zic ca trece peste toate testele

Titlul: 036 Cutii
Scris de: Oltean Dorin din Septembrie 01, 2005, 09:22:13
da bineinteles ca este subsir maximal si eu asa am rezolvato si am luat 100 p

Titlul: 036 Cutii
Scris de: Cosmin Negruseri din Septembrie 01, 2005, 09:45:19
vladut cred ca nu ai inteles ce se discuta mai sus ....

Titlul: Cutiute
Scris de: nivan din Octombrie 11, 2005, 20:10:25
Uite de ce nu merge asta: Fac problema pe principiul subsirului crescator maximal, doar ca consider un numar mai mare ca altul dak poa sa intre o cutie in alta. Nu merge nu stiu de ce. Mie pe comp imi da bine.

Uite si sursa dak te ajuta:
Cod:

#include <stdio.h>

long int gasit,i,nicu,j,n,m,l[3502],L[3502],h[3502],v[3502],x;

void quick(long int li, long int ls)
{
 long int i,j,x,y;
 i=li; j=ls; x=v[(li+ls)/2];
 while (i<=j)
      {
       while (v[i]>x) i++;
       while (v[j]<x) j--;
       if (i<=j)
	 {
	  y=v[i]; v[i]=v[j]; v[j]=y;
	  y=l[i]; l[i]=l[j]; l[j]=y;
	  y=L[i]; L[i]=L[j]; L[j]=y;
	  y=h[i]; h[i]=h[j]; h[j]=y;
	  i++; j--;
	 }
      }
 if (i<ls) quick(i,ls);
 if (j>li) quick(li,j);
}

int intra(long int i, long int j)
{
 long int gasit=1;
 if (l[i]>l[j] && L[i]>L[j] && h[i]>h[j])
   gasit=0;
 return gasit;
}

int main()
{
 FILE *g=fopen("cutii.out","w");
 FILE *f=fopen("cutii.in","r");
 fscanf(f,"%ld %ld",&n,&m);
 for (nicu=1;nicu<=m;nicu++)
    {
 for (i=1;i<=n;i++)
    fscanf(f,"%ld %ld %ld",&l[i],&L[i],&h[i]);

 for (i=1;i<=n;i++)
    v[i]=l[i]*L[i]*h[i];

 quick(1,n);

 for (i=1;i<=n+2;i++)
    v[i]=0;
 v[n]=1;
 long int max=0;
 for (i=n-1;i>=1;i--)
    {
     max=0;
     for (j=i+1;j<=n;j++)
	if (v[j]>=max && intra(i,j)==0)
	  {
	   max=v[j];
	   break;
	  }
     v[i]=max+1;
    }

 max=0;
 for (i=1;i<=n;i++)
    if (max<=v[i])
      max=v[i];

 fprintf(g,"%ld",max);
 }
 fclose(f);
 fclose(g);
 return 0;
}

Destul de lunga sursa da' va rog sa o examianti poate imi spuneti si mie ce are.

Editat de moderator: Cand postezi cod apasa si tu butonul "Code" :P sa se pastreze indentarea

Titlul: 036 Cutii
Scris de: nivan din Octombrie 11, 2005, 20:20:09
Cosmine eu am cautat cartea in lung si lat si nu am gasit O(n log n) pt. subsir cescator maximal. Te rog sa-mi zici si mie pagina la care se afla.

Titlul: 036 Cutii
Scris de: u-92 din Octombrie 11, 2005, 21:04:27
din cate am vazut ai facut subsir crescator in O(n^2) (care se pare ca intra in timp).. dar poti sa implementezi solutia cu AIB (gasesti hinturi mai sus, este si un articol in ginfo).. si implementarea la subsir in n*lgn trebuie sa o cauti mai bine in ultimul capitol, nu-s chiar asa de multe probleme, o poti gasi relativ usor  :D

Titlul: Sal...
Scris de: Barbus Sergiu Dan Petru din Octombrie 25, 2005, 18:14:25
Am citit mesajele, si am scos o solutie, as zice eu combinata  :)

Am sortat cutiile dupa z (sa zicem, ca vad ca va place, desi merge dupa oricare din cele 3 dimensiuni, duh ...). Pentru incadrare in timp, sortare liniara
Parcurgand sirul ordonat dupa z, de la cea mai mica la cea mai mare, am folosit programare dinamica: astfel, best = numarul maxim de cutii care pot fi continute in cutia i.
din pacate nici asa nu am prins toate testele (TLE)...
pentru o si mai buna optimizare cutiile tratate deja le-am retinut intr-o lista liniara, in ordinea numarului de subcutii continute.
merge... timpi buni (sub 4 sec/test);

Titlul: Re: Sal...
Scris de: nivan din Noiembrie 09, 2005, 13:27:03
Mei yo pot sa bag o cuite in pzitia L h l  in o cutie mai mare care sta in pzitia h L l????   Adica trebuie sa le bag astefl incat lungimea mica sa orespunda cu lungimea mare, Latimea mica cu latimea mare shi inaltimea mica cu cea mare.....  Sau pot sa bag o cutie in alta cutie cum vreau eu doar sa mearga.....   ](*,)  aci cred ca am o problema.... Oricum fac cu subsir crescator in O(n2) shi iau WA. Asa ca nici n-are rost ca incerc in O(n log n) cum mi s-a sugerat mai sus.

Titlul: Re: Sal...
Scris de: nivan din Noiembrie 09, 2005, 13:29:49
Eu iau doar 10 puncte la rpoblema asta.... Ceea ce imi pare k e ciudat.

Titlul: 036 Cutii
Scris de: u-92 din Noiembrie 09, 2005, 14:15:46
eu zic ca ai gresit implementarea.. poti sa bagi cutia A in cutia B daca xA < xB, yA < yB, zA < zB.. ps: vad ca s-a modificat timpu` la 7 secunde, inainte parca era 9, nu prea cred ca mai intra acum n^2

Titlul: 036 Cutii
Scris de: nivan din Noiembrie 09, 2005, 19:51:24
mda    ](*,)

Titlul: 036 Cutii
Scris de: Adriana Sperlea din Noiembrie 13, 2005, 13:54:56
Citat din mesajul lui: nivan
Cosmine eu am cautat cartea in lung si lat si nu am gasit O(n log n) pt. subsir cescator maximal. Te rog sa-mi zici si mie pagina la care se afla.

pagina 160 :D in plus, merge si cu subsiru in n(n-1)/2 si un quicksort. Eu am luat 100 asa.

Titlul: 036 Cutii
Scris de: nivan din Noiembrie 14, 2005, 15:11:46
mda.... mersi ca mi-ai zis ca nu stiam (In primul rand problema mea nu e cu complexiatatea.. sau poate e dar nu asta e majora... ci faptul ca ia wrong answer sau cine stie ce ia ca e destul de complicat de descfifrat ce scrie acolo ... eu inteleg ca iau WA dar e posibil sa fie shi alte erori ca e destul de ciudat ce scrie)

Titlul: 036 Cutii
Scris de: u-92 din Noiembrie 14, 2005, 15:51:34
"erai aproape dar ai gafat" sau "belea.. ai gresit la greu" inseamna WA :)
cel mai bine refa codul.. (btw sper ca nu il folosesti pe cel postat mai sus, am obs. cateva chestii dubioase la sortare si la subsir)

Titlul: 036 Cutii
Scris de: nivan din Noiembrie 14, 2005, 16:05:55
Pei cu exceptia ca e facuta in O(n^2). Nu prea e nimik dubios. Dak nu intra in timp ... il refac in O(n log n). Care sunt acele chestii dubioase?

Titlul: 036 Cutii
Scris de: u-92 din Noiembrie 14, 2005, 16:17:58
hmm.. ce e cu vectorul v si de ce te opresti la subsir crescator la prima cutia "buna" gasita?

Titlul: 036 Cutii
Scris de: Adriana Sperlea din Noiembrie 14, 2005, 19:29:15
pai in vectorul v tine lungimea subsirurilor gasite pana acum, dar intr-adevar, ar trebui sa caute toate subsirurile din care poate face parte cutia curenta, si sal ia pe cel mai mare. Nu sa se opreasca la primul. Cu alte cuvinte trebuie scos break-ul ala de acolo.

Titlul: 036 Cutii
Scris de: u-92 din Noiembrie 14, 2005, 20:27:52
eu ma refeream la faptul ca sortarea nu e buna (la inceput pune in v produsul dimensiunilor)

Titlul: 036 Cutii
Scris de: Adriana Sperlea din Noiembrie 14, 2005, 21:53:19
sorry, nu m-am uitat decat la cum face subsirul nu si la sortare. Oricum amandoua nu sunt bune :P

Titlul: 036 Cutii
Scris de: Filip Cristian Buruiana din Noiembrie 14, 2005, 21:56:23
Bai omule, tu vrei mura-n gura? :-# Ce ar fi si eu sa postez o sursa de 200 de linii si sa rog pe cineva sa mi-o corecteze? Si dupa aia sa mai postez si vreo N-spe mesaje cu ce cred eu k e gresit sau nu e! Refa sursa aia, ce mare chestie sa implementezi un subsir crescator maximal? :annoyed:  

                                           bubbleSORT

Titlul: 036 Cutii
Scris de: nivan din Noiembrie 15, 2005, 13:59:46
Mersi ca mi-ai dat idee.... doar ca nu cred ca problema e de implementare ci de idee.
Scuze era de implementare... tocmai am citit ce a scris Adriana_S mai sus si mi-am dat seama.

mda... la inceput sortez dupa volum (apoi incep sa fac subsirul crescator).

Aici era greseala.... acum am luat 100 puncte !!!!!! Acum imi dau seama ca am fost idiot ](*,)   e posibil ca o cutie cu volum mai mic ca alta sa nu poata intra in ea !!!!  Acum am sortat dupa una din dimensiuni (nu conteza care).  Nu shtiu cum de nu mi-am dat seama mai devreme  :oops:

P.S.  Era gresit shi break-ul ala.... care nu mi-as fi dat seama (eu am crezut ca optimizez la timp.. dar din contra greseam la cursul algoritmului). Eh important e ca acum m-am prins.
Ah, shi vad ca a intrat in timp in O(n^2)... deci nu ma mai chinui cu O(n log n).

Titlul: 036 Cutii
Scris de: Tudorica Constantin Alexandru din Februarie 04, 2006, 18:37:21
Cod:
#include <stdio.h>
#include <stdlib.h>
FILE *f,*o;
int x[3502],y[3502],z[3502],q[3502],n,m,l,j,i,g,k,p;

int intra(int i,int j)
{
 return x[i]<x[j] && y[i]<y[j] && z[i]<z[j];
}

int main()
{
 f=fopen("cutii.in","r+");
 o=fopen("cutii.out","w+");
 fscanf(f,"%ld %ld",&n,&m);
 for (j=1;j<=m;j++)
 {
  p=0;
  for (i=1;i<=n;i++) fscanf(f,"%ld %ld %ld",&x[i],&y[i],&z[i]);
  for (i=1;i<=n;i++)
  {
   g=0;
   for (k=1;k<p;k++)
    if (!intra(q[k],i) && intra(i,q[k]+1)) { g=1; q[k]=i;}
   if (!g && intra(q[p],i)) { p++; q[p]=i;}
  }
  fprintf(o,"%ld\n",p);
 }
 fclose(f);
 fclose(o);
 return 0;
}

Imi poate explica si mie cineva de ce imi da "RUN ERROR - Invalid memory reference"???am compilat-o pe linux(Fedora 4) si imi merge.

Titlul: 036 Cutii
Scris de: Valentin Stanciu din Februarie 05, 2006, 11:24:13
am submitat codul tau pe infoarena si uite ce primesti:
Cod:
TEST 1	...[0.01s]...	erai aproape.. dar ai gafat
TEST 2	...[0.01s]...	belea.. ai gresit la greu..
TEST 3	...[0.02s]...	belea.. ai gresit la greu..
TEST 4	...[0.01s]...	belea.. ai gresit la greu..
TEST 5	...[0.38s]...	belea.. ai gresit la greu..
TEST 6	...[0.38s]...	belea.. ai gresit la greu..
TEST 7	...[0.38s]...	belea.. ai gresit la greu..
TEST 8	...[0.39s]...	belea.. ai gresit la greu..
TEST 9	...[0.38s]...	belea.. ai gresit la greu..
TEST 10	...[0.38s]...	belea.. ai gresit la greu..


eu nu vad nici un "RUN ERROR - Invalid memory reference"  :|

Titlul: 036 Cutii
Scris de: Tudorica Constantin Alexandru din Februarie 06, 2006, 13:49:15
acum doua zile dadea "RUN ERROR - Invalid memory reference" acum nu mai da. Poate a fost evaluatorul.

Titlul: Raspuns: 036 Cutii
Scris de: tmac din Aprilie 05, 2006, 17:43:07
am cateva nelamuriri :

1. AIB(arbori indexati binar respectiv arbori de arbori indexati binar) nu se pot folosi pentru a determina maximul, din cate stiu eu.
2. La arborii de intervale bidimensionali cu pcte si valoare cum pot determina maximul ? stiu sa numar cate puncte sunt, ca e usor de cautat binar indicii in vectorul respectiv, dar cum aflu maximul portiunii aleia dintre indici ... ; cum ar trebui sa fac inserarea de exemplu ? ca este clar ca trebuie adaugate punctele in ordinea sortarii dupa o coordonata, nu toate de la inceput ....  .
 



Titlul: Raspuns: 036 Cutii
Scris de: u-92 din Aprilie 05, 2006, 18:05:28
AIB se pot folosi pentru a determina maximul, dar numai pt portiuni de genul 1->x respectiv (1,1) -> (x,y)

Titlul: Raspuns: 036 Cutii
Scris de: tmac din Aprilie 05, 2006, 18:13:25
ah da asa e :)  ce n00b sunt. dar cum pot afla min/max in 2D cu arbori de intervale ? mar interesa si asta ... ms f mult :)

Titlul: Raspuns: 036 Cutii
Scris de: Filip Cristian Buruiana din Aprilie 05, 2006, 18:39:05
Pentru arbori de intervale 2D, te gandesti pur si simplu ca in fiecare nod al arborelui cu o dimensiune ai un alt arbore de intervale. Parcurgerea acestui arbore se face in felul urmator: daca de exemplu vrei sa strabati regiunea [x1, y1, x2, y2], atunci parcurgi toate nodurile care alcatuiesc [x1, x2] ( fiecare astfel de nod fiind un alt arbore de intervale ) si in acesti noi arbori parcurgi informatia dorita pt. [y1, y2] ( in fiecare nod initial ). Deci poti avea maxim O(logM) intervale pt. [x1, x2] si pentru fiecare astfel de nod, alte maxim O(logN) intervale pe [y1, y2], deci o complexitate finala de O(logN * logM), pe query / update.

Titlul: Raspuns: 036 Cutii
Scris de: tmac din Aprilie 05, 2006, 19:24:02
am inteles, ms mult. dar am o intrebare : cum pot sa fac o implementare eficienta ? adica si spatiu si timp, ca pare cam costisitoare construirea ...   ? poate nam inteles io bine daca ai putea sami dai detalii... ms f mult ;

Titlul: Raspuns: 036 Cutii
Scris de: Andrei Grigorean din Aprilie 05, 2006, 20:54:37
eu cred ca te complici cam mult.

daca sortezi numerele in functie de o dimensiune, ai redus problema la aflarea celui mai lung subsir crescator maximal. doar ca in acest caz relatia "<" trebuie sa fie adevarata ptr amandoua dimensiunile care ti-au ramas. o implementare in O(n^2) cred ca stii si tu, insa aceasta nu e destul de buna. poti folosi in schimb un AIB bidimensional ptr a reduce complexitatea la O(n log^2 n).

Titlul: Raspuns: 036 Cutii
Scris de: tmac din Aprilie 05, 2006, 21:39:19
am luat 100 p cu AIB ... mam prins ca poti calcula maxim pt (1.. x) credeam ca nu poti deloc. ma interesau si arborii de intervale 2D ca stiu doar reprezentarea aceea din ginfo, cu lista sortata dupa y in fiecare nod si e greu sa calculezi maxim pe ea.

Titlul: Răspuns: 036 Cutii
Scris de: Trimbitas Viorel Stefan din Martie 23, 2007, 07:52:08
Citat din mesajul lui: u-92 din Noiembrie 14, 2005, 20:27:52
eu ma refeream la faptul ca sortarea nu e buna (la inceput pune in v produsul dimensiunilor)

Nu am nimic impotriva ... doar sa fi spus si de ce ...

Sirul dimensiunilor L, l, h au o proprietate ... deci sirul poate fi citit direct sortat.

Titlul: Răspuns: 036 Cutii
Scris de: Cezar Mocan din Martie 23, 2007, 22:29:16
Se poate lua 100 daca se face subsir crescator maximal in n log n?? As vrea sa fac asa, dar adevarul e ca nu prea l-am inteles...  ](*,)

Titlul: Răspuns: 036 Cutii
Scris de: Bondane Cosmin din Martie 23, 2007, 22:38:30
subsirul crescator maximal se poate face si in n^2 si este mult mai usor de inteles  :thumbup:

l(i) cel mai lung subsir crescator care se termina cu a(i). Dupa ce vei avea pt fiecare i calculat => maximul ( l(i), i = 1..n ) este subsirul crescator maximal.

Titlul: Răspuns: 036 Cutii
Scris de: Cezar Mocan din Martie 23, 2007, 22:39:50
Da, pe ala il stiu, dar vreau sa invat ceva nou cu problema asta. (si in plus nu-mi intra in timp "bulaneala"). Si mi-e o lene sa ma apuc de AIB...  :'(. De aia intrebam de el...

Titlul: Răspuns: 036 Cutii
Scris de: Marius Stroe din Martie 23, 2007, 22:43:32
Gaseste o motivatie daca iti este lene.  :)

Sa iti zic eu una: e mai usor si mai elegant cu AIB.

Titlul: Răspuns: Răspuns: 036 Cutii
Scris de: Tabara Mihai din Martie 23, 2007, 22:44:34
Citat din mesajul lui: Cezar Mocan din Martie 23, 2007, 22:39:50
Da, pe ala il stiu, dar vreau sa invat ceva nou cu problema asta. (si in plus nu-mi intra in timp "bulaneala"). Si mi-e o lene sa ma apuc de AIB...  :'(. De aia intrebam de el...

Daca ai manualul de clasa XI-A, de Dana Lica si Mircea Pasoi, cauta la pagina 240-241.E explicatie si implementare  :ok:

 :thumbup:

[later edit] Cred ca il gasesti si pe net  :eyebrow:

Titlul: Răspuns: 036 Cutii
Scris de: Cezar Mocan din Martie 23, 2007, 22:52:16
Este si in GInfo, si mi l-a explicat un prieten, dar sunt asa de batut in cap ca nu l-am inteles...  :fighting:. Vreau sa-l gasesc undeva explicat ca pentru prosti... :D
@Marius Stroe: Da, ai dreptate... Totusi eu zic ca e mai "prioritar" subsiru crescator maximal in n log n. Am mai facut AIB (la datorii de exemplu), dar niciodata in 2 dimensiuni... si totusi... zici ca e mai usor?? :mrgreen:

Titlul: Răspuns: 036 Cutii
Scris de: Lucian Boca din Martie 24, 2007, 00:00:39
Acum imi dau seama ca nu (cred ca) se poate aplica algoritmul in n log n pentru cel mai lung subsir crescator la problem asta, deoarece nu exista relatie de ordine totala pe multimea punctelor din plan (o astfel de relatie ar fi echivalenta cu o relatie de ordine pe multimea numerelor complexe...). Asadar, nu se poate face cautarea binara din algoritmul in n log n... curaj cu AIB :D

Titlul: Răspuns: 036 Cutii
Scris de: tester din Octombrie 24, 2008, 16:34:32
nu exista cutii cu una dintre cele trei dimensiuni x ,y sau z egale nu ?

Titlul: Răspuns: 036 Cutii
Scris de: Andrei Grigorean din Octombrie 24, 2008, 16:38:11
Nu.

Titlul: Răspuns: 036 Cutii
Scris de: Tirca Bogdan din Noiembrie 14, 2008, 15:36:03
ìmi lasa si mie cineva niste teste mai mari?(si mijlocii dak se poate ) :rotfl:

Titlul: Răspuns: 036 Cutii
Scris de: Alex Mircescu din Noiembrie 23, 2008, 19:46:47
http://infoarena.ro/job_detail/222530
iau 10 puncte si sunt la sfarsitul puterilor... habar n-am ce are...
si nu's din ala care cere mura'n gura... m-am chinuit... eh.. nu mai zic...
un test ceva... ca sa-mi busheasca programu' ?   :-s

Titlul: Răspuns: 036 Cutii
Scris de: Andrei Grigorean din Noiembrie 24, 2008, 17:53:02
Programul nu buseste nimic. Pur si simplu algoritmul pe care il folosesti nu e corect. In plus are complexitatea O(N^2).

Titlul: Răspuns: 036 Cutii
Scris de: Tirca Bogdan din Decembrie 24, 2008, 16:25:57
Cu un quick sort si un scmax cu programare dinamica iei 0 puncte? :-k

Titlul: Răspuns: 036 Cutii
Scris de: Cezar Mocan din Decembrie 24, 2008, 16:37:19
S'a discutat si inainte despre asta. Se ia 40, cu TLE. Complexitatea optima este alta.

Titlul: Răspuns: 036 Cutii
Scris de: Tirca Bogdan din Decembrie 24, 2008, 16:40:35
Mda ma apuc sa vad ce scrie p'aici.ms

Titlul: Răspuns: 036 Cutii
Scris de: Vlad Tarniceru din Septembrie 08, 2010, 16:32:23
merge la limita ( http://infoarena.ro/job_detail/483433 ) si fara AIB daca pui:

inline bool cmp ()  

unde cmp este de la

sort (vector+1, vector+N+1, cmp); :)

Titlul: Răspuns: 036 Cutii
Scris de: Mircea Dima din Septembrie 09, 2010, 00:18:05
Si daca as micsora timpul de executie la 3.6 secunde ti-ar mai intra boolaneala ta? Eu nu prea cred...

http://infoarena.ro/job_detail/462653

Si apropo... tu ai raspuns la un topic in care nu s-a mai postat nimic din 2008

Titlul: Răspuns: 036 Cutii
Scris de: Vlad Tarniceru din Septembrie 09, 2010, 09:27:42
pai nu e sulutia optima, doar ca intra in timp la aceasta limita :) . scopul arhivei oricum nu este sa faci puncte ci sa inveti lucruri noi :)

Titlul: Răspuns: 036 Cutii
Scris de: Simoiu Robert din Septembrie 09, 2010, 12:01:30
La 5 secunde ar trebui micsorata limita ca sa intre orice solutie optima, solutia neoptima nu ar intra in 5 secunde.

Titlul: Răspuns: 036 Cutii
Scris de: Mircea Dima din Septembrie 09, 2010, 13:14:58
Sec... am scos timpi mai buni cu O(n^2) cu boolan (am facut un fel de pruning :D ) decat solutia mea in O(n log^2n) .

Deci... ar trebui imbunatatite testele  :))

http://infoarena.ro/job_detail/483617

LE: se pare ca am o sursa in O(nlog^2n) cu timpi mai buni decat boolaneala
http://infoarena.ro/job_detail/288044

Titlul: Răspuns: 036 Cutii
Scris de: Predescu Sebastian Ion din Noiembrie 14, 2018, 13:45:54
Sursa asta nu da 100!!!!!!!!!!!!!!!!!!!!  :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry: :angry:


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