Is the file in binary or text format ? It wouldn't be that hard to interchange between them but I am curious.

LE: I'm thinking that with the binary format you could seek in that file, this enables you to even transpose it in place,
without even using any significant memory or extra disk space for even larger files. But this is slow due to all those disk read/write/seek operations.

Eu am facut asa :

Fie A1 originea, A1B1 axa Ox, A1A2 Oy si A1D1 Oz.
Cele doua drepte pot fi caracterizate astfel :

L1 : Contine punctul (0, 1, 0) si are directia u1 (1 , -1 , 0);
L2 : Contine punctul (0, 0, 0) si are directia u2(0, 1, 1);

Fie P punct pe dreapta L1 si Q punct pe dreapta L2;
P are coordantele(t, 1 - t, 0) iar
Q are coordonatele(0 , s, s) , s, t din R;

Pentru ca lungimea lui PQ sa fie distanta dintre cele doua drepte
trebuie sa avem ca PQ dot u1 sa fie 0 (produs scalar) , si PQ dot u2 sa fie 0;

Avem PQ = ( -t, s + t - 1, s)
PQ dot u1 = 0 <=> 2t + s = 1;
PQ dot u2 = 0 <=> 2s + t = 1;

rezolvand sistemul obtinem t = 1/3 si s = 1/3;
Inlocuind ajungem la PQ = (-1/3, -1/3, 1/3) = 1/3 * ( -1, -1, 1);
Deci |PQ| = 1/3 * sqrt(1 + 1 + 1) = sqrt(3)/3;

Cum ati calculat sqrt(2)/2 ? Mie tot sqrt(3)/3 imi da.

Sursa http://www.infoarena.ro/job_detail/989978 cu Set de la indicatii ce ar trebui sa obtina 80 de puncte acum scoate 90-100 la limita.
Si de mentionat ca o imbunatatire ar fi eliminarea intrarii din set si inserarea unei intrari noi atunci cand actualizam distanta unui nod.

Noii timpi obtinuti : http://www.infoarena.ro/job_detail/989976

Incerc de ceva timp sa ma prind unde am gresit la implementare si nu imi dau seama

Cat tre sa dea pe :

Cod:

9 45
9 9
9 8
9 7
9 6
9 5
9 4
9 3
9 2
9 1
8 8
8 7
8 6
8 5
8 4
8 3
8 2
8 1
7 7
7 6
7 5
7 4
7 3
7 2
7 1
6 6
6 5
6 4
6 3
6 2
6 1
5 5
5 4
5 3
5 2
5 1
4 4
4 3
4 2
4 1
3 3
3 2
3 1
2 1 
1 4
5 8

si pe :

Cod:

9 43
9 9
9 8
9 7
9 6
9 5
9 4
9 3
9 2
9 1
8 8
8 7
8 6
8 5
8 4
8 3
8 2
8 1
7 7
7 6
7 5
7 4
7 3
7 2
7 1
6 6
6 5
6 4
6 3
6 2
6 1
5 5
5 4
5 3
5 2
5 1
4 4
4 3
4 2
4 1
3 3
3 2
3 1
2 1 

Ar trebui sa dea 10 si 8  nu?

Nici in cazul in care se opteaza pentru algorimul lui Tarjan nu e necesara sortarea topologica.

2. isn't it T(N) = 3 * T(N/2) ?
at each step u eliminate 1 out of 4 ?

LE: O(N^(log(2,3)))

Eu zic asa:
-Schimba <fstream.h> in <fstream> si scrie dupa using namespace std;.
-Declara variabilele tale ca fiind locale si nu globale.

Nu se mai posteaza solutia? a trecut o luna

Este prima data cand doresc sa trimit o solutie la problema saptamanii, si nu stiu exact sub ce forma se trimit solutiile. Pseudocod cu explicatii sau implementarea propriu-zisa C++ ?

atunci cand tii unul pair faci o singura inserare pe muchie si nu doua ma gandesc eu.

Inserarea unui element intr-un vector merge in timp liniar.
Si daca vrem sa inseram elementele ce fac parte din M in N atunci vine N*M nu?
Cum stim ca vectorii sunt deja sortati la o singura parcurgere a lui N si M inserari e gata.
Si in cazu asta vine N+N*M care e mai putin decat (N+M)^2 si cu Memorie O(1).
Se incadreaza? sau gresesc la rationament?
[LE]: ca sa fie mai clar: cand zic inserare...  ma refer la asezarea lui pe pozitia finala, pt ca practic elementele sunt deja in vector si trebuie doar sa "dam mai incolo" cu o pozitie elementele, sa aiba loc cel care trebuie asezat, "dand mai incolo" suprascriem pozitia originala iar in golul lasat copiem dintr-un aux .

deci faptu ca retineam graful sub forma a doi vectori manca timpu.. si daca folosesc unul singur cu pair<> se rezolva.. multumesc mult pt timpu acordat
[LE] si partea cu numarul de aparitii pe care ai mentionat-o , din cate stiu n-am folosit nimic de genul acesta ... dar oricum.. acea modificare.. din 2 vectori cu unu pair... a rezolvat problema:D multumesc
[LE].. ahh am inteles . dar acea chestie care zici ca numara aparitiile era folosit p postul de un vector true false, desi era declarat int... era ceva memorie irosita ce-i drept.. dar l-am schimbat in unul bool

aha... am sa incerc... ma gandeam ca motivu pt care pierd ceva timp e ca.. in bellman folosesc coada in stl.. in loc sa o implementez eu... iar in ambele cazuri.. reprezentarea grafului sub forma de vectori in stl.. si ma gandesc ca poate.. o reprezentare dinamica cu liste de adiacenta ar fi mai rapida

Am scris un Dijkstra normal, am luat 50 de puncte.
Am incercat apoi un Dijkstra cu heapuri, iese din timp la ultimul test si iau 90, iar in final cu un bellman cu coada si acelasi rezultat, iese din timp la ultimul test.
Probabil implementarea mea cu heapuri nu e optima.
Poate cineva sa arunce o privire si sa-mi dea un sfat?
[LE]
Am inteles unde gresesc la bellman, eu inserez nodul chiar daca este deja in coada,
dar la dijktra cu heapuri tot am intrebari.

multumesc sa vad daca merge.

L.E.: asta era. multumesc. de acum am sa stiu.

L.L.E.: dar mai am de lucrat cu totientu... acolo am o buba... am gresit la rationament putin si mai trebe si optimizata...

Editat de admin: Nu mai posta consecutiv, foloseste butonul modifica.

am facut o sursa care imi rezolva bine problema.
am folosit eratostene si totient. numai ca imi da o eroare de compilare p care eu nu stiu sa o rezolv.
complilatoru folosit de mine e cel borland m-am obisnuit cu cateva diferente dintre cele doua si m-am adaptat, dar p asta nu o mai stiu.

invalid types 'int [10001][double]' for array subscript

si nu am declarat nimic double. toate variabilele care lucrez sunt declarate long sau int. am o secventa de cod unde fac o impartire dar rezultatu impartirii este int cu siguranta. borlandu nu imi da eroare... gnu c++ imi da:( ajutor