1008 Inv

[•stef2n]

Aici puteți discuta despre problema Inv.

[•w4nt3d]

Cum pot sa nu depasesc timpul la problema asta?

Am reusit sa o fac doar de 30 pct.

[•Mishu91]

Cum pot sa nu depasesc timpul la problema asta?

Am reusit sa o fac doar de 30 pct.

Să o rezolvi în complexitate optimă, O(NlogN).

[•w4nt3d]

Usor de zis... Imi puteti da mai multe indicatii?

[•mathboy]

Arbori indexati binar sau arbori de intervale. Tu alegi

[•Mishu91]

Normalizezi numerele date, iar apoi ții un arbore indexat binar pentru a afla câte numere parcurse anterior sunt mai mari decât numărul actual.

[•blasterz]

Exista o solutie folosind divide et impera (merge_sort putin modificat) care cred ca e mai abordabila de catre un elev de clasa a10a.

[•Cristi09]

Salut!
Am incercat rezolvarea problemei ca in solutie(folosind un arbore de intervale) si iau 90pct(TLE pe testul 9),dar nu imi dau seama ce-as mai putea optimiza.
As vrea sa stiu daca normalizarea se mai poate imbunatati:

Cod:

          int arb[264010],n,v[100000]....;
          struct structura
          {
	           int pos,val;
           };
           .....
           
           ifstream f("inv.in");
	f>>n;
	int i;
	structura sort[100000];
	for(i=0;i<n;++i)
	{f>>v[i];sort[i].val=v[i];sort[i].pos=i;}
	f.close();
	qsort(sort,n,sizeof(structura),cmp);
	int ct=0;
	for(i=0;i<n;++i)
	{
		if(sort[i].val!=sort[i-1].val)++ct;
		v[sort[i].pos]=ct;
	}

Multumesc anticipat!

[•SpiderMan]

Incearca sa sortez cu ajutor Sortului din STL:

Cod:

sort (vector, vector + nr.elemente) - incepand de la vector[0] -> vector[nr.elemente-1]
sort (vector + 1, vector + nr.elemente + 1) - incepand de la vector[1]-> vector[nr.elemente] 

Trebuie sa incluzi headerul algorithm.

[•Cristi09]

Multumesc mult!
Am luat 100!

P.S. De acum inainte nu-am sa mai folosesc qsort-ul.

[•SpiderMan]

E mult mai util Sortul din STL si mai usor, pentru mai multe detalii aici .

[•MciprianM]

Asta e prima problema pe care am facut-o cand am fost eu la excelenta pe clasa a 11-a la domnul profesor Ilea ( cu merge sort ) asa ca m-am bucurat mult cand am intalnit-o din nou. Si CezarMocan era acolo. Nu stiu cum de ia doar 60 de puncte. Poate ne spune ce algoritm incearca(cu cautare binara?) ;
P.S.: Problema asta apare si in Cormen, iar pe timus este o variatie(problema 1090).

[•wefgef]

Eh, Cezar ia 60 din cauza ca nu stie sa normalizeze .

[•vladtarniceru]

din complexitatea oficiala (NlogN), logN e de la cautare binara?

[•blasterz]

Nu... sunt 2 solutii. La una logn vine de la aib / arbore de intervale.
Iar la cealalta solutie e un fel de merge-sort

[•VisuianMihai]

Merge sort, aib sau robert spunea quicksort in STL. Oare un radix sort nu ar merge?

[•SpiderMan]

Merge sort, aib sau robert spunea quicksort in STL. Oare un radix sort nu ar merge?

Daca merge N log N, o sa mearga si radix sortul in N * C (C = constanta mica). Si vezi ca in STL e introsort, nu quicksort .

[•klamathix]

Radix sort-ul nu e N * constanta mica. N* lungimea medie a radixului eventual, si nu ai cum sa alegi un radix care sa nu depinda nici de N si nici de magnitudinea numerelor.
Vezi ca tu trebuie sa numeri inversiunile, nu sa sortezi. Gandeste-te la asta.

[•VisuianMihai]

Ceva nu e bine. Imi da KBS la toate si daca declar vector de 5.000.000 sau 100.001 si nu stiu de ce.

[•an_drey_curent]

Am normalizat vectorul.
Incerc sa fac un arbore de intervale in care: in nodurile interne memorez minimul din intervale. Daca minimul e mai mare decat elementul actual, atunci am gasit ,,lungimea intervalului" inversiuni si nu caut mai departe in acel interval. Daca am ajuns pe frunza, compar cu elementul actual si daca e mai mare(frunza), adun la rezultat 1. Apoi inserez in arbore elementul actual ... Ori ideea de a folosi arborele de intervale nu e buna, ori implementarea ca iau 20 de puncte  
Implementarea e cam identica cu problema din arhiva educationala.

Update: Rezolvata, nu era ideea buna de folosire a arborelui.

[•repp4radu]

Am implementat ideea cu merge sort in O(n log n) si imi da ok pe toate testele pe care mi le-am dat eu, dar la evaluare prind numai testul 10. Mi-ati putea da unul din testele de la aceasta problema sa imi dau seama ce nu fac bine?

Multumesc anticipat!

LE: am rezolvat. Uitam sa fac restul impartirii )

[•ion824]

Am facut o rezolvare dupa cum e spus in solutia oficiala dar iau doar 70p. Mă gândesc că greseala ar putea fi in cautarea numarului de pozitii mai mari ca cea curenta.
Eu fac asa:partea cu sortarea , apoi caut in arbore pozitia curenta+1 si cind o gasesc ca limita de jos a intervalului ce-l contine nodul dat atunci adaug valoarea data si adaug si valoarea descendentului drept in caz ca div+1>val , apoi introduc in arbore si pozitia elementului curent. Poate are cineva idei unde ar putea fi greseala ?

[•Procopliuc]

Daca folosesti functia sort din STL vezi sa compari si pozitiile elementelor in caz de egalitate(dupa sortare elementele egale nu pastreaza ordinea din vector).Asta greseam eu,poate te ajuta si pe tine.

[•ion824]

Folosesc sortarea din stl ,dar am facut functia de comparare aparte, si am si verificat sortarea pe asha cazuri . Poate cineva care a facut cu arbori de intervale sa-mi explice poate cumva altfel ar trebui sa lucrez cu arborele...

L.E. S-a rezolvat. Era problema cu functia de comparare a sortare , in ciuda faptului ca credeam ca merge perfect sortarea.

[•mirceati]

Help!!! Cum descarc solutiile cpp trimise de participanti?