infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Airinei Adrian din Aprilie 05, 2009, 11:27:50


Titlul: 841 Bete2
Scris de: Airinei Adrian din Aprilie 05, 2009, 11:27:50
Aici puteti discuta despre problema Bete2 (http://infoarena.ro/problema/bete2).

Titlul: Răspuns: 841 Bete2
Scris de: A Andrei din Aprilie 05, 2009, 11:45:29
O idee pentru a obtine 100 puncte?! #-o

Titlul: Răspuns: 841 Bete2
Scris de: Marius Stroe din Aprilie 05, 2009, 16:03:24
Citat din mesajul lui: Avadanei Andrei din Aprilie 05, 2009, 11:45:29
O idee pentru a obtine 100 puncte?! #-o

Căutare binară.

Titlul: Răspuns: 841 Bete2
Scris de: Florian Marcu din Aprilie 05, 2009, 16:25:43
Se poate mai rapid de O(N^2 * logN ) ?   :-k

Titlul: Răspuns: 841 Bete2
Scris de: A Andrei din Aprilie 05, 2009, 17:00:56
Multumesc! =D>

Titlul: Răspuns: 841 Bete2
Scris de: Marius Stroe din Aprilie 05, 2009, 17:28:32
Citat din mesajul lui: Marcu Florian din Aprilie 05, 2009, 16:25:43
Se poate mai rapid de O(N^2 * logN ) ?   :-k

O(N2) cu hashuri.

Titlul: Răspuns: 841 Bete2
Scris de: Cezar Mocan din Aprilie 06, 2009, 07:22:00
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...

Titlul: Răspuns: 841 Bete2
Scris de: A Andrei din Aprilie 06, 2009, 09:47:16
Citat din mesajul lui: Avadanei Andrei din Aprilie 06, 2009, 09:46:14
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.

Titlul: Răspuns: 841 Bete2
Scris de: Cezar Mocan din Aprilie 06, 2009, 10:00:20
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).

Titlul: Răspuns: 841 Bete2
Scris de: A Andrei din Aprilie 06, 2009, 11:12:45
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.

Titlul: Răspuns: 841 Bete2
Scris de: Florian Marcu din Aprilie 06, 2009, 11:19:54
Nu asa.  :)
Citat

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

Titlul: Răspuns: 841 Bete2
Scris de: Tirca Bogdan din Aprilie 07, 2009, 22:22:17
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...)??? :-k

Titlul: Răspuns: 841 Bete2
Scris de: Preda Rares Mihai din Aprilie 10, 2009, 22:58:35
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.

Titlul: Răspuns: 841 Bete2
Scris de: Codrin LACHE din Aprilie 17, 2009, 17:01:49
 e ceva mai special la primele 4 teste??
ca iau WA si chiar nu stiu ce gresesc  :readthis:

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--;
		    }
	    }
    }

Titlul: Răspuns: 841 Bete2
Scris de: A Cosmina - vechi din Iulie 30, 2009, 19:37:25
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;
              }
        }


Titlul: Răspuns: 841 Bete2
Scris de: Sima Cotizo din Iulie 30, 2009, 19:42:04
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).

Titlul: Răspuns: 841 Bete2
Scris de: Mihai Calancea din Iulie 30, 2009, 22:01:29

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  :D Am un coleg care face ceva gen while ( 1 ) { if ( nu stiu ce )  break; } Nu recomand :roll: Cel putin cand ai alternativa .

Titlul: Răspuns: 841 Bete2
Scris de: George Popoiu din Ianuarie 04, 2010, 23:26:49
@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
Citat
Acum si-a propus ss formeze grupuri distincte

Titlul: Răspuns: 841 Bete2
Scris de: Vlad Tarniceru din Iunie 01, 2010, 20:20:23
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 ...

Titlul: Răspuns: 841 Bete2
Scris de: Paul-Dan Baltescu din Iunie 01, 2010, 20:32:19
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.

Titlul: Răspuns: 841 Bete2
Scris de: Johnny Depp din Mai 27, 2013, 13:53:20
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 ) ).  

Titlul: Răspuns: 841 Bete2
Scris de: Bejenariu Ionut Daniel din Ianuarie 19, 2014, 16:12:27
imi puteti da un exemplu ca nu imi dau seama unde gresesc  :)

Titlul: Răspuns: 841 Bete2
Scris de: Mihai Ionut Enache din Ianuarie 19, 2014, 16:29:46
Pe testul
Cod:
3
1
2
3
programul tau afiseaza 0. Raspunsul corect e 1.

Titlul: Răspuns: 841 Bete2
Scris de: Bejenariu Ionut Daniel din Februarie 08, 2014, 12:38:36
vreo idee de optimizare (cod sursa #1101355)

Titlul: Răspuns: 841 Bete2
Scris de: Rodion Raskolnikov din Martie 24, 2016, 15:53:21
#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";
} :)

Titlul: Răspuns: 841 Bete2
Scris de: Bejenariu Ionut Daniel din Martie 26, 2016, 21:30:41
Multumesc!

 \:D/


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines