808 K1

[•bogdan2412]

Aici puteti discuta despre problema K1.

Problema a fost adaugata de Cezar Mocan. Mai multe detalii la Extinde arhiva.

[•miculprogramator]

Imi poate spune cineva cat da pentru datele:

Cod:

3
3
5
8

Multumesc anticipat.

[•vlad.doru]

Ar trebui sa fie modificat timpul si aici.. Nici citirea nu intra in timp.

[•danalex97]

Am impresia ca limita de timp e foarte mica. Se ia 60 cu O(N+xmax). 

[•Steve]

Limita e ok, mie mi-a intrat cu o metoda jmenoasa.
Ar merge poate un increase cu 0.05 din cauza ca nu intra fara parsare decat de ~90 puncte.
Complexitatea tinde spre O(N), numai ca trebuie o smecherie in rezolvare. Complexitatea reala e O(N + K log K), unde K <= 10000. Hope it helps, dati PM daca nu va prindeti.

[•danalex97]

Ai dreptate , uitasem sa parsez. Am luat 100.

[•ctlin04]

Si cum se face parsare la problema asta daca se da cite un numar pe rind 

[•danalex97]

In C este functie. In Pascal nu stiu.

Cod:

In.getline( Str,lmax,EOF ); // Str - sirul de caractere , lmax - nr maxim de caractere citite , EOF = end of file

[•ctlin04]

Ms, o sa incerc atunci in CPP, pur si simplu inca nu m-am deprins cu el 

[•veleandu]

Eu am rezolvat problema cu 2 deque-uri.
Solutia nu imi apartine, Rares mi-a spus-o cand veneam de la un lot ..

Mi se pare foarte trist ca nu poti lua 100 de puncte cu un algoritm o(n).
 ( sortarea se face in o(n) )
si practic generez cum decurg luptele ..


Daca omul ala vrea sa ii citesc 10^6 numere, eu i le citesc.

Daca vrea sa i le parsez, sa imi dea mai putine ...

[•VisuianMihai]

Alex Velea, imi poti spune si mie te rog cum faci sortarea in O(n)?

[•ctlin04]

Pai elementele din sir sunt mai mici ca 10 000, faci o distribuire si gata  
Adica tii un vector de 10 000 de elemente si pentru fiecare numar citit din fisier notezi in vector, apoi parcurgi tot vectorul de 10 000 de elemente si iti scoti din el cele n elemente sortate, codul ar arata cam asa:
COD:
 for (i=1; i<=n; ++i){ fin>>x; ++aux[ x ]; }
  n=0;
 for (i=0; i<=10 000; ++i)
    while (aux[ i ] != 0) {++n; a[n]=i; --aux[ i ]; }
si asta e tot.

[•klamathix]

Sortare O(N) nu exista, daca N are semnificatia pe care o folosim noi cel mai des, i.e numarul de elemente. Sortarile bazate pe comparatii sunt N log N si asa vor ramane, iar radix sort-ul e O(N log MAX_VALUE). Se spune despre radix sort ca e "liniar in marimea inputului", adica ar fi O(N) daca luam N ca fiind numarul de biti ai fisierului de intrare .

[•veleandu]

Mihai, sortarea se face in o(max_n+max_val) si totusi max_val e de 100 de ori mai mic decat numarul de elemente.
Nu poti spune ca se face in o(max_n)?

[•VisuianMihai]

Cat ar da pentru:
5
8
3
1
5
2

Mie imi da 41...

[•vendetta]

Raspunsul corect e 39.
Si ii iei asa : initial ai : 8 3 1 5 2.
Prima lupta : iei al 3 lea luptator cu ultimul luptator => Cost = 1 + 2 = 3; Raman luptatorii : 8 3 5 3(asta ultimul e noul format)
A 2-a : il iei pe al 2-lea si pe ultimul => Cost +=  3 + 3 = 9; Raman luptatorii : 8 5 6;
A 3-a : il iei pe al 2-lea si pe ultimul => Cost += 5 + 6 = 20; Raman luptatorii : 8 11;
Ultima lupta : pe primul si pe al 2-lea(evident ) ) => Cost = 20 + 8 + 11 = 39; Ramane doar unul singur si ma opresc

[•VisuianMihai]

De  ce 39? Nu inteleg...


Later edit... a, eu luam al 2-lea si al 3-lea dupa prima lupta, iar pe primul il luam ultimul...

[•superman_01]

 Salut,
poate cineva sa imi dea un hint pentru o suta? eu iau doar 60  folosind heapuri.
Multumesc anticipat!

[•pauldb]

Citeste indicatiile de rezolvare de la coduri huffman din arhiva educationala.