infoarena

Aici puteţi discuta despre problema Numarare triunghiuri (http://infoarena.ro/problema/nrtri).

cum se face de 100?  :roll:

citeste articolul cu solutii de pe info.devnet.ro

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

E si mai frumos cu n^2

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

Crescatoare...   :-s

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

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.  :-k

Multumesc. :ok:

Hashing ...

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

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

Merge fara hashing, e algoritm de 5 linii.

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. :-s
Scuze de eroarea initiala.Imi cer scuze  :'(

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

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

 :oops:

Si totusi, nu modifica nimeni ... ?

Gata, am modificat.

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

Nu, pur si simplu acum am avut timp  :-' ... sorry

 ](*,)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?

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

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... :oops: :oops:

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


sper ca intelegi  :P

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
 

WOW,  :shock: :shock: am invatat ceva azi.
Multumesc mult de tot ; chiar merge  :banana: multumesc frumos inca o data pentru ajutor, momentele astea in care ne ajutam unii pe altii sunt poate cele mai minunate din toata viata noastra, a fost incredibil ce am simtit azi si acum, iti multumesc mult inca o data. sa ai bafta in continuare la olimpiade si in viata. Sa iesi pe :winner1: si sa ai grija de tine. Salut

In solutiile oficiale scrie ca trebuie sa sortam vectorul nedescrescator.......a sorta nedescrescator  nu inseamna a sorta crescator, ci doar a sorta oarecum aleatoriu astfel incat sa nu fie descrescator(iar pe cautare binara merge decat cu crescator si descrescator).....nu am dreptate?

O functie e "crescatoare" daca oricare ar fi x < y, f(x) < f(y).
O functie e "nedescrescatoare" daca oricare ar fi x < y, f(x) <= f(y).

Asa e in engleza cel putin... Se intelege destul de clar ce se vrea...

si totusi vreau si eu sa te intreb de ce in exemplu e
4
2 3 7 4   2 (care e corect)
iar explicatia e ca variantele sunt
1, 2, 4
2, 3, 4
cand acestea sunt :
2 3 7
2 4 7

Citeste mai atent.

corect :) scuzele mele :)

ma ajuta cineva si pe mine va rog cu un test mai urat sau daca binevoieste cineva sa vada sursa

http://infoarena.ro/job_detail/237622

iau doar 55, si fac ca toata lumea cu cautare binara

eu buseam la cautarea binara  :oops:... trimite-mi sursa pe prv daca vrei :peacefingers:

De unde vine betisorul de lungime 1? :-s

A. Sunt pozitii. Ar trebui specificat.  :readthis:

 Editat de moderator: Nu mai posta succesiv. Editeaza-ti mesajele precedente!

E foarte clar specificat.

cu o mica optimizare se pot scoate 100p si cu O(n^3). dar cautarea binara intra muuuult mai lejer in timp :D

Ce optimizare?

in al 3lea for, nu parcurgi vectorul pana la capat, ci pana gasesti prima valoare care nu mai respecta conditia v[ i ]+v[ j ]<=v[ k ]. pentru ca ai sortat dinainte vectorul, conditia va fi falsa si pentru toate valorile de dupa acest k. in practica folosesti un mic break.

sper ca am fost clar :D

[L.E.] Cred ca ar putea fi modificate testele astfel incat sa descurajeze folosirea smecheriei asteia :) adica conditia de care ziceam sa devina falsa spre sfarsitul vectorului, astfel incat sa nu mai conteze foarte mult la timp break-ul ala.

Cat da pentru testul :


Mie imi da 482. Scot doar 50 de puncte si nu imi dau seama ce are  :-k

539

Wait a sec, cum adica , conditia e ca a+b<=c ? pai daca a+b=c atunci inaltimea e 0 deci aria e 0 deci triunghiul nu exista. Prin urmare conditia nu ar trebui sa fie defap a+b<c ?

Exista si triunghiul cu inaltimea 0. Daca ai 3 puncte in plan, ele pot determina un triunghi; daca sunt coliniare, triunghiul format de ele are inaltimea 0.

se poate face problema fara cautare binara....

se sorteaza, eu am folosit quick-ul

cu 2 for-uri
nr=0;
   for(i=1;i<=n-2;++i)
      for(j=i+1;j<=n-1;++j)
         {
            int k=j+1;
            while(v+v[j]>=v[k] && k<=n)
               ++k;
            
         
            nr+=k-j-1;
            
         }

iei 100 pct pe asta pe cel mai mare timp am scos 64 ms, dublu fata de cautare binara:)

Mie mia iesit in O(n^3) cu 100p. Sami explice si mie cineva cum poate fi folosita cautarea binara aicea  :-' .
Deci din ce banuiesc eu.
Sortez descrescator.
for(i=0;i<n-2;i++)
for(j=i;j<n-1;j++)
si apoi caut cel mai mic si cel mare numar (prin cautare binara) care poate face trunghi cu celelate doua ?

apropo se poate cauta primul x<=val intrun hash? fara a sorta nimic? ???

Nu, hash-urile nu tin niciun fel de ordine. Pentru ceea ce ceri tu ai nevoie, ori de alta structura de date, ori de o sortare si apoi sa cauti binar!

FRATE!.....  ](*,)

In mod sigur nu gandesc bine, dar nu stiu de ce. Inegalitatea triunghiului afirma ca suma a doua laturi este mai mare ca cea de a treia. Dar de ce este suficient sa verificam daca:

if (a[k]<=a+a[j])

si nu trebuie sa luam in cnsiderare si celalate cazuri: a[j]<=a[k]+a si a[<=a[j]+a[k]. Imi scapa ceva... #-o . Ar putea cineva sa ma lamureasca si pe mine?  ](*,)


EDIT: Mi-am dat seama :)))))

mie imi merge si fara cautare binara

dupa enunt se poate forma si triunghiul 2 3 4  (4 + 3 <= 7).. e gresit enuntul sau nu inteleg eu bine?

sorry, este specificat, nu am fost atent

conditia ca sa formezi un triunghi cu laturile de lungime a,b,c nu este a+b>c? :-'

Aproape, este necesar dar nu suficient. a = 10, b = 1, c = 1. a + b > c dar aceste 3 nu pot reprezenta laturile unui triunghi.

Si in restrictii scrie ca si triunghiurile degenerate sunt acceptate (cele cu un unghi de 180 de grade si 2 de 0 grade), deci restrictia ar trebui sa fie a + b >= c.

dar corect aceasta relatie este pt toate laturile(a<b+c&&b<a+c&&c<a+b)

dar corect aceasta relatie este pt toate laturile(a<b+c&&b<a+c&&c<a+b)