168 Numarare triunghiuri

[ditzone]

Aici puteţi discuta despre problema Numarare triunghiuri.

[•spixie]

cum se face de 100?  

[u-92]

citeste articolul cu solutii de pe info.devnet.ro

[•Coty]

mie mi-a mers si cu un fel de N^3  , sa fie de la teste???
 dar mai frumos e cu cautare binara...

[ditzone]

E si mai frumos cu n^2

[•cos_min]

cum adik nedescrescatoare? nu inteleg ce vrea sa zica...

[•bogdan2412]

Crescatoare...  

[•cos_min]

10x am luat 70 cu o sol de O(n^3)

[Tabara Mihai]

Am facut O(N^3) - 75.
Am facut si cu Cautare Binara si a mers de 100.

Insa daca a facut cineva in O(N^2) as vrea sa imi explice putin ideea. 

Multumesc.

[•Marius]

Hashing ...

[Tabara Mihai]

Hashing ...

Aveam o presimtire ca se face asa.OK. multumesc.

[•Marius]

Nu e nevoie sa presimti, e nevoie sa stii ca o cautara binara o poti inlocui cu un hashing.

[•Cosmin]

Merge fara hashing, e algoritm de 5 linii.

[•peanutz]

http://infoarena.ro/problema/nrtri .. nu ar trebui sa dea exemplul 1? Eu am facut n^3, am luat 75. Si acum implementez si cautarea binara, deci daca mi-a dat pe majoritatea testelor, raspunsul 2 ar trebui sa fie gresit.

[•Tabara]

http://infoarena.ro/problema/nrtri .. nu ar trebui sa dea exemplul 1? Eu am facut n^3, am luat 75. Si acum implementez si cautarea binara, deci daca mi-a dat pe majoritatea testelor, raspunsul 2 ar trebui sa fie gresit.

Scuze...nu mai retineam ideea..
am verificat acuma cu sursa mea si e 1.( am luat 100 cu ea )

Ar trebui schimbat enuntul.
Scuze de eroarea initiala.Imi cer scuze 

[•devilkind]

exemplul e intr-adevar gresit, (2+3<6) si totusi cum de nu a observat nimeni pana akuma

[•Tabara]

exemplul e intr-adevar gresit, (2+3<6) si totusi cum de nu a observat nimeni pana akuma

Chiar asa  ??
Poate s-a schimbat intre timp din greseala...sau poate cand s-a mutat site-ul desi ma cam indoiesc ...

 

[•peanutz]

Si totusi, nu modifica nimeni ... ?

[•DITzoneC]

Gata, am modificat.

[•peanutz]

Modificarile se aplica dupa un timp? Sau cum functioneaza chestia?

[•DITzoneC]

Nu, pur si simplu acum am avut timp  ... sorry

[•Dastas]

 ](*,)Nu-mi iese nicicum cautarea binara la problema asta si ma chinui de ceva timp

Acuma am ajuns sa fac in felul urmator:
2 foruri, i=0..n-1, j=i+1..n-1 prin care fixez a si b
cautarea binara in cel de-al doilea for:
x = j+1, y = n-1;
m = (x+y)/2;
daca a[ i ]+a[j] >= a[m] atunci
x = m+1
si un contor temporar este m-j...

in afara while-ului de la cautarea binara, adun la contorul final contorul temporar... merge pe exemplul din enunt, dar pe altele intr-adevar nu.. ce gresesc?

apropo, cu hashing cum ar fi? exista vreun articol de inceput despre asta?

EDIT: am rezolvat cu cautarea binara pana la urma.. dar as fi interesat s-o fac si cu hashing, as putea citi undeva despre asta?

[•stef2n]

http://infoarena.ro/tabele-hash-scurta-prezentare
http://infoarena.ro/tabele-hash-prezentare-detaliata

[•gicurez]

Salut

Eu sunt inca la inceput am cautat pe net informatii despre cautarea binara si am gasit cate ceva; din pacate nu pot sa-mi dau seama cum sa fac exercitiul asta; am doua foruri care imi calculeaza suma a doua numere din vector si dupa accea fac o cautare binara care imi da un raspuns aproximativ ,sau daca are, unul exact; si dupa aceea calculez nr. total de triunghiuri pe care pot sa-l obtin obtinut pe baza cautarii; dar nu-mi da bine; mie pe toate testele facute de mana si cele de pe generator imi iese bine; verific cu o sursa care foloseste 3 foruri; deci tarasenia apare ori la cautarea pe care o fac ori la cum calculez nr total de triunghiuri; daca vreti pot sa postez cautarea binara pe care o fac eu sa va uitati.
Rugamintea mea era cum ar trebui sa arate cautarea binara aici si cum se calculeaza nr total de triunghiuri;
eu il fac asa: nr:=nr+c-b-1; unde b este numarul din cel de-al doilea for; si c primul nr mai mare decat suma primelor 2 nr, adica

for a:=1 to n do
   for b:=a+1 to n do
       begin
        c:=find(a+b);
        nr:=nr+c-b-1;
       end;

Unde gresec???

sunt inca la inceput si asa ca va rog sa nu va suparati daca pun intrebari stupide...

[•toni2007]

cautare binara: v:vectorul... p si u poz intre care cauti v [ i ] +v [ j ] ;

Cod:

int cautare(int p, int u)
{
  int m;
  m=(p+u)/2;
  while (p<=u){
      if ((v[m]<=v[i]+v[j] && v[m+1]>v[i]+v[j]) || (v[m]<=v[i]+v[j] && m==n-1))
		  return m;
	  else if (v[m]<=v[i]+v[j] && v[m+1]<=v[i]+v[j]) {
		  p=m+1; 
		  m=(p+u)/2;
	  }
	  else {
		  u=m-1; 
		  m=(p+u)/2;
		  }  
  }
  return 0;
}

sper ca intelegi 

aaa vectorul e de la 0 la n... daca il ai de la 1 la n pune n in loc de n-1 la primu if in while

si vezi ca tu trebuie sa ai
 

Cod:

..................................
for (i=0;i<n-2;++i)
    for (j=0;j<n-1;++j){
         caut(1,n);
    }
....................................