110 Granita

[•domino]

Aici puteţi discuta despre problema Granita.

[•MarcvsHdr]

Am rezolvat problema asta in O(N*logN) si iese din timp pe 7 teste. Am vzut ca a fost data la .campion 2003 si am cautat-o acolo. Solutia oficiala de acolo e tot O(N*logN)  .

DAR, limita de timp era acolo 0.2 sec. Intr-adevar, in 0.2 sec merge. E o greseala pe site cand s-a pus limita de 0.1? Daca nu, a rezolvat cineva si in O(N)??

[•m_dersidan]

Rezolvarea este in O(N log N), pentru ca e nevioe de o sortare, si intra in timp.

[•MarcvsHdr]

Am trimis DOAR citirea si sortarea, ca sa vad daca intra in timp, de curiozitate. Si nu intra nici macar citirea + sortarea. La sortare am folosit quick. Citirea o fac cu fscanf.

(later edit)
Gata, s-a rezolvat. Am inlocuit Quick Sort cu un Heap Sort. Se pare ca totusi exemplele erau bine alese ca sa nu intre Quick in timp.

[•m_dersidan]

Intra si quick sort in timp, trebuia doar sa il faci random.

[•crus]

daca nu intra quick...incearca merge...

[•Florian]

Ei bine...eu iau 80 de puncte cu bubble sort....Am trimis o sursa cu quicksort si luam 0, cu TLE pe toate...Este ciudat cum bubble este mai rapid ca quick..,.[ps: nu inteleg ce e ala quicksort random!  Poate ma poate ajuta cineva, k vreau sa invat si eu, va rog! ] 

[•stef2n]

La quicksort-ul normal, pentru un interval [A,B] afli pozitia pe care trebuie sa stea pivotul A astfel incat toate elementele din stanga sunt mai mici, iar toate elementele din dreapta sunt mai mari ca el. La quicksort-ul aleator, in loc de A folosesti ca pivot alt element din intervalul [A,B], pivot pe care il generezi random

[•CezarMocan]

Sau se poate sa iti randomizezi un pic valorile inainte de sortare... eu asa am facut si am luat 100.

[•cos_min]

Cel mai usor ii cu un set 

[•crus]

poate pe tipurile astea de teste...quiksort scoate un timp mai prost...aproape de N^2...incearca merge sort...ala sigur intra

[•gabitzish1]

merge si quicksort.. mie mi'a intrat la problema asta..cel mai mare timp a fost 40ms... deci e destul de bine.

[•ciprianf]

Salut...am vazut problemele alea cu qsort si asa ca m-am gandit sa va postez o sortare f f buna pe care eu o stiu sub numele de sheel( la aceasta probl cel mai mare timp a fost de 20 ms), fie v vectorul nostru care contine n numere, numerotate de la 1 la n:

Cod:

 
inj=n;
while(inj>1){
		inj/=2;
		do{
			gata=1;
			for(i=1;i<=n-inj;i++)
				if(v[i]>v[i+inj]){
					aux=v[i];
					v[i]=v[i+inj];
					v[i+inj]=aux;
					gata=0;
				}
		}
		while(!gata);
	}

sper sa fie de folos cei care nu au facut inca problema
         

[•wefgef]

Algoritmul postat de tine (shell sort) este destul de ineficient pentru seturi mari de date, insa pentru un numar mai mic de elemente este unul din cei mai rapizi algoritmi cunoscuti. In plus, nu are nevoie de memorie suplimentara.

[•ciprianf]

Si cam de la cat incep "seturile mari de date?" si pt aceste seturi ce metoda folosesc? qsort?

[•skyel]

Depinde foarte mult si de cum e aranjat sirul initial. Pentru ca exista seturi de date pe care shell sort poate ajunge O(N^2). Pentru mai multe info poti sa cauti pe wikipedia....cred

[•wefgef]

In general e bine sa folosesti quicksort pentru siruri mai mare de 100-200 de elemente. In C++ poti sa folosesti sort-ul din STL.

[•toni2007]

In general e bine sa folosesti quicksort pentru siruri mai mare de 100-200 de elemente. In C++ poti sa folosesti sort-ul din STL.

cum faci sort pentru structuri? se poate face?

[•wefgef]

Da, dar trebuie sa iti faci propria functie de comparare.

Cod:

typedef struct Fractie {
   int a, b;
} Fractie;

inline int cmp(Fractie A, Fractie B) {
    return A.a * B.b < A.b * B.a;
}

int N;
Fractie V[MAXN];

int main() {
    Citeste(V, N);
    sort(V, V+N, cmp);
}

Am schitat codul pentru un program care citeste in vectorul V N fractii pe pozitiile 0... N-1 si le sorteaza crescator.

[•andrei.finaru]

La problema asta se intampla ceva ciudat: am ok pe primele 3 teste si pe ultimul (care, judecand dupa memorie, e cel mai mare) si pe restul TLE. Cum pot sa ies din timp daca pe cel mai mare test imi intra, nu stiu. Am sortat structura cu mergesort si apoi am verificat cu :

Cod:

for(j=2;j<=n;j++)
		{q=1;
		while(q<j)
			if(a[q].s>a[j].s) {c++; q=j;}
				else q++;}

daca dispozitivul e redundant. Daca e un caz poate mai special va rog sa-mi dati un test sa ma prind si eu unde pica. Multumesc anticipat.

[•Florian]

Nu e bine cum verifici. Complexitatea ta e patratica. Trebuie un pic mai eficient. Incearca sa renunti la while-ul ala. 

[•andrei.finaru]

Mersi mult! Am luat suta:D:D:D

[•idomiralin]

Eu am facut quicksort si iau numa 20
Cod:

Cod:

int quick(int st, int dr)
{
     int i,j,piv,aux,aux1;
     i = st; j = dr; piv = a[(st + dr) / 2]; 
     while (i <= j)
     {
           while (a[ i ] < piv) ++i;
           while (a[ j ] > piv) --j;
           
                 if (i <= j)
                 {
                 aux = a[ i ];  
                 a[ i ] = a[ j ];
                 a[ j ] = aux;
                 aux = b[ i ];
                 b[ i ] = b[ j ];
                 b[ j ] = aux;  
                
                 ++i;--j;}
  }
  if (st < j) quick(st,j);
  if (i < dr) quick(i,dr);
}

Ce as putea imbunatati la quicksortu asta?(daca ma poate ajuta cineva)

Editat de moderator: Foloseste tagurile [ code ] [ /code ] cand postezi cod.

[•valentin.harsan]

cred ca trebuia sa fie  Aj<=Ai si Bi<=Bj  nu  Aj<Ai si Bi<Bj

[•Smaug-]

Cat trebuie sa de pt:

Cod:

3
1 10
9 12
11 20

Cod:

3
1 11
9 12
11 20