Rama

[•savim]

Aici se pot pune întrebări legate de problema Rama de la Runda 4 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•catalinutzb]

Scuzati-ma dar sunt nou pe infoarena... Sursele le salvam cu numele problemei?

[•freak93]

Intrebarea puteai sa o pui chiar pe topicul concursului. http://www.infoarena.ro/forum/index.php?topic=8798.0.

Dar oricum ca sa-ti raspund la intrebare: NU, nu trebuie sa salvezi cu numele problemei. Trebuie doar sa ai extensia .cpp .c sau .pas .

[•catalinutzb]

Multumesc mult

[•PlayLikeNeverB4]

Liniile formate din elemente de 1 se considera si ele valide?

[•vladii]

Da, si liniile si coloanele!

[•Dddarius95]

o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p...  TLE pe 3 teste ...
eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col...
apoi am sortat vectorul cu quicksort dupa val...
si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)...
si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare  dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)...
sugestii de optimizare?

[•razvan.popa]

Care era complexitatea oficiala ?

[•Cosmin]

n^2 log n dar s-a luat 100 cu n^3

[•razvan.popa]

n^2 log n dar s-a luat 100 cu n^3

Ciudat, eu am avut O(N^3) si am luat 60p.

Un hint pentru O(N^2 * logN) ?

[•gogu]

Sunt curios de solutia N^2 log N, suna misto.
Eu chiar am presupus ca era limita pentru N^3, ca intra in timp, doar ca am avut un bug la sursa trimisa in concurs care nu s-a manifestat pe niciunul din testele open

[•andretti]

o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p...  TLE pe 3 teste ...
eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col...
apoi am sortat vectorul cu quicksort dupa val...
si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)...
si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare  dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)...
sugestii de optimizare?

Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare.

[•freak93]

Ca hint pentru N^2 log:

Divide et Impera

[•Dddarius95]

Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare.

mersi. incerc sa implementez ce mi-ai zis. revin cu rezultatul

[•Dddarius95]

o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p...  TLE pe 3 teste ...
eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col...
apoi am sortat vectorul cu quicksort dupa val...
si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)...
si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare  dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)...
sugestii de optimizare?

Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare.

am incercat ce mi-ai sugerat. intr-adevar este mult mai rapid (inainte timpul maxim de executie pentru testele care intrau era 640ms acum este sub 180 ms)...dar tot da TLE pe 3 teste (aceleasi teste 4,7,9)...or fi cazuri particulare/speciale pe testele astea? (si poate nu le-am depistat eu)...
ideea sugerata de andretti am implementat-o prin procedurile spre_dreapta  si in_jos (lungimile respective salvandu-le in matricele dr si jos ).

Cod:

 
{$Q-}
program rama_runda4;
type punct=record
     val:longint;
     lin,col:integer;
     end;
     mat=array[1..701,1..701]of integer;
     vect=array[1..500001]of punct;
     vector=array[1..701]of integer;
var a,jos,dr:mat;
    ok:boolean; dreapta:vector;
    n,m:longint;
    v:vect;
    nr,k:longint;
    f,g:text;

procedure initializare;
var i,j:integer; c:char;
begin
readln(f,m,n);
for i:=1 to m do
  begin
  for j:=1 to n do begin
                   read(f,c);
                   if c='0' then a[i,j]:=0;
                   if c='1' then a[i,j]:=1;
                   end;
  readln(f);
  end;
end;

procedure quicksort(var a:vect;inf,sup:longint);
var i,j:longint; aux,pivot:punct;
begin
if (inf<sup)then begin
                 pivot:=a[inf];
                 i:=inf+1; j:=sup;
                 while (i<=j) do begin
                                 while (i<=sup)and(a[i].val<=pivot.val) do inc(i);
                                 while (j>=inf)and(a[j].val>pivot.val) do dec(j);
                                 if (i<j)and(i>=inf)and(j<=sup)then begin
                                                                    aux:=a[i];
                                                                    a[i]:=a[j];
                                                                    a[j]:=aux;
                                                                    inc(i); dec(j);
                                                                    end;
                                 end;
                 dec(i);
                 a[inf]:=a[i]; a[i]:=pivot;
                 quicksort(a,inf,i-1);
                 quicksort(a,i+1,sup);
                 end;
end;

procedure drept(x,y:integer;var ok:boolean);
var p,i,j:integer; ok1:boolean;
begin
i:=1; 
while (i<=m-x+1)and(dreapta[i]<y)do inc(i);
//verific daca fixand coltul stanga sus pe linia i am sanse sa gasesc lungimea y 
while (i<=m-x+1)and ok do
 begin
 j:=1;
 while ((dr[i,j]<y)or(jos[i,j]<x))and(j<=n-y+1)do inc(j);
 //daca pe coloana j gasesc inaltimea x
 while (j<=n-y+1)and ok do
    begin
    ok1:=true;
    p:=i;
    while (p<=i+x-1)and ok1 do
       begin
       if (a[p,j]=0)or(a[p,j+y-1]=0)then ok1:=false;
       inc(p);
       end;
    p:=j;
    while (p<=j+y-1)and ok1 do
       begin
       if (a[i,p]=0)or(a[i+x-1,p]=0)then ok1:=false;
       inc(p);
       end;
    if ok1 then begin
                nr:=x*y; //am gasit solutia
                ok:=false;//ma opresc
                end;
    inc(j);
    end;
 inc(i);
 end;
end;

procedure spre_dreapta(var dr:mat);
var i,j,primu,dif,k:integer;
begin
for i:=1 to m do
 begin
 j:=1; 
 repeat
 while (a[i,j]<>1)and(j<=n)do inc(j);
 primu:=j;
 while (a[i,j]=1)and(j<=n) do inc(j);
 dif:=j-primu; if dif>dreapta[i] then dreapta[i]:=dif;
 for k:=primu to j-1 do 
                       begin 
                       dr[i,k]:=dif;
                       dec(dif);
                       end;
 until j>n;
 end;
end;

procedure in_jos(var jos:mat);
var i,j,primu,dif,k:integer;
begin
for j:=1 to n do
 begin
 i:=1; 
 repeat
 while (a[i,j]<>1)and(i<=m)do inc(i);
 primu:=i;
 while (a[i,j]=1)and(i<=m) do inc(i);
 dif:=i-primu;
 for k:=primu to i-1 do 
                       begin 
                       jos[k,j]:=dif;
                       dec(dif);
                       end;
 until i>m;
 end;
end;

procedure cauta_dreptunghi;
var i,j,k:longint;
begin
//calculez toate ariile posibile i*j si le memorez in v
k:=0;
for i:=1 to m do
for j:=1 to n do
               begin
               inc(k);
               v[k].val:=i*j;v[k].lin:=i;v[k].col:=j;
               end;
quicksort(v,1,k);//ordonez vectorul crecator dupa arii
//pornesc cu cea mai mare arie. daca e buna ma opresc daca nu o iau pe urmatoarea(in ordine descrescatoare)
ok:=true; nr:=0;
while ok and(k>=1)do
  begin
  drept(v[k].lin,v[k].col,ok);
  dec(k);
  end;
writeln(g,nr);
end;

begin
assign(f,'rama.in');reset(f);
assign(g,'rama.out');rewrite(g);
initializare;
spre_dreapta(dr);
in_jos(jos);
cauta_dreptunghi;
close(f);close(g);
end.