Mie-mi crapa sort-ul din stl?!? Desi i-am dat domeniul de sortare corect? Crapa in STL.

Se poate face si arbore partial de cost maxim tot asa? (de ex la Kruskal sortezi descrescator in loc de crescator)

Dar nu putem sa legam de tata nu doar la interogari, ci si la reuniuni (chiar daca radacina se schimba pe urma), ca scurteaza drumul? Oricand parcurgem sa gasim radacina?

Si oricum, iei 100 si fara prima euristica. Adica conteaza atat de mult? Pentru ca oricum cand legi direct de radacina
scurtezi f mult drumul si ce conteaza adancimea unei grupe din moment ce la la prima parcurgere o faci 1?

Bulina portocalie o au adminii.
Userii normali au buline verzi, galbene sau rosii.

Cam ciudat alese culorile. Ca ai zice ca rosu e mai mult ca portocaliu.

Ati putea sa mutati restictiile problemei intr-o categorie separata ca la restul problemelor. Asa nu e acelasi stil.

________________________________________________________

pot sa fie oricate cifre de 0, mai putin prima din numar. trebuie sa nu ai o subsecventa de lungime P cu cifre de 0.

fara numere mari iei 65 de puncte.

http://infoarena.ro/job_detail/558926
Eu iau 80 fara numere mari. Cred ca s-au schimbat intre timp testele asa ca am postat aici cat iei acum.

Dar dc oare s-au pus restrictiile sa-ti trebuiasca numere mari? Adica 20^20 are doar 8-9 cifre in plus fata de cat iti incape pe long long. Ar fi incaput pe long long long...  daca exista.

[i]

Nu e din cauza ca numarul de intoarceri e prea mic. E din cauza ca fiecare numar va fi procesat o singura data. Algoritmul e echivalent cu urmatorul algoritm. Trec prin fiecare element in parte si il adaug intr-o stiva. Vreau sa mentin acea stiva sortata descrescator, astfel ca daca elementul din varful stivei e mai mic decat elementul pe care vreau sa il bag acuma incep sa scot din stiva pana cand in varful stivei ramane un element mai mare. In acest moment elementul din varful stivei este de altfel si primul element din stanga mai mare decat el (pentru dreapta faci la fel). De ce e acest lucru O(N). Simplu, pentru ca fiecare element intra in stiva o singura, si iese o singura data. E drept ca poate parea mai mult din cauza ca la fiecare pas trebuie sa mai si scoti niste elemente din stiva, insa gandestete ca suma numarului de elemente pe care le scoti e N.

Da, pentru ca tu atunci cand calculezi "zidul" (pana unde vede) pentru un anumit turn (turnul i), desi treci prin puncte intermediare pana ajungi la rezultat, nu vei mai trece din nou prin punctele intermediare pentru turnurile viitoare (de dupa i) pentru ca un turn viitor fie va "vedea" complet intervalul dintre zidul lui i si i, fie nu-l va vedea deloc (fiind blocat de turnul i). Deci tot acest interval dintre i si zidul sau va fi rezumat pe viitor doar consultand turnul i.

Fiecare turn va mai fi consultat o singura data (de zidul sau din partea opusa). Cand facem parcurgerea uitandu-ne spre stanga pt vizibilitate la turnul i, acest turn va fi dupa aceea "subordonat" zidului sau din dreapta k, i va fi folosit de catre k pt a i se calcula vizibilitatea si apoi nu va mai fi consultat i. Va fi consultat k cat si pentru i.

Problema se numeste camera de la faptul ca obiectul din camera este o camera sau de la faptul ca locul unde se afla camera este intr-o camera? Sau ambele?

Tu faci post hunting ?

Nu. Era o gluma. Oricum, nu mi-ai raspuns la intrebare. Eram curios.

Lasa debugger-ul,,, Invata sa debuggezi cu printf-uri.

e mai productiv cu debugger decat cu printf
lucreaza in MinGW?

Ms. Am gasit problema. Se pare ca / nu tine cont de semn.

_______________________________

Am completat eu articolul cu solutii cu ce am stiut.

http://infoarena.ro/algoritmiada-2011/runda-2/solutii

Daca folosim algoritmi mai performanti de inmultire a matricilor putem obtine timpi mai buni, in particular cu algoritmul lui Strassen obtinem o complexitate de O ( K * N ^ 2.807 + Q ) , dar niciunul dintre acesti algoritmi nu obtine punctaj maxim.

Dc e algoritm performant daca are complexitate N ^ 2.807 (si ceva)?

Faza cu ++i, i++ conteaza de la caz la caz. Daca ai V[++i] sau V[i++] sunt doua lucruri diferite. Si in for, nu conteaza cum il scrii, fiecare cum s-a obisnuit. Streamurile in general merg mai repede, pentru ca sunt mai noi si s-au dezolvata mai bine ca si printf, dar uneori citirea din c face minuni. Si da, "%d" e mai rapid ca si "%i" pentru ca formatul "%d" e mai nou.

Stiu ca v[++i] sau v[i++] sunt doua chestii diferite.

Atata timp cat implementezi calumea nu ar trebui sa fie problema detalii de genul.

