841 Bete2

[•astronomy]

Aici puteti discuta despre problema Bete2.

[•AnDrEwBoY]

O idee pentru a obtine 100 puncte?!

[•Marius]

O idee pentru a obtine 100 puncte?!

Căutare binară.

[•Florian]

Se poate mai rapid de O(N^2 * logN ) ?   

[•AnDrEwBoY]

Multumesc!

[•Marius]

Se poate mai rapid de O(N^2 * logN ) ?   

O(N²) cu hashuri.

[•CezarMocan]

Se poate O(N^2) si fara hashuri. Sortezi sirul si incerci sa obtii elementul i ca suma a 2 numere dinaintea lui din sirul sortat (asta se poate face cu 2 indici, unul porneste de la 1 spre i si celalalt de la i spre 1).

L.E. Nu's foarte sigur ca e corecta, dar testata cu brutul a mers pe vreo 2000 de teste...

[•AnDrEwBoY]

Si nu e O(N^3)?
Ai O(N) pentru a lua fiecare numar in parte si O(N^2) pentru a verifica daca se poate forma cu 2 numere dinainte sa.Cu rezolvarea asta obtii 40 puncte.

[•CezarMocan]

Nu e O(N^3) pentru ca tu cu fiecare din cei 2 indici pargurgi portiunea 1..i pana se intalnesc (adica maxim i operatii in total).

[•AnDrEwBoY]

Cod:

    sort(0,n-1);
    
    for(i = n-1; i >= 0; i--)
    {
        t = nr[i];
        for(j = i-1; j >= 0; j--)
        {
              for(k = 0; k < j; k++)
               if(nr[j]+nr[k]==t) { total++; break;}
        }   
    }
    
    printf("%d",total);

Asa?Daca da,cu solutia aceasta vei lua doar 40 puncte.

[•Florian]

Nu asa. 

sortare sir;

for(i=1;i<=n;++i)
{
  p = 1; k=i;
  cat timp(p != k) { prelucrare in o(1); ++p; --k; }
}

Ceva in genul asta. 

[•Bogdan_tmm]

sal... cum poti sa estimezi care e cea mai "eficienta" dimensiune pt un hash?
DIM              timp
984437         552ms
4342            208ms
2333            236ms
371              308ms
din cate vad valoarea optima aici e de 3000-5000(banuiesc,ca nu mai bagai si altele)...
Cum as putea aproxima asta in functie de datele de intrare(normal ca depinde si de teste,dar asa in mare...)

[•rares192]

Am facut sortare rapida si m-am gandit sa aplic cautarea binara dar obtin doar 40 de puncte deoarece pe celelalte 6 teste obtin raspuns incorect.
Ma ajutati va rog in depistarea greselii mele ?

//quicksort 

Cod:

 x=0;
   for(i=2; i<n; i++)
	{
	for(k=i-1; k>=0; k--)
		if(a[k]+a[k]>=a[i])
		{

		        st=0;
			dr=k;

		       int mij1=-3200;

			while(st<dr)
			{
			mij=(st+dr)/2;

			if(mij==mij1) break;

			if(a[i]-a[k]==a[mij])
                        x++;

		        else
			if(a[mij]>a[i]-a[k])
			dr=mij;
			else
			st=mij;
			mij1=mij;

			}
           }
}

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•codrin]

 e ceva mai special la primele 4 teste??
ca iau WA si chiar nu stiu ce gresesc 

Cod:

sort(a,a+n); 

for(i=0;i<n;i++)
    {
	p=1;
	k=i;
	while(p<k)
	    {
		if(a[i]==(a[p]+a[k]))
		    {
			contor++;
			p++;
			k--;
			if(p>=k)
				break;
		    }
		else
		    {
			if(a[i]>(a[p]+a[k]))
				p++;
			else if(a[i]<(a[p]+a[k]))
				k--;
		    }
	    }
    }

[•miculprogramator]

Ma poate ajuta cineva cu ( , ) cautarea binara ? 

Cod:

    for (i=0;i<N-1;i++)
        for (j=i+1;j<N;j++)
        {
        st=i;
        dr=j;
        while (st<=dr)
              {
              mij=(st+dr)/2;
              if (v[mij]==v[i]+v[j]) nr++;
                 else if (v[mij]<=v[i]+v[j]) st=mij+1;
                      else dr=mij;
              }
        }

[•sima_cotizo]

Probabil iti ruleaza la infinit. In primul if din cautare eu as sparge while-ul cu un break... sau oricum, trebuie facuta acolo o operatie care sa iti modifice st sau dr pentru ca din momentul in care conditia este indeplinita, st si dr nu se mai modifica (deci nu se mai iese din while).

[•klamathix]

Cod:

    
                      else dr=mij;
     

else dr = mij - 1;   

Mai bine fa-o functie :

Cod:

 

bool Bsearch ( int val ) { 

   int mid , left = j , right = N;
    
   while ( left <= right ) { 
        mid = ( left + right ) >> 1;
        if ( A[mid] == val ) return 1;
          else if ( A[mid] < val ) left = mid + 1;
              else right = mid - 1;
     }

return 0;
}

Break-urile si chestii dinastea nu-s chiar semnele programarii ingrijite  Am un coleg care face ceva gen while ( 1 ) { if ( nu stiu ce )  break; } Nu recomand Cel putin cand ai alternativa .

[•popoiu.george]

@miculprogramator

De ce descrescator? Vad ca pornesti i de la 0, daca porneai de la N-1 sortai descrescator.

Daca sortezi descrescator pentru v[ i ]+v[j] nu o sa gasesti nici un numar in intervalul (i,j) cara sa fie egal cu suma elementelor din capat.

Incearca sa sortezi crescator, si pt i si j sa cauti in intervalul (j,N].

P.S : Este o mica greseala in enunt

Acum si-a propus ss formeze grupuri distincte

[•vladtarniceru]

am rezolvat problema de 100 de puncte folosind sortarea+cautarea binara, dar se poate lua un vector v[1.000.000.000]?

adica de tip short, ca nu stiu cum sa verific daca incape in memorie ...

[•pauldb]

Socoteala memoriei se face asa:

(unsigned) char - 1 byte
(unsigned) short - 2 bytes
(unsigned) int/long/float - 4 bytes
(unsigned) long long/double - 8 bytes

Socotesti pentru fiecare variabila declarata cat ocupa, insumezi valorile si convertesti rezultatul la kb sau Mb, in functie de unitatea in care este exprimata limita de memorie.

In cazul tau un vector de lungime 10^9 de short inseamna 2*10^9 bytes = (aprox.) 2*10^6 kb = (aprox.) 2*10^3 Mb. Tu ai la dispozitie 16384 kb < 2*10^6 kb => nu poti declara atata memorie. In general, in probleme de olimpiada, nu poti aloca memorie de ordinul miliardelor sau al sutelor de milioane.

[•Johny_Depp22]

Eu am rezolvat problema fara hasuri si fara cautare binara si se pare ca e mai rapid asa decat cu hashuri. Am facut pur si simplu 2 for-uri si verificam daca v[ i ]+v[ j ]<=1000000000( 1<=i<=n si i+1<=j<=n) si daca mai e un element cu acea valoare ( in vectorul v am sirul initial si am mai tinut un bitset in care lg[ x ]=1 daca in sirul initial am un element egal cu x ( 1<=x<= 1000 000 000 ) ).  

[•ionut98]

imi puteti da un exemplu ca nu imi dau seama unde gresesc 

[•Mihai22e]

Pe testul

Cod:

3
1
2
3

programul tau afiseaza 0. Raspunsul corect e 1.

[•ionut98]

vreo idee de optimizare (cod sursa #1101355)

[•N00bSh4d0w]

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int v[3000];
int main()
{
    ifstream in("bete2.in");
    ofstream out("bete2.out");
    int n,s,start=1,endd,m=0;
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>v;
    }
    int ct=0;
    sort(v+1,v+n+1);
    for(int j=1; j<=n; j++)
    {
        for(int k=j+1; k<=n; k++)
        {
            s=v[j]+v[k];
            start=1;
            endd=n;
            while(start<=endd)
            {
                int mij=(start+endd)/2;
                if(v[mij]==s)
                {
                    ct++;
                    break;
                }
                else if(v[mij]<s)
                {
                    start=mij+1;
                }
                else endd=mij-1;
            }
        }
    }
    out<<ct<<"\n";
}