infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 04, 2007, 14:07:38


Titlul: 337 Ograzi
Scris de: Adrian Diaconu din Martie 04, 2007, 14:07:38
Aici puteţi discuta despre problema Ograzi (http://infoarena.ro/problema/ograzi).

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 00:04:58
O solutie in care se sorteaza vectorul de ograzi si apoi se cauta binar fiecare oaie nu ar putea lua 100 de puncte .. dar 70 .. daca nu de ce ? .. Eu am implementat algoritmu asta si iau numa 40 de puncte (pe un singur test iau TLE :-') iar pe restu 5 teste iau WA ](*,) si nu inteleg de ce   :-k

Titlul: Răspuns: 337 Ograzi
Scris de: Adrian Diaconu din Martie 06, 2007, 00:10:45
Pai ce cauti tu binar? Ar trebui sa cauti vreo patru chestii.
O rezlvare de complexitate O(m log n) ar trebui sa ia cam 50 de puncte.
Arunca o privire peste solutia oficiala (http://infoarena.ro/preoni-2007/runda-3/solutii).

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 00:36:48
Pai caut (pe scurt) x>=ograda si x<=ograda+latime , analog pt y :P ; m-am uitat  peste solutia oficiala dar la linii de baleiere si hashuri m-am pierdut  :D  :'(

Titlul: Răspuns: 337 Ograzi
Scris de: Cosmin Negruseri din Martie 06, 2007, 01:23:29
Ai luat 40 de puncte cu asa ceva? Tare ...

Titlul: Răspuns: 337 Ograzi
Scris de: Musina Rares din Martie 06, 2007, 10:23:38
Citat din mesajul lui: Suciu Adrian din Martie 06, 2007, 00:36:48
Pai caut (pe scurt) x>=ograda si x<=ograda+latime , analog pt y :P ; m-am uitat  peste solutia oficiala dar la linii de baleiere si hashuri m-am pierdut  :D  :'(
Si eu am facut aceeasi chestie si tot 40 am luat...incearca un test de forma
3 2 2 2
2 2
1 6
4 5
5 2
2 7
In mod normal ar trebui sa iti pice, deoarece oaia de coordonate (2, 7) are acelasi x cu o ograda din care nu face parte si o omiti la cautare...

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 10:54:56

Cod:
3 2 2 2
2 2
1 6
4 5
5 2
2 7

Imi da 0 ... e corect ? Eu nu verific cu cautarea binara doar x'ul (practic am 2 cautari in una) : daca x'ul oii apartine de o ograda .. de fapt dupa ce ma complic  :D :
Cod:
if(x<ogr[c][0]){ dr=c-1;continue;}
if(x>ogr[c][0]+w){ st=c+1;continue;}
if(x>=ogr[c][0]&&x<=ogr[c][0]+w){
		if(y<ogr[c][1]){ dr=c-1;continue;}
		if(y>ogr[c][1]+h){ st=c+1;continue;}
		if(y>=ogr[c][1]&&y<=ogr[c][1]+h){ return 1;}


Asta e cautarea binara x,y is coordonatele oii, c ii (st+dr)/2 , iar ogr ii vectorul de ograzi sortat mai intai dupa x si apoi dupa y.  :mrgreen:

Titlul: Răspuns: 337 Ograzi
Scris de: Musina Rares din Martie 06, 2007, 11:23:20
raspunsul e 1...fa si pe foaie-asa o sa intelegi mai bine unde nu iti merge...

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 12:43:28
La testul tau imi da rezultatul 1 dar tot 40 de puncte iau  ](*,) .. Cred ca o sa ma resemnez :P

Titlul: Răspuns: 337 Ograzi
Scris de: Bondane Cosmin din Martie 06, 2007, 12:48:28
Citat
5 7 2 2
2 2
6 2
4 5
7 7
1 6
5 2
8 5
1 5
8 8
2 7
1 6
1 7

Raspunsul este 4.

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 12:49:48
Citat
Raspunsul este 4.
Atata primesc si eu ... am incercat aproape totul in afara de solutia oficiala .. oricum algoritmul meu teoretic ar trebui sa mearga  :annoyed:

Titlul: Răspuns: 337 Ograzi
Scris de: Savin Tiberiu din Martie 06, 2007, 15:19:43
Citat
Pai caut (pe scurt) x>=ograda si x<=ograda+latime , analog pt y Tongue ; m-am uitat  peste solutia oficiala dar la linii de baleiere si hashuri m-am pierdut  Very Happy  Cry

adik u cauti binar nr de oi care se incadreaza intre x-urile celor 2 ograzi si apoi intre y-urile lor. adik dak ai ograda x1 y1,x2 y2 u verifica cate oi ai intre x1 si x2 si cate oi ai intre y1 si y2. Daca asta faci pai atunci u ce faci cu cele 2 rezultate??

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 15:34:22
Citat
dik u cauti binar nr de oi care se incadreaza intre x-urile celor 2 ograzi si apoi intre y-urile lor. adik dak ai ograda x1 y1,x2 y2 u verifica cate oi ai intre x1 si x2 si cate oi ai intre y1 si y2. Daca asta faci pai atunci u ce faci cu cele 2 rezultate??

Nu... eu am un vector sortat de ograzi ({1,2},{1,5},{3,4},{3,8}) (un exemplu)
citesc coordonatele oii din fisier(x,y) si fac cautarea binara astfel:
Cod:
cat timp(dr>st)
  c=(st+dr)/2
  daca x(oaie)<x(ograda[c])
          atunci dr=c-1;
  daca x(oaie)>x(ograda[c]+latime )
          atunci st=c+1 
  daca(x(oaie) apartine intervalului (ograda[c],ograda[c]+latime)
          atunci
  		daca y(oaie)<y(ograda[c])
                           atunci dr=c-1;
  		daca y(oaie)>y(ograda[c]+inaltime)
                           atunci  st=c+1;
  		daca y(oaie) apartine intervalului (ograda[c],ograda[c]+inaltime)
                        atunci 
                           incrementez numarul oilor;
                           termin cautarea;
                    
sfarsit cat timp


Sper ca ai inteles ideea :P

Titlul: Răspuns: 337 Ograzi
Scris de: Airinei Adrian din Martie 06, 2007, 21:51:11
Nu cred ca o sa stea cineva sa iti gaseasca un contraexemplu pentru algoritmul tau, in schimb poti sa iti generezi tu niste teste si sa compari rezultatul tau cu un program simplu O(N*M). Cand ai gasit un test pe care nu iti da aceleasi valori faci un debug :thumbup:

Titlul: Răspuns: 337 Ograzi
Scris de: Suciu Adrian din Martie 06, 2007, 21:57:19
Citat din mesajul lui: Airinei Adrian din Martie 06, 2007, 21:51:11
Nu cred ca o sa stea cineva sa iti gaseasca un contraexemplu pentru algoritmul tau, in schimb poti sa iti generezi tu niste teste si sa compari rezultatul tau cu un program simplu O(N*M). Cand ai gasit un test pe care nu iti da aceleasi valori faci un debug :thumbup:

Mersi de idee .. nu m-am gandit la asta :P

Titlul: Răspuns: 337 Ograzi
Scris de: Claudiu Guiman din Martie 07, 2007, 18:47:22
Am incercat sa implementez solutia prezentata de voi... dar nu stiu unde am gresit de iau doar 50 de puncte, la celelalte teste primesc TLE... ar trebui sa fac functia de dispersie mai buna?

Titlul: Răspuns: 337 Ograzi
Scris de: Cosmin Negruseri din Martie 08, 2007, 10:16:52
tu implementezi propriul tau hash_map sau il folosesti pe cel din stl?

Titlul: Răspuns: 337 Ograzi
Scris de: Bogdan-Alexandru Stoica din Martie 08, 2007, 10:22:08
incearca sa parsezi citirea. daca nici asa nu merge inseamna ca nu ai reusit sa dezvolti un algoritm de complexitate optima ( O(N+M) ).

Titlul: Răspuns: 337 Ograzi
Scris de: Claudiu Guiman din Martie 08, 2007, 11:18:41
Citat din mesajul lui: Bogdan A. Stoica din Martie 08, 2007, 10:22:08
incearca sa parsezi citirea. daca nici asa nu merge inseamna ca nu ai reusit sa dezvolti un algoritm de complexitate optima ( O(N+M) ).

 :-k  am facut citirea cu fgets, si cred ca am respectat indicatiile.....

Titlul: Răspuns: 337 Ograzi
Scris de: Andrei Grigorean din Martie 08, 2007, 14:46:49
Cauta pe google diferite functii de hash, si alege una care iti intra in timp :P. Incercarea moarte n-are.

Titlul: Răspuns: 337 Ograzi
Scris de: Stratulat Alexandru din Martie 10, 2013, 13:54:14
Eu incerc sa fac O(n*m), adica sa verific pentru fiecare oita daca intra intr-o ograda. Imi da raspuns corect doar in unele cazuri si chiar nu inteleg ce imi scapa la implementare : Oita[j] coord unei oi si Ograd coord din stanga jos a ograzii.

Nmax = M;
    for(register int i=1;i<=N;++i)
        for(register int j=1;j<=M;++j)
            if(Oita[j].x <= Ograd.x +H && Oita[j].x >= Ograd.x && Oita[j].y <= Ograd.y +L && Oita[j].y >= Ograd.y)
                Nmax--;

    printf("%d",Nmax);


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