infoarena

Aici puteţi discuta despre problema Sortari (http://infoarena.ro/problema/sortari).

care e valoarea maxima a lui t?

10

:-' traiasca time.h si stdlib.h cu tot cu rand() -ul lui..
(100) :P

=D> tot asa ...

Complexitatea fara bulaneli  [-X este O(2^N * M)? TLE pe 3 teste... Oricum, ma intreb cat ar fi luat un O(N! * M)...  :-k Ca un random ia 100 fara probleme.. nu as vrea sa vad problema asta intr-un concurs...  :P

   Oricum, O(2^N * M) e complexitatea oficiala?

Da complexitatea este O(2^n*m) folosind principiu 0-1 in retele de sortare. Problema a fost pusa doar pentru exercitiu nu a fost conceputa pentru concurs motivul fiind randomul care se comporta mai mult decat "binisor".
Un O(n!*m) lua destul de putin...

:shock: am aflat in cele din urma ca ce faceam eu, era adevarat, adika chestia asta cu 0-1,

cum se face cu "0-1" ? care e principiul 0-1 in retelele de sortare ?

Cristi: Uita-te in Cormen. Ideea e ca daca o retea de sortare sorteaza bine orice secventa formata din 0 si 1 atunci ea sorteaza bine orice secventa de numere.

Vlad: Vrei sa zici ca te-ai prins singur de rezolvare fara sa stii principiul 0-1? :o

dap, pai dupa ce am facut random asta mi-o fost idea urmatoare cu 0,1 am implementat, da am gresit in implementare si am luat 70 (restu wa).
no serios nu stiam ca exista teorema. eu o foloseam doar ca asa mi se parea mie ca ar tb sa mearga, ca ziceam ca pe mine ma intereseaza doar relatia a > b, (ca sa le interschimb) si am zis ca e indeajuns sa folosesc 0 si 1, ( 1 > 0 ). Azi am aflat dupa cum am zis, ca chestia asta e teorema, funny  :))

Nu e clar daca operatiile pot sau nu pot fi puse in orice ordine ...

Eu am rezolvat problema luand in ordinea data in fisier  operatiile si am luat 0. Ma rog..e posibil sa fi implementat prost...dar cum e pana la urma cu operatiile, care e ordinea ?  :?

Cea din fisier !

 :-k .. mi'a luat doar 3 teste.. in rest , incorect...  ???

Se poate afla numarul de 0-uri din reprezentarea binara a unui numar, in timp constant? Daca da, cum?

Precalculezi :P.

Daca numarul este pe 32 de biti, nu iti ajunge insa memoria. Trebuie sa precalculezi ptr valorile intre 0 si 1 << 16, si apoi vei face suma a doua valori cand vrei sa afli cate 0-uri contine un numar.

Eu am verificat pentru fiecare numar de la 0 la 2ⁿ-1 daca bitii lui pot fi sortati. Complexitate O(2ⁿ(M+N)). Cand verific daca bitii sunt ordonati imi ia O(N) - verific toti bitii. Cum as putea optimiza? Iau TLE pe ultumul test.

LE: Pentru memorarea celor M operatii foloseam un singur vector (codificam cele 2 valori intr-una singura). Acum folosesc 2 vectori si programul se incadreaza in limita de timp pentru toate testele.

Eu am aceeasi complexitate.

Ai grija sa nu faci calcule inutile? Daca ai gasit o configuratie care nu poate fi sortata, dai un break acolo?

Eu m-am gandit asha:
Am luat cazul extrem in care vectorul este sortat descrescator.Ca acesta sa poata ajunge sortat crescator, asupra lui trebuie sa fie facute cel putin n*(n-1)/2 operatii.Daca se faceau mai putine operatii, afisam 0,daca nu luam un vector de n elemente pe care il initiam c=n-i+1(adik sortat descrescator, cazul extrem), apoi faceam operatiile asupra lui in ordinea in care erau in fisier si apoi verificam daca este sortat.Am luat doar 30 p si pe restu WA.  :'(
Ma poate ajuta cineva cu un exemplu pe care algoritmul meu sa nu mearga.

Imi poate da cineva un material de unde sa aflu mai multe despre aceste retele de sortare. :P

Nu cred ca-i adevarata chestia asta.
De exemplu, sa zicem ca ai:
5 4 3 2 1

Tu zici ca ai nevoie de 5*4/2 adica 10 operatii. Dar nu ai nevoie decat de 2:
1 5 => 1 4 3 2 5
2 4 => 1 2 3 4 5

Tu trebuie sa vezi daca operatiile din fisier sorteaza corect orice sir format din 0 si 1. Asta poti face cu back, pe biti sau cu random.

Eu ma gandisem ca tre sa verific fiecare cu fiecare si asa am ajuns la chestia aia :P.Mersi pt ajutor.
Oricum am mai trim o data sursa fara conditia aia si tot 30 p am luat asa ca o sa incerc pe biti si sa le pregenerez.

mie mi'a iesit cu random.. am generat 10000 de configuratii si am verificat daca dupa operatiile descrise sunt sortate sau nu..

Cred ca ar putea fi marita limita de timp la problema asta. Pentru 100 p a trebuit sa-mi precalculez intr-un vector puterile lui 2.  :-s

Puteai sa le obtii si folosind operatii pe biti (<<, shl).

am facut operatii pe biti am pus break-uri am parsat dar nu mi-a intrat nici cum in timp. Te poti uita peste surse :D

Eu am generat,pentru fiecare test, toate permutarile de n elemente , iar apoi pe fiecare permutare am vazut daca cele m interschimbari au sortat "permutarile" si imi da TLE. Cum as putea face cu generarea submultimilor , am vazut ca asa este indiciul.

Se poate demonstra ca o retea de sortare este buna daca sorteaza corect orice multime {0, 1}^N. Demonstratia e in Cormen parca.

Problema nu intra in O(t*m*n!)?

N-ar trebui.

Cu O(2^N * M) iau TLE pe 3 teste. Ce as putea optimiza?

Am rezolvat . Nu era nevoie decat de un break acolo unde trebuie.

Cred ca ar trebui marita limita de timp la problema asta.
Am complexitate O(T * 2 ^ N * M) si iau TLE pe ultimul test.
Folosesc operatii pe biti, parsez citirea, dau break la primul sir de biti care nu poate fi sortat, preprocesez puterile lui 2 cum a fost sugerat mai sus si tot nu intru.

Incearca cu back simplu, nu pe biti.  :ok:

Am luat 100. Mersi mult!  :yahoo: