Este posibil ca limita de timp sa fie prea stransa pentru problema asta?

Iau TLE cu O(T), in care am:

Cod:

fscanf(in, "%d%f%d", &R, &alpha, &S);
sol = O(6 inmultiri, 2 scaderi, 1 adunare, 1 apel al functiei "sin" si 1 apel al functiei "sqrt")
fprintf(out, "%.3f\n", sol);

Presupun ca se poate parsa citirea, dar complexitatea de rezolvare mi se pare oricum neglijabila.

Ceea ce e special este ca programul se adreseaza exclusiv bobocilor.

Am uitat sa fac o precizare: anuntul este valabil si pentru studentii de anul 2 care urmeaza un ciclu de licenta de 4 ani.

In completarea a ceea ce a spus Mihai, ROSEdu a evoluat exponential fata de acum trei ani, si din punctul meu de vedere, este sursa unei fractiuni semnificative din educatia tehnica a multor studenti de la facultatea de Calculatoare.

Anul acesta am inceput sa interactionam pe teme de Open Source cu un public mult mai larg, printre care si comunitatea Infoarena (unde multi dintre noi ne-am format pe parcursul liceului si am invatat sa iubim algoritmica si programarea).

Am avut onoarea de a contribui deja la un eveniment Infoarena, s-a contribuit la site-ul Infoarena in cadrul ROSEdu Hack Days, si folosim inclusiv o clona modificata de Infoarena ca site al unei materii de anul 1 (http://elf.cs.pub.ro/programare).

Dupa cum spunea  si Traian, atunci cand se investeste in consolidare si in educatie, rezultatele pe termen lung intrec asteptarile. Iar atata timp cat avem mai multe idei bune decat timp sa le punem in practica, stim ca suntem pe drumul cel bun.

Toti urmarim sa ne maximizam fericirea in viata, la urma urmei. De aici ar trebui sa porneasca raspunsul.

De exemplu, pentru mine (si foarte multi dintre noi, din discutiile pe care le mai purtam) cel mai important ar fi sa fac ceva cu adevarat fascinant, nu ceva "tehnologic". Mai putin ar conta cati bani primesc, in anumite limite (vreau totusi o viata decenta).

Raman foarte _foarte_ dezamagit cand aplic undeva la un internship si mi se ofera un proiect caruia eu nu ii vad rostul si in care sa codez ca o maimuta niste chestii la care nu le pot vedea utilitatea pragmatica. Fiind doar un internship, accept, dar daca ar fi un job full-time, as simti ca trece viata pe langa mine.

Chiar recent mi-a spus cineva ca "nu primim decat doctoranzi la un astfel de proiect" dupa ce mi-am trecut preferintele acolo. Din punctul asta de vedere, fericit cu adevarat pe termen scurt n-as putea fi decat in facultate (dar una [mai] normala, nu una care imi suge energia cu porcarii). Peste cativa ani s-ar putea sa imi schimb parerea.

In schimb, pentru cineva care vrea provocarile unui mediu real, doar un job i-ar putea oferi ceea ce isi doreste el cu adevarat.

E ceva ce nu inteleg la testul 2 din enunt.

In total, in joc sunt 13 bile.
De asemenea, suma capacitatilor buzunatelor celor 4 prieteni este 13.

Dar pentru x=0, inseamna ca prietenul 0 extrage 0 bile din urma 0 => in urna raman 2 bile.
Singurul prieten care mai poate extrage din urna 0 este prietenul 3, dar el are capacitatea buzunarelor de 1 bila => se iroseste o bila.
Raspunsul din exemplu pt x=0 este 13.

E o greseala sau nu am inteles textul?

Subsirurile au intelesul clasic? (adica sunt formate din caractere care in sirul initial sunt plasate pe pozitii crescatoare?)

Cred ca exemplul este destul de neconcludent. Eu am luat 0 la concurs pentru ca in cazul in care costul nou este mai mare decat cel vechi, afisam un numar negativ (si ar fi trebuit sa afisez 0).

Din fraza "cu cât s-ar îmbunătăţii suma timpilor necesari" nu reiese neaparat ca aceasta cantitate trebuie sa fie mai mare sau egala cu 0 si apar probleme de interpretare. Nu stiu daca au mai avut si altii problema asta, dar oricum... s-ar putea modifica enuntul.

Nu pot sa prind testul cu "Imposibil." sub nici o forma 

Am presupus ca X!=autor in propozitiile de forma

Cod:

A: X este {divin | om |malefic}.

, dar nu a facut nici o diferenta... neglijez punctele de la sfarsitul propozitiilor (in fisierul de intrare, pe ultima linie, lipseste)... practic am verificat fiecare caz de propozitie...

Ah, si ar trebui de mentionat undeva ca liniile se termina cu terminator de Windows si nu de Unix...

Totusi, am o nelamurire in legatura cu solutia oficiala. Fie urmatorul set de date de intrare:

1
5 6
1 2
1 3
1 4
2 5
3 5
4 5

Conform ideii de rezolvare descrisa acolo... acest graf ar trebui sa fie un arbore de cicluri, dar din enuntul problemei eu inteleg ca nu este (pentru ca doua cicluri trebuie sa aiba in comun o singura muchie si doua noduri, iar in cazul de fata e vorba de 2 muchii si 3 noduri). 

I'm confused, solutia ar trebui sa dea YES sau NO? 

Hai sa luam exemplul asta:

---ec1: 8x^2+35x+12=0
1.(-8x-3)(x-4)
2.(-x-4)(-8x-3)
3.(x+4)(8x+3)
4.(8x+3)(x+4)

De ce nu figureaza si (-8x-3)(-x+4) printre solutii?
E adevarat ca are aceeasi ordine de sortare ca si (-8x-3)(x-4), dar sirurile nu sunt identice.
In cazul asta:
-1 -2 -1 2 mie imi da (x+1)(-x-1), dar o alta posibilitate e si (x+1)(x+1)...
daca trimit sursa cum am facut eu busesc anumite teste, cu a doua varianta le busesc pe altele

Oricum as face, nu pot trece testul 7 si pace. Nu inteleg ce are special... am verificat codul de vreo 10 ori in ultima ora, cap-coada si nu vad nimic suspect, nici un cast, nimic :-<

Nu numai la genul ala de moda m-am referit. In primul rand, daca faci un poll "rock vs manele", evident, vrei sa aduci in evidenta ca marea majoritatea dintre noi asculta rock si nu manele (conform realitatii, asa e). Si observand rezultatele (sau inainte de a le observa) si avand in vedere ca suntem oameni cat de cat destepti, poti sa tragi concluzia [empirica] ca oamenii destepti asculta rock. Si de aici se creeaza ideea [gresita] ca rock-ul ar fi superior ca gen muzical. Si de aici pana la a te lauda [voit sau nu] ca asculti "rock adevarat" si "rock clasic, cum era pe timpuri" devine echivalent cu a te crede superior. Iar asta e un tip de moda. Daca nu ar fi o forma de moda, nu te-ai obosi sa scoti in evidenta ca tu asculti X si Y, nu?

Cei mai multi dintre noi pur si simplu au raspuns la topic. Unii insa s-au apucat as critice un gen sau altul, sau sa spuna cat de elevati sunt ei pentru ca asculta X (rock, in cazul nostru).

Pentru asta am scris ce era cu BOLD mai sus. Nu m-am referit ad literam la un juramant de tacere cand am zis sa nu mai spui la nimeni ce asculti.

E ca si cu aia care sustin ca muzica clasica va fi mereu cea mai valoroasa.

Momentan e.

Esti sigur ca nu am ascultat niciodata Led Zeppelin si Deep Purple (wrong), si la fel de sigur ca daca as asculta, mi-ar place.

Ai dreptate, nu toata lumea intelege muzica buna.

Si asta imi demonstreaza perfect cele zise. Jignesti (nu numai pe mine, pe toti care asculta altceva) pentru ca ai un complex de superioritate. Si chestia asta s-a mai intamplat de la inceputul topicului, asa cum am subliniat si in primul post.

Si ca sa raspund si la faza cu "de ce m-am lasat", am facut-o pentru ca am realizat ca mesajul nu corespunde cu atitudinea mea fata de viata. N-am fost asa de disperat cat sa ma imbrac bizar.

E ca si cum ai pune pe Tiesto, Britney Spears si 50 Cent la un loc...

Si care e problema?

Pai, tie nu iti place sa ii pui pe Pink Floyd si Marylin Manson la un loc, nu??

Si faza cu rock-ul... daca nu ar fi la moda nu stiu la cati ar place. Eu ascultam intensiv rock pana acum vreo 2-3 ani si m-am lasat incetul cu incetul, nu mai ascult decat Undertaker. Aici e vorba de chestia aia cu linistea... you know... Daca asculti doar ca sa porti tricouri nengre imprimate in graba si bocanci/tenisi negri, mai bine te lasi.

Nu vreau sa te simti jignit, insa tu nu ai nici cel mai mic habar despre ceea ce inseamna rock. Nu e la moda sa asculti rock, era la moda acum 30 de ani. "Rockerii" din ziua de azi care poarta bocanci cand sunt 50 de grade afara sau considera cool sa isi taie venele in marea majoritate a cazurilor nu sunt nimic altceva decat niste copii frustrati care se manifesta intr-un mod mai putin obisnuit si respingator pentru multi la prima vedere. Te rog nu mai asocia marele nume al rock-ului cu ceea ce se intampla in ziua de azi. Asculta formatii gen Led Zeppelin, Deep Purple sau Queen si spune-mi ce crezi.

Ba da, vrei... E ca si cu aia care sustin ca muzica clasica va fi mereu cea mai valoroasa. Daca omului nu ii place un gen, ii spui ca nu stie ce inseamna genul respectiv sau ca nu are gusturi.

Esti sigur ca nu am ascultat niciodata Led Zeppelin si Deep Purple (wrong), si la fel de sigur ca daca as asculta, mi-ar place. Tu de fapt spui ca nu stiu ce imi place si ce nu, si asta e jignitor. Eu ii respect pe cei care asculta alt fel de muzica (atata timp cat au casti si nu ma obliga si pe mine sa ascult) si nu le spun ca sunt inculti daca nu le place muzica mea.

Si acuma... 

Eu am facut O(NlogN) si am luat 100, dar ma intrebam... SIGUR nu se poate O(N)? Era problema aia... camion sau cum se numea... de la campion, in care se intampla ceva asemanator, doar ca lua operatiile in ordine inversa. 

[Testul suprem despre daca iti place sau nu un gen de muzica este sa te straduiesti sa nu mai spui la nimeni ce gen de muzica iti place. Atunci, daca nu mai apare tentatia de a te lauda, o sa fii mai multumit si mai sincer cu tine insuti...]

Dj Tiesto, Armin van Buuren, ATB, Schiller, Deep Dish, Iio, Delerium, Andain, Gigi D'Agostino, Paul van Dyk   nu am vazut deloc! 

Nu asculta nimeni house sau trance ? 

Eu ascult 99% trance: Dj Tiesto, Paul van Dyk, Marcel Woods, Dj Optik (cel mai bun roman dj, dupa mine), Faithless, van Buuren, Pulsedriver, Dj Zex, Delirium, Merlin, East Clubbers, Dj Eco, Emax, ATB,... etc si sute de piese de la cine stie ce Dj care mi s-au parut bune.

Imi place trance pentru ca imi iti da o liniste interioara in noptile lungi pe care nici un alt fel de melodii nu reuseste sa mi-o ofere.

Oricum, sunt de parere ca topicul asta e gresit gandit, pentru ca Altele ala minimalizeaza celelalte genuri. E ca si cum ai pune pe Tiesto, Britney Spears si 50 Cent la un loc...

Astfel, banuiesc ca scopul topicului este condamnarea manelelor. Si faza cu rock-ul... daca nu ar fi la moda nu stiu la cati ar place. Eu ascultam intensiv rock pana acum vreo 2-3 ani si m-am lasat incetul cu incetul, nu mai ascult decat Undertaker. Aici e vorba de chestia aia cu linistea... you know... Daca asculti doar ca sa porti tricouri nengre imprimate in graba si bocanci/tenisi negri, mai bine te lasi.

Testul suprem despre daca iti place sau nu un gen de muzica este sa te straduiesti sa nu mai spui la nimeni ce gen de muzica iti place. Atunci, daca nu mai apare tentatia de a te lauda, o sa fii mai multumit si mai sincer cu tine insuti...

Daca e prea multa filozofie, ma scuzati, tocmai am citit povestiri Zen.

Ms. Scuze ca am postat acolo, am ajuns la pagina prin search si credeam ca e din arihva, nu am fost atent.

Pai, nu stiu ce poate sa aiba sursa, ca am dat diverse cazuri si a mers pe toate  ... plus ca merge pe primele 24.
Ma gandeam ca daca imi dati un test asemanator cu ultimul test o sa imi dau seama...
La urma urmei e un flux clasic (dupa ce dublez nodurile). Toate capacitatile sunt [stiti voi], cu exceptia sursa->sursa' si destinatie->destinatie' care sunt infinite, pentru ca sursa si destinatia pot fi fol. de oricate ori.

Iau WA pe ultimul test si nu pot sa imi dau seama de ce  (dublez nodurile)...

Ce e special la el?

Pe testul de mai sus imi da bine (adica 1)

Very useful stuff. Thanks a LOT, guys.
Am auzit si eu de treap dar nu am facut sapaturi pentru ca nu credeam ca o sa fie util. Acuma ca mi-ati spus voi, ma pun sa il citesc calumea la noapte. 

[puternic]

O alta problema la implementarea cu vectori este ca spre deosebire de heap, de exemplu, arborele nu este compact. Altfel spus, e posibil ca A[10] sa reprezinte un nod de arbore, iar A[9] sa nu existe. Si te costa in plus sa tii minte nodurile existente, oricum.

Eu folosesc alocare dinamica mereu. Stiu ca e mai lent lucrul cu pointeri, dar dupa mine, apar mai putine erori dupa ce te inveti. Pentru un arbore binar, fac asa:

typedef struct NOD {INFORMATIE a; NOD *stga,*drta;};

unde INFORMATIE e un tip de date (poate fi si int). Deasemenea, recomand puternic cand lucrezi cu alocare dinamica sa faci functii speciale pentru acces la structura. De exemplu, insert(x); delete (x);, etc...

Daca ai timp, cel mai bine e sa faci clase, dar merge si cu functii clasice, in mod special la concursuri unde nu ai timp.

Si nu uita, "NOD *a;" nu inseamna ca ai memorie alocata pentru a.

Deschid topicul asta pentru ca m-am lovit de o dificultate de implementare. Am gasit recent o problema la care am nevoie de arbori de cautare - echilibrati.

Am citit vreo 2 zile si am invatat despre arbori AVL, dar lipseste un amanunt de implementare si m-am blocat. Mai exact, nu stiu cum sa reactualizez factorul ala de echilibru pe masura ce rotesc subarborii. O idee era sa pastrez si inaltimile, dar mi se pare destul de grotesc si implementarea din care m-am inspirat nu folosea inaltimile, ci doar factori de echilibru. (bibliografia mea se compune majoritar din cartea lui Ioan Maxim, "Arbori")

Cat despre arbori bicolori, nu am inteles nimic. Mi se pare tare naspa implementarea si m-a speriat cu totul.

Din cate am vazut, sunt gata implementati arbori echilibrati in STL, dar eu nu stiu sa folosesc STL si ma oftic tare... 

Ma poate ajuta cineva cu detalii de implementare la AVL? Teoretic stiu, dar nu stiu cum sa implementez practic.

P.S. chiar daca invat sa folosesc STL, tot vreau sa stiu sa implementez si manual, ca imi ofera pace sufleteasca 

Eu m-am chinuit mult la problema asta. Intr-adevar, testele nu sunt chiar bine construite si luam 90 cu o sursa gresita.

Uite un test pe care sa il dati in caz ca primiti WA...
.IN
1 3 1 3 7 2 1 1 1 1 1 1

.OUT:
1
1
6

[long]

ok cred cas batut in cap. Primesc pentru doua teste "RUN ERROR - Invalid memory reference", desi am declarat toti indicii si chiar toate variabilele long.  NU ma prind ... poate exista teste si cu siruri mai lungi de  1.000.000 

Am dat acuma de curiozitate lmax = 10.000.000 si merge ... ciudat 

Pentru cei care scriu surse in C:
Nu uitati cand declarati siruri de caractere ca sirurile se termina cu '\0' (sau NULL). Asta inseamna ca daca sirul are N caractere, trebuiesc memorate N+1. Eu imi mai iau din cand in cand cate o tzeapa din asta.

Pai in primul rand, testul lui Marius nu e bun  . (ala, primul... cu muchiile de cost 1). De ce? Pentru ca orice drum intre 1 si X e minim (orice produs e 1, sau altfel spus, orice suma de logaritmi e 0).
De altfel spune si in enunt, ca dimensiunile sunt intre 2 si 10^9.

Raspunsul ar fi
5 6 4 4                        - daca drumurile sunt elementare
infinit infinit infinit infinit - daca drumurile nu sunt elementare

Nu scrie nicaieri daca drumurile sunt sau nu elementare, pentru ca reiese din conditia de drum minim (din nou, daca costul fiecarei muchii >1)

Cat despre precizie... sa ma dau cu capul de pereti, nu alta   

  S-a dus metoda mea. Si totusi parea sa verifice pana la o bucata...

Faceam cu partitiile lui n, si pentru fiecare partitie adunam la total un numar care depindea de configuratia partitiei... (combinari, dar se reduce la un raport de factoriale...).

Dai un hint? 

De curiozitate, pentru 9 da 25788?

Am observat si eu, sorry, my fault. 
Mi s-a busit Mozilla si l-am reinstalat.