657 Heavy metal

[•DITzoneC]

Aici puteţi discuta despre problema Heavy metal.

[•taloibogdan]

Imi da doar Non-zero exit status(ca si la concurs)
Am largit limitele, am verificat impartirile,etc.,etc.
Imi ies toate testele!
NU INTELEG CE ARE!!!!!!

[•anna_bozianu]

Daca ai void main() schimba in int main() si scrie la final return 0

Si acum am si eu o intrebare. Cerinta e lungimea reuniunii intervalelor sau valoarea maxima a lungimilor reuniunilor de intervale disjuncte ? Mai precis o formatie este obligata sa cante intregul interval de timp [Ai,Bi] sau poate sa cante si pe un subinterval lasand apoi alta formatie sa intre?

[•CezarMocan]

Canta tot intervalul.

[•anna_bozianu]

10x.

[•tm_radu]

Am gasit la problema asta o rezolvare in O(n*log n). Care ar fi complexitatea oficiala?

[•astronomy]

Tot O(n*logn).

[•drag0sh]

cum se realizeaza normalizarea ?? :fighting:ca nu pot sa declar un vector de un miliard?ma poate ajuta cineva

[•astronomy]

Sortezi sirul initial si atribui fiecarui element indicele de dupa sortare. Adica daca V este vectorul sortat indicele lui V[1] va fi 1, a lui V[2] va fi 2 etc.

[•ciprianf]

Am trimis o sursa goala doar cu citire + qsort...si am luat ca timp +300ms....umpic cam nasol... zice-ti-mi si mie o sortare mai buna, si sa ma ajutati sa o implementez, va rog(PM daca se poate)

[•fireatmyself]

incearca 'sort' din STL. gasesti aici cateva informatii.
daca ti se pare complicat sa-l folosesti, poti sa faci qsort cu pivot ales random. merge mai repede decat qsort normal. aici gasesti un post de-ale lui Alex Tandrau, care explica pe larg cum se face.
inca un topic pe tema sortarilor este acesta.

[•toni2007]

mie mi-a intrat cu qsort in 204 ms deci nu cred ca e problema asta... singura smecherie e sa nu interschimbi structurile ci doar indicii (merge mai repede)

[•cosmin79]

Am luat 100 pct fara normalizare. Eu afisez cost[TMAX], TMAX=timpul maxim.Avand in vedere ca programul ia 100 pct, inseamna ca TMAX nu depaseste niciodata 2^17(atat am declarat eu vectorul).Cred ca ar trebui refacute o parte din teste 

[•rayvian]

Am sortat vectorii după ora de terminare, am folosit o relaţie de recurenţă ca cea prezentată aici: http://infoarena.ro/preoni-2008/runda-4/solutii şi totuşi la ultimele 2 teste îmi zice "Incorect". Au ceva special acestea 2? 

[•dutzul]

hmm nu vrea nici cum sami dea mai mult de 40 de pct(( am facut cu cautare binara dar nustiu ce greseste imi puteti da un test? de ex testul 1 ca pica pe el; ms

[•CezarMocan]

Testele oficiale nu se fac publice.  Daca vrei sa iti verifici sursa cu ceva, fa un brut si un generator de teste si ruleaza generatorul pana gaseste un test pe care rezultatele dau diferit la brut fata de programul bun.

[•alex_ovidiunitu]

Incercati si problema Rent de pe SPOJ (semana foarte mult).

[•coada_soricelului]

Cartile din carti se fac.

[•mateisirghe]

  pb asta e grea