Imprimă pagina - 083 Evantai

Titlul: 083 Evantai
Scris de: Mircea Pasoi din Iulie 12, 2005, 13:44:10

Aici puteÅ£i discuta despre problema Evantai (http://infoarena.ro/problema/evantai).

Titlul: 083 Evantai
Scris de: VladS din Iulie 15, 2005, 21:02:37

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];
		}

Titlul: 083 Evantai
Scris de: vladut.forum din Iulie 16, 2005, 12:47:10

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

Titlul: 083 Evantai
Scris de: VladS din Iulie 16, 2005, 13:56:04

Gata, am gasit. Uitam sa fac modulo 30103 :oops:

Titlul: 083 Evantai
Scris de: Oltean Dorin din August 04, 2005, 22:58:23

Citat

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]

Titlul: 083 Evantai
Scris de: Oltean Dorin din August 04, 2005, 23:27:41

sin in exemplul

Cod:


evantai.in
6
1
2
3
4
5
6

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

Titlul: 083 Evantai
Scris de: vladut.forum din August 05, 2005, 07:44:01

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

Titlul: 083 Evantai
Scris de: Silviu-Ionut Ganceanu din August 05, 2005, 10:56:00

Citat

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

Titlul: 083 Evantai
Scris de: Silviu-Ionut Ganceanu din August 05, 2005, 10:56:52

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

Silviu

Titlul: 083 Evantai
Scris de: Oltean Dorin din August 05, 2005, 12:52:40

Citat

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 :|

Titlul: 083 Evantai
Scris de: vladut.forum din August 05, 2005, 16:07:28

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

Citat

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

:-$

Titlul: 083 Evantai
Scris de: Oltean Dorin din August 05, 2005, 16:15:27

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

Titlul: 083 Evantai
Scris de: VladS din August 06, 2005, 15:21:05

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

Titlul: 083 Evantai
Scris de: Silviu-Ionut Ganceanu din August 08, 2005, 19:46:57

Okay.. m-am linistit :)

Titlul: 083 Evantai
Scris de: Filip Cristian Buruiana din Februarie 09, 2006, 16:26:30

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

Titlul: 083 Evantai
Scris de: Silviu-Ionut Ganceanu din Februarie 09, 2006, 17:04:49

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

Titlul: 083 Evantai
Scris de: Gogu Marian din Februarie 09, 2006, 17:36:45

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

Titlul: 083 Evantai
Scris de: u-92 din Februarie 09, 2006, 17:45:06

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)

Titlul: 083 Evantai
Scris de: Cosmin Negruseri din Februarie 09, 2006, 23:24:12

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

Titlul: 083 Evantai
Scris de: Silviu-Ionut Ganceanu din Februarie 10, 2006, 02:03:26

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

Titlul: 083 Evantai
Scris de: Filip Cristian Buruiana din Februarie 11, 2006, 12:41:46

10x all de sfaturi =D> Aveam TLE de la chestia cu % ( :? )...

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Iulie 12, 2005, 13:44:10