083 Evantai

[•domino]

Aici puteţi discuta despre problema Evantai.

[VladS]

Am trimis mai multe solutii si nu iau mai mult de 15 puncte cu solutia in N^4. Imi poate spune cineva care e greseala in secventa urmatoare.

Cod:

for (i=n-1;i;--i)
	for (j=i+1;j<=n;++j)	
		{
		mat[i][j]=1;
		for (k=i+1;k<j;++k)
			for (l=k+1;l<j;++l)
				if (v[k] + v[l] < v[i] + v[j])
					mat[i][j] += mat[k][l];
		total+=mat[i][j];
		}

[vladut.forum]

wow, N^4, nici o sansa pt 100 de puncte...

[VladS]

Gata, am gasit. Uitam sa fac modulo 30103  

[•Dorin]

Un evantai este un şir cu un număr par de termeni, E1 E2 ... E2K, cu următoarea proprietate:

E1 + E2K > E2 + E2K-1 > ...  > EK + EK+1

in exemplu spune ca sunt 7 nu??
deci o sa fie subsir evantai elementul de pe poz 1 cu elementul de pe poz 2
adica k =  1  E1 = 1 , E2k = 2
E1 + E2k >= E2 + E2k-1 deci nu e strict mai mare

unde e problema in enunt sau gandesc eu gresit exemplul???[/i]

[•Dorin]

sin in exemplul

Cod:

evantai.in
6
1
2
3
4
5
6

cate subsiruri vor fi evantai 23

[vladut.forum]

de ce nu iei codul de mai sus, chiar daca e ineficent pt exemplu asta merge

[•silviug]

cate subsiruri vor fi evantai ???23???

Nici nu pot fi 23 de subsiruri de lungime para pentru un sir de 4 elemente!!! Numarul de subsiruri de lungime para este 7:
- 6 de lungime 2 (combinari de 4 luate cate 2)
- 1 de lungime 4 (sirul insusi)

Toate 7 sunt evantai.

Exemplu era facut sa va spuna ca se numara si subsirurile de lungime 2.

Silviu Ganceanu

[•silviug]

TYTUS, tu chiar ai luat 100 cu N^4 ?

Silviu

[•Dorin]

Numarul de subsiruri de lungime para este 7:

eu am intrebat pentru exemplul ce l-am dat eu cate sunt nu pentru exemplul din problema
adica

Cod:

evantai.in
6
1
2
3
4
5
6

dar o sa fac oricum cum a zis vladut poate iasa raspunsul  

[vladut.forum]

silviu doar ti-a explicat ceva. aduti aminte ce-ai spus mai sus...

unde e problema in enunt sau gandesc eu gresit exemplul???[/i]

 

[•Dorin]

da mi-am dat seama numa ca dupa ce am trimis mesajul ms oricum
am aflat pana la urma care erea problema

[VladS]

Pt Silviu: nu, codul il foloseam ca verificator pentru solutia cu AIB.

[•silviug]

Okay.. m-am linistit

[•filipb]

Iau TLE pe 7 teste. Am folosit o idee aflata de la Cosmin Negruseri: am luat toate perechile si le-am sortat in functie de suma lor ( sortare liniara, un fel de radixsort ). Si dupa aia aflam sumele unor submatrici din AIBul meu si actualizam. Am actualizat AIBul cam asa ( cea mai rapida implementare pe care o cunosc ):

Cod:

void query(int x, int y)
{
	int p1 = 1, p2 = 1, sy;

	while (x > 0)
	{
		sy = y; p2 = 1;
		while (sy > 0)
		{
			S = (S + A[x][sy]) % MOD;
			while ((p2 & sy) == 0) p2 <<= 1;
			sy -= p2;
			p2 <<= 1;
		}

		while ((p1 & x) == 0) p1 <<= 1;
		x -= p1;
		p1 <<= 1;
	}

}

Pentru a afla suma pe o portiune dreptunghiulara scad si adun niste submatrici cu coltul in (1,1) (4 matrici).

Ce pot sa fac sa scap de TLE?    

P.S: Complexitatea mea e O(N^2 log^2 N).

[•silviug]

Chiar Cosmine.. tu cum faceai problema asta, ca niciodata nu te-am ascultat pana la capat

Filip, daca vrei iti spun cum o faceam eu.. Mi-aduc aminte ca nu-mi trebuia query decat pentru dreptunghiuri cu coltul in (0,0) (am vazut ca pomeneai ceva de adunat si scazut de prin colturi, nu prea m-am uitat pe codul tau).

Iar AIB-ul tau cred ca e comparabil cu ce faceam eu in solutia oficiala. Totusi, incearca sa compari versiunea ta cu versiunea cu LSB(x) (o gasesti prin surse oficiale, daca nu zi-mi si ti-o trimit prin email) pe niste teste mari (chiar sunt curios ce iese).

Have fun,

Silviu

[•gogu]

filipb, un sfat: renunta le operatia %.
Instructiunea

Cod:

S = (S + A[x][sy]) % MOD; 

poti sa o inlocuiesti cu

Cod:

S += A[x][sy];
if (S>=MOD) S-= MOD;

Face minuni la timpul de executie. De asemenea, cred ca ar trebui sa te folosesti de formula ca sa aflii cel mai nesemnificativ bit de 1 in O(1).

[u-92]

o implementare mai rapida la aib cred ca ar fi asta

Cod:

int query(int x, int y)
{
     int r = y, val = 0;
     for(; x > 0; x -= (x^(x-1))&x)
      for(y = r; y > 0; y -= (y^(y-1))&y)
         val += A[x][y];
     return val;
}

si ideea e ca iti trebuie elementele mai mici ca x de pe pozitii intre y1 si  y2,
deci A

• [y2] (deoarece pe pozitiile mai mici ca y1 nu ai updatat nimic)

[•Cosmin]

Pai eu luam toate perechile de indici i,j si sortam a + a[j]. Dupaia lucram cu punctele (i, j) cu suma a+a[j] luate in ordine dupa suma lor. Acuma ma interesa cate subsiruri incep cu i1 se termina cu j1 si au suma a[i1] + a[j1] au suma mai mica (adica puncte (i1, j1) care le-am inserat deja in structura) cu proprietatea ca i < i1 < j1 < j. Ca sa fac chestia asta bagam un range query pe arborele de intervale si un update dupaia ca sa inserez punctul. Asa scapam de restrictia asupra valorilor elementelor sirului pt ca ne intereseaza doar ordinea sumelor nu si valoarea lor.

Edit: Se pare ca solutia mea e ca si a lui filip

[•silviug]

Marfa gandit. Ai folosit arbori de intervale sau AIB-uri ?

Query-ul tau e tot intr-o structura 2D, corect ? (e un query cu varfuri in [0,0] si [i, j])

Silviu

[•filipb]

10x all de sfaturi Aveam TLE de la chestia cu % ( )...