Algoritmul lui Kruskal gaseste un arbore partial de cost minim. Adica un graf conex cu N noduri si N-1 muchii in care suma costurilor muchiilor este minima. Astea sunt toate conditiile care trebuie indeplinite, nu stiu de unde ai scos ca un nod trebuie sa aiba maxim 2 descendenti.

Cred ca e prea mica limita de timp la problema asta. Initial luam 50p si dupa ce am urmat sfatul lui Catalin si am inversat dimensiunile am luat 80p cu solutia oficiala.

M-am uitat pe multe surse de 100p si unele se duc in 1s pe testele 8 si 10, deci chiar asa de mult sa fi scazut limita? Diferenta de 0.7s mi se pare mult.

Ca sa fiu sigur am facut rost si de o sursa care lua 100p pe evalul vechi de la un prieten si ia tot 80p.

Sper sa rezolve cineva. Multumesc anticipat !

O solutie pe care am folosit-o eu este suprascrierea constructorului pentru Form si cand instantiezi un nou Form sa trimiti ca si parametri datele de care ai nevoie in acel form.

Nu stiu cat de corecta este aceasta abordare dpdv al design-ului OOP dar a functionat pentru mine.

Am citit in topicul de feedback pentru Runda 1 ca se foloseste un Aint 2D pentru a rezolva problema asta. Un hint va rog ?

Singura mea idee e in O(N^4). 

PS : Nu am mai auzit pana acum de Aint 2D (initial credeam ca e vorba de AIB 2D), dar mi-a spus un prieten de http://infoarena.ro/arbori-de-intervale (problema 3)

Ma ajuta si pe mine cineva? Nu ma prind ce arbori de intervale trebuie sa tin ca sa pot updata in logN tot intervalul [1..pos].

Am postat si eu ceva legat de limita de timp la Maxq in topicul problemei. Cred ca trebuie marita.

http://infoarena.ro/problema/maxq

Cred ca ar trebui marita limita de timp la problema asta. Cu solutia oficiala iau 70.

In plus, am facut rost de o sursa care lua 100p inainte de upgradarea evaluatorului si am retrimis-o si aceea ia tot 70p.  

LE : Problema SequenceQuery e aceeasi problema, dar fara update-uri si N,M<=100000 si are tot 0.6 limita de timp.
http://infoarena.ro/problema/sequencequery

Incearca sa le instalezi pe rand. Mysql, Apache si apoi PHP. Gasesti multe tutoriale pe net. 

Stie cineva daca la Unibuc se poate intra fara admitere daca ai luat locul 3 la InfoEducatie ?

Daca va place Formula 1, va rog sa dati un like :

http://www.facebook.com/pages/Formula-1-fara-comentarii-inutile-despre-MotoGP/277700858911534

Eu si un prieten incercam sa ne spunem punctul de vedere si vrem sa fim auziti, dar nu putem face asta decat cu ajutorul celor pasionati de viteza, masini, motorsport si in principal Formula1.

Vreau sa subliniez ca nu e o campanie de advertising, noi nu castigam nimic din asta, doar incercam sa imbunatatim calitatea comentariului din timpul transmisiunilor de Formula1, iar daca administratorii considera ca topicul este necorespunzator, ii rog sa il stearga.

Multumesc anticipat !

2) si 12)

Un hint ?  Nu ma prind cum sa adaptez problema rucsacului ...

Nu folosi endl ! Foloseste caracterul \n. Vezi cum iti intra in timp asa.

Cod:

...
fout<<Compute(dr)-Compute(st-1)<<"\n";
...
fout<<Binar(val)<<"\n";

Cum pot sa vad in Ubuntu cata memorie foloseste un program rulat din terminal (ma intereseaza pt programele in C++ de algoritmica) ?

Stiu ca pentru a vedea timpul de executie era comanda time.

Cod:

$ time ./executabil

Nu am gasit nimic asemanator si pentru memorie... Am gasit chestii mai complicate cu id-ul procesului, etc.

Ma intrebam daca nu este tot la fel o comanda mai usoara.

Multumesc anticipat !

[incepator]

@Sireanu Roland

Da. Sunt explicate toate. E buna daca esti incepator.

Daca stii deja C# si ai lucrat la vreun proiect nu ti-o recomand, dupa cum am spus, daca esti incepator si nu stii cu ce se mananca programarea vizuala si OOP te va ajuta mult.

PS : doar George 

Recursivitatea (functiile) lucreaza cu zona de memorie numita stiva. Ce trebuie sa stii e ca la fiecare auto apel al functiei nivelul stivei creste si pe noul nivel se aloca toate variabilele locale ale functiei (vectori, etc) si parametrii de apel. Cand rularea s-a terminat si se revine din recursivitate, se dezaloca tot de pe nivelul curent.

Ideea e ca daca ai o functie recursiva foarte "adanca", adica care se auto apeleaza de multe ori, si aloci in acea functie vectori risti sa depasesti repede memoria disponibila pentru stiva, care e in general si mult mai mica decat memoria HEAP disponibila.

Cartile alea sunt o mare porcarie, stai departe de ele. Incearca "Programarea in C# pentru liceu", editura L&S Infomat, sau daca le ai cu engleza citeste ceva de O'Reilly, alea sunt cele mai bune.

Eu am fost la un concurs recent si ca timpi orientativi ni s-a aratat ca un for

Cod:

for(int i=1; i <= 150000000; i++) { } //150.000.000

de genu asta fara alte operatii ruleaza ~ in 0.5s.

Oricum, din restrictiile problemei poti sa-ti dai seama cam de ce complexitate ai avea nevoie.

Aici : http://www.byblos.ro/search/?next=1&pg=book&isbn=9739753477

Si e la un pret bun . Stiu persoane care au dat mai mult chiar si cu 50 RON.

Eu mi-am facut comanda. Se merita, dar o am si .pdf. Daca o vrei da-mi un PM cu mailu tau.

De unde ai auzit tu asta ?

Am modificat postul, ma refeream la diametre, nu raze.

Incearca kit-ul de aici http://infoarena.ro/schimbare-borland/pachet

Multumesc !

Am implementat pana la urma solutia pe care o stiam, dar nu strica niciodata sa stii sa rezolvi o problema prin mai multe metode.

Retii razele diametrele paralele cu Ox ca segmente si sortezi punctele dupa x si in caz de egalitate dupa y. De aici faci ca la intersectia de segmente in O(logN) numai ca la introducerea si scoaterea segmentelor din structura de date (arbore echilibrat, daca vrei complexitate O(logN)) verifici pentru intersectia discurilor, nu a segmentelor. Cred ca e corect, nu am gasit o solutie oficiala la problema aia pe net, de aia am si postat.