840 Cuburi3

[•astronomy]

Aici puteti discuta despre problema Cuburi3.

[•cosgb]

Sal. La probl asta iau eroarea "Killed by signal 11(SIGSEGV)". Din c cauza? Am o coada de 2.000.000 d elemente  cu 2 campuri de tip long si in mod normal dupa calculele mele ar intra...dar coada este subdimensionata...asa ca nu stiu exact cauza: am coada subdimensionata si incerc sa folosesc niste zone d memorie care nu exista sau depasesc memoria? ( mai am si alte variabile sau vectori, dar in total acestea nu depasesc 100000 Kb)

[•gh09]

Ai prea multa memorie 2 * 2 mil = 4 mil....cam mult

[•Florian]

Fac problema cu dinamica in O(n^2), cu memoizare. Iau TLE pe testul 10. Fac cam asa:

pt fiecare i=1,n , daca !memo[ i ] atunci calc(i).

iar calc(i) arata cam asa:

int calc(int i)
{
daca (memo[ i ]) return memo[ i ];
pt (j=1;j<=n;++j) daca(j!=i && j se poate pune deasupra lui i) {  x = calc(j); daca(x>max) max = x; }
memo[ i ] = max + l[ i ];
return max;
}

Bineinteles, ca mai am doi vectori, unul care imi retine numarul de turnuri, iar celalalt pentru reconstructia drumului. Este cineva care a luat 100 in acest fel? Ce optimizare as putea face ca sa intre in timp?

[•Marius]

Fac problema cu dinamica in O(n^2), cu memoizare. Iau TLE pe testul 10. Fac cam asa:

Soluţia cu memoizare nu obţine 100p. Încearcă Varianta 2, sau chiar Varianta 3

[•Florian]

Ar trebui specificat lucrul asta in articolul cu solutii. Desi prima data mi-a venit in gand ideea de la varianta 2, cand m-am uitat pe articolul cu solutii, am observat ca solutia data in varianta 1 e mult mai usor de implementat... Dar se pare ca nu e optima...

[•gabor_oliviu1991]

Am o problema la afisarea indiciilor cuburilor care formeaza turnul. La testele mari imi afiseara cateva cuburi in plus la inceputul fisierului, restul fiind bune.

Cod:

 int k = 0;
    while(sol[poz_max] != 0)
           t[++k] = poz_max;
           poz_max = sol[poz_max];}

poz_max = la inceput e pozitia maximimului turnului
sol[ i ] = inaltimea maxima care are ca ultim element cubul i

[•Florian]

Nu ar trebui sa ai poz_max = pre[poz_max] (sau cv de genu)? Adica elementul de pe care "s-a venit" in poz_max pt a obtine acel sol[ poz_max ] . La tine sol[] e inaltime, iar poz_max e pozitie. Am inteles eu gresit?

[•gabor_oliviu1991]

Scuze, nu m-am exprima eu bine. sol[ i ] e tatal din care se ajunge in i cum zici tu. 

[•Bit_Master]

Ce legatura are problema asta cu Subsir crescator maximal? (ca acolo se face referire la ea)

[•SpiderMan]

Citeste solutia oficiala si ai sa vezi legatura.

[•thesilverhand13]

Am o intrebare pentru cei carora li s-a mai intamplat sa ia WA pe ultimele 7 teste....care era bugul? Mentionez ca folosesc varianta a 2-a din solutia oficiala,cea a subsirului crescator maximal de complexitate O(n^2).Multumesc anticipat!

L.E:Never mind....am luat suta  .

[•ctlin04]

Nu inteleg de ce iau numai primele doua teste, inteleg TLE pe ultimul, dar nu inteleg de ce iau incorect pe celelalte, fac PD O ( n^2 ), si pe exemplele mele merge bine, ma poate ajuta cineva, pls ? 

[•PlayLikeNeverB4]

Cum sa te ajute lumea? Sa ghiceasca ce ai gresit? Posteaza si tu ceva cod sau descrie-ti solutia.
Ai grija la sortare (cand una dintre dimensiuni e egala cum faci cu cealalta), acelasi lucru si la subsirul crescator.