http://infoarena.ro/job_detail/547479
http://infoarena.ro/job_detail/547484
Pe infoarena iau 60 cu %i si 100 cu %d.

Se pare ca unele teste sunt mai rapide cu %i, altele cu %d. Iar unul dintre ele iese de tot din timp la %i.

Au mai fost unele de 90 cu scanf si 100 cu streamuri.
Poate ar trebui marite un pic limitele, nu stiu.
Oricum, daca zici ca la olimpiada nu conteaza e bine. Poate sunt mai mari limitele.

Daca stochezi vectori intr-o functie recursiva (e necesar la o problema), memoria aceea se elibereaza dupa ce termina executia acea instanta a functiei?
Mai mult, daca s-a terminat de evaluat o linie de cod in care s-a folosit parametrul intors de functie, si s-a zicem functia intorcea adresa unui vector, vectorul se elibereaza?
Ca eu stiam ca C++ nu are garbage collector si ma gandeam daca asa obtii memory leaks.

Traiasca familia! Mi-a iesit  
Am uitat ca in operatiile cu module poate da valoare negativa  

Poti sa fii mai explicit? Adica tocmai pt ca % respecta semnul, cu ce mai trebuie sa fii tu atent?

Problema se numeste camera de la faptul ca obiectul din camera este o camera sau de la faptul ca locul unde se afla camera este intr-o camera? Sau ambele?

Ce indica bulina colorata legata de rating?
Ca am vazut oameni cu bulina rosie cu rating mai mic decat altii cu bulina portocalie.
Pana si evaluatorul infoarena cu rating 0 are bulina portocalie.

Din cauza citirii, tu ai "%i", ceea ce se folosea mai demult in borland ( daca nu ma insel ) . Incearca sa folosesti "%d", si o sa mearga, si la rezultat sa folosesti "%lld", uite aici sursa ta : http://infoarena.ro/job_detail/546327
[LE] Totusi "%i" cred ca mergea, greseala fatala era la rezultat, trebuie "%lld" ..... dar folosesti "%d" mai bine alte dati

Mersi

Dar cred ca fiindca lipsea ll-ul de la format.
http://cplusplus.com/reference/clibrary/cstdio/printf/
Scrie acolo d or i pt Signed decimal integer.
Mie-mi place mai mult cu i.

_________________________________
http://infoarena.ro/job_detail/547479
http://infoarena.ro/job_detail/547484

Se pare ca e mai lent cu %i.
din ce am inteles pana cum
++i mai rapid ca i++
%d mai rapid ca %i
max-ul de mana mai rapid decat cel din stl
streamuri mai rapide pe infoarena, scanf si printf mai rapide pe campion si la olimpiada.

70 cu cstdio
100 cu streamuri

Cu ce difera sursa mea (http://infoarena.ro/job_detail/546312?action=view-source) cu cea a lui Rares
(http://infoarena.ro/job_detail/545858?action=view-source).
Mi-am modificat sursa pana a ajuns aproape identica. Dc iau 25 si el 100?

"trebuie determinata distanta intre satele X si Y, daca acest lucru este posibil."
"Intotdeauna va putea fi determinata distanta dintre X si Y pe baza informatiilor primite"

?

Cum se citesc numerele din fisierul de iesire la evaluare?
Ca am vazut ca daca afisezi cu format " %i" in loc de "%i ", iei 0 in loc de 100.
Adica daca erau string-uri era clar ca conta. Dar vad ca si la numere conteaza daca afisezi un spatiu in fata.

Si ce e de preferat cand lucrezi cu cozi?
deque sau queue?

Mie-mi scrie la "scorul tau in arhiva" N/A desi am ultima sursa trimisa are 100 de puncte.

Dar de ce raspunsul e 0 la a doua? Nu sunt bune
3.1123
3.1124
3.1125
ca secvanta crescatoare si
3.1126
ca secventa descrescatoare?

____________

never mind. Am luat 100. Vad ca secventa descrescatoare trebuie sa inceapa descrescator fata de cea crescatoare.

Ai inf pe double, e util daca vrei sa sortezi dupa tangenta de exemplu. Cred ca daca incerci atan(pi/2) obtii asta. Functioneaza compararea bine, nu sunt sigur insa in priviinta operatiilor.

si daca pe urma aduni 100 sau scazi 100, ramane INF?
Si daca inmultesti cu -1, ajunge -INF?

Am observat de ceva timp o diferenta mare in ceea ce priveste operatiile din C# vs C++.

La overflow, variabilele din C++ intra pe numere negative, in timp ce cele din C# iau valoarea unei constante ce reprezinta infinit.
Si de aici toate operatiile de fac corect.
INF + const = INF
INF - const = INF
INF * (-1) = -INF

la nedeterminari inca n-am incercat sa vad ce face, dar mi se pare o chestie destul de utila pt proiectele mai mari.

Oare operatiile sunt incetinite mult din cauza asta? Stiu ca in C++, nr ies negative pt ca asta obtii daca aplici operatiile, in C# or fi ceva if-uri in cadrul operatiilor ca sa puna valoarea INF?