036 Cutii

[•Cosmin]

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

[•Dark_Raxvan]

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.

[•cavendish]

evaluatorul suporta clase. ai grija cand trimiti rezolvarea sa pui 'c++' ... daca nu asta e problema, inseamna ca nu ai scris cod bun.

[vladut.forum]

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

[•Dorin]

da bineinteles ca este subsir maximal si eu asa am rezolvato si am luat 100 p

[•Cosmin]

vladut cred ca nu ai inteles ce se discuta mai sus ....

[nivan]

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" sa se pastreze indentarea

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

[u-92]

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  

[•danube]

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

[nivan]

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.

[nivan]

Eu iau doar 10 puncte la rpoblema asta.... Ceea ce imi pare k e ciudat.

[u-92]

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

[nivan]

mda    

[•Adriana_S]

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 in plus, merge si cu subsiru in n(n-1)/2 si un quicksort. Eu am luat 100 asa.

[nivan]

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)

[u-92]

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

[nivan]

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?

[u-92]

hmm.. ce e cu vectorul v si de ce te opresti la subsir crescator la prima cutia "buna" gasita?

[•Adriana_S]

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.

[u-92]

eu ma refeream la faptul ca sortarea nu e buna (la inceput pune in v produsul dimensiunilor)

[•Adriana_S]

sorry, nu m-am uitat decat la cum face subsirul nu si la sortare. Oricum amandoua nu sunt bune

[•filipb]

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?  

                                           bubbleSORT

[nivan]

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  

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

[•tudalex]

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.