[•ctlin04]

Uite codul:
code:

begin
 assign(fi,'cuburi3.in');
  assign(fo,'cuburi3.out');
 settextbuf(fi,b1);
  settextbuf(fo,b2);
 reset(fi);
  rewrite(fo);
 readln(fi,n);
 for i:=1 to n do begin
                     readln(fi,a[ i ].l,a[ i ].g);
                     a[ i ].ind:=i;
                     end;
 qsort(1,n); j:=0;
 for i:=1 to n do
  if a[ i ].l=a[i+1].l then inc(j)
   else if j>0 then begin
                    qsort2(i-j,i);
                     j:=0;
                    end;
 b[n].h:=a[n].l; b[n].pos:=n; b[n].nr:=1; b[n].ind:=a[n].ind;
 max2:=b[n].h; posmax2:=n;
 for i:=n-1 downto 1 do begin
                 max:=0; posmax:=i;
                 for j:=i+1 to n do
                  if (a[ j ].g<=a[ i ].g) and (b[ j ].h>max) then begin
                                                              max:=b[j].h;
                                                              posmax:=j;
                                                              end;
                 b[ i ].h:=a[ i ].l+max; b[ i ].pos:=posmax;
                  b[ i ].nr:=b[posmax].nr+1; b[ i ].ind:=a[ i ].ind;
                 if b[ i ].h>max2 then begin
                                  max2:=b[ i ].h;
                                  posmax2:=i;
                                  end;
                 end;
 writeln(fo,b[posmax2].nr,' ',b[posmax2].h);
  j:=posmax2;
 repeat
 writeln(fo,b[j].ind);
 dec(b[posmax2].nr);
  j:=b[j].pos;
 until b[posmax2].nr=0;
close(fo);
end.
Cimpurile tabloului a sunt : l=latura, g=greutatea, ind=numarul de ordine cum apare in sirul initial;
Cimpurile tabloului b sunt : h=inaltimea maxima a turnului la baza caruia se afla elementul i;
pos=pozitia din care s-a format maximul respectiv; nr= cite cuburi formeaza turnul respectiv; ind= pozitia cubului in sirul initial, cam asta.
LE: S-a rezolvat, uitasem sa fac ceea ce e insemnat cu rosu, o greseala mica dar care te costa 80 de puncte 

[•PlayLikeNeverB4]

Presupun ca ordonezi valorile in ordine descrescatoare. Cred ca ar trebui un posmax:=0; (sau vreo pozitie a vectorului care ia valoarea 0 tot timpul) dupa max:=0; la fiecare iteratie a lui i. Daca nu ma insel, pici astfel de teste:

Cod:

4
1 4
2 5
4 3
6 1

P.S.: Data viitoare cand postezi un cod pune-l intre tagurile [code] [/code]
P.S. 2: In mijlocul unui cuvant se scrie â din a, nu î din i
P.S. 3: Treci la C.

Edit: Aa, exact cand am scris ai corectat

[•VisuianMihai]

la mine da la testul tau 2 3
                                  2 1
Dar punctajul meu e ca all lui ctlin

[•VisuianMihai]

observati ceva in neregula in codul meu?? in afara de ultimul TLE...

Cod:

for ( i = 1; i <= n; i++ )
	{
		fin >> a[i].l >> a[i].g;
		b[i] = a[i];
	}
	do
	{
		gata = 1;
		for ( i = 1; i < n; i++ )
			if ( b[i].g < b[i+1].g )
			{
				aux = b[i];
				b[i] = b[i+1];
				b[i+1] = aux;
				gata = 0;
			}
	}
	while ( !gata );
	maxim[n] = 1;
	for ( i = n-1; i >= 1; i-- )
	{
		maxim[i] = 1;
		for ( j = i+1; j <= n; j++ )
			if ( b[i].l >= b[j].l && maxim[i] <= maxim[j] )
			{
				maxim[i] = maxim[j]+1;
				poz[i] = j;
			}
			if ( maxim[i] > max )
			{
				max = maxim[i];
				p = i;
			}
	}
	fout << max << ' ';
	i = p;
	while ( i != poz[n] )
	{
		s+=b[i].l;
		c[++k] = b[i];
		i = poz[i];
	}
	max = 0;
	min = 99999;
	for ( i = 1; i <= n; i++ )
	{
		if ( c[i].g > max )
		{
			max = c[i].g;
			max2 = c[i];
		}
		else
		if ( c[i].g < min && c[i].g != 0 )
		{
			min = c[i].g;
			min2 = c[i];
		}
	}
	fout << s << '\n';
	for ( i = 1; i <= n; i++ )
		if ( a[i].g == max2.g && a[i].l == max2.l )
			fout << i << '\n';
	for ( i = 2; i < k; i++ )
		for ( j = 1; j <= n; j++ )
			if ( a[j].l == c[i].l && a[j].g == c[i].g )
				fout << j << '\n';
			for ( i = 1; i <= n; i++ )
				if ( a[i].g == min2.g && a[i].l == min2.l )
					fout << i;
			fin.close();
			fout.close();
			return 0;
}

[•Bit_Master]

Citeste solutia oficiala si ai sa vezi legatura.

ms

[•Mitza444]

Imi puteti spune de ce iau WA inafara de 2 teste .Am facut o structura in care am retinut lungimea,greutatea si indicele initial.Am sortat crescator structura dupa latura sau daca e latura egala dupa greutate .Dupa am facut subsir crescator maximal de la capat incoace si dupa reconstitui solutia,pe care o afisez in ordine inversa.

Cod:

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct cub{
	int l,g,ind;
}v[4001];
bool comp(cub x,cub y){
	if(x.l==y.l)
		return (x.g<y.g);
	else 
		return (x.l<y.l);
}
vector < int > w;
int best[4001],poz[4001],nr[4001];
int main(){
	int n,i,p,j,mx=0;
	freopen("cuburi3.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&v[i].l,&v[i].g);
		v[i].ind=i;
	}
	fclose(stdin);
	sort(v+1,v+n+1,comp);
	freopen("cuburi3.out","w",stdout);
	best[n]=v[n].l;
	poz[n]=-1;
	mx=v[n].l;
	p=n;
	nr[n]=1;
	for(i=n-1;i>=1;i--){
		poz[i]=-1;
		best[i]=v[i].l;
		for(j=i+1;j<=n;j++){
			if(v[i].g<v[j].g && best[i]<best[j]+v[i].l){
				best[i]=best[j]+v[i].l;
				poz[i]=j;
				nr[i]=nr[j]+1;
				if(best[i]>mx)
					mx=best[i],p=i;
			}
		}
	}
	printf("%d %d\n",nr[p],mx);
	i=p;
	while(i!=-1){
		w.push_back(v[i].ind);
		i=poz[i];
	}
	for(i=w.size()-1;i>=0;i--)
		printf("%d\n",w[i]);
	fclose(stdout);
	return 0;
}

[•geniucos]

Eu am facut solutia cu AIB dar mai exact am folosit arbori de intervale.
In fine am luat 70,toate variabilele declarate in int.Imi mergeu testele 1,2,3,4,5,6,7;
Apoi am pus toate variabilele declarate in long long.Si imi merg testele 1,2,3,4,5,7,8,pe ultimul TLE;
NU INTELEG DE CE.Teoretic nu ar trebui bagate in long long si oricum nu inteleg de ce dupa o modificare ca astanu imi mai merge testul 6,nu are logica,Mi-am dat o groaza de teste toate imi merg.Ma poate ajuta cineva?

[•SebiSebi]

Da, intradevar nu trebuie long long, insa este destul de ciudat ce se intampla. Nu trebuie neaparat sa folosesti AIT , merge si in complexitate patratica foarte repede deoarece n <= 4000. Incearca asa si vedem pa urma ce se intampla.

[•DEYDEY2]

iau 80p cu 2 WA si nu imi dau seama de ce. Vreo idee?

[•PlayLikeNeverB4]

Pot fi si egale dimensiunile (latura sau/si greutatea).

[•DEYDEY2]

Multumesc!