337 Ograzi

[•DITzoneC]

Aici puteţi discuta despre problema Ograzi.

[•Adix]

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   

[•DITzoneC]

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.

[•Adix]

Pai caut (pe scurt) x>=ograda si x<=ograda+latime , analog pt y ; m-am uitat  peste solutia oficiala dar la linii de baleiere si hashuri m-am pierdut   

[•Cosmin]

Ai luat 40 de puncte cu asa ceva? Tare ...

[•cretu]

Pai caut (pe scurt) x>=ograda si x<=ograda+latime , analog pt y ; m-am uitat  peste solutia oficiala dar la linii de baleiere si hashuri m-am pierdut   

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

[•Adix]

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  :

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. 

[•cretu]

raspunsul e 1...fa si pe foaie-asa o sa intelegi mai bine unde nu iti merge...

[•Adix]

La testul tau imi da rezultatul 1 dar tot 40 de puncte iau  .. Cred ca o sa ma resemnez

[•cos_min]

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.

[•Adix]

Raspunsul este 4.

Atata primesc si eu ... am incercat aproape totul in afara de solutia oficiala .. oricum algoritmul meu teoretic ar trebui sa mearga 

[•devilkind]

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??

[•Adix]

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

[•astronomy]

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

[•Adix]

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

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

[•y2k]

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?

[•Cosmin]

tu implementezi propriul tau hash_map sau il folosesti pe cel din stl?

[•fireatmyself]

incearca sa parsezi citirea. daca nici asa nu merge inseamna ca nu ai reusit sa dezvolti un algoritm de complexitate optima ( O(N+M) ).

[•y2k]

incearca sa parsezi citirea. daca nici asa nu merge inseamna ca nu ai reusit sa dezvolti un algoritm de complexitate optima ( O(N+M) ).

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

[•wefgef]

Cauta pe google diferite functii de hash, si alege una care iti intra in timp . Incercarea moarte n-are.

[•Fayed]

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