infoarena

infoarena - concursuri, probleme, evaluator, articole => Algoritmiada 2013 => Subiect creat de: Serban Andrei Stan din Martie 24, 2013, 00:56:58



Titlul: Rama
Scris de: Serban Andrei Stan din Martie 24, 2013, 00:56:58
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.


Titlul: Răspuns: Rama
Scris de: Craciun Catalin din Martie 24, 2013, 09:26:41
Scuzati-ma dar sunt nou pe infoarena... Sursele le salvam cu numele problemei?


Titlul: Răspuns: Rama
Scris de: Adrian Budau din Martie 24, 2013, 09:36:38
Intrebarea puteai sa o pui chiar pe topicul concursului. http://www.infoarena.ro/forum/index.php?topic=8798.0 (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 .


Titlul: Răspuns: Rama
Scris de: Craciun Catalin din Martie 24, 2013, 09:39:47
Multumesc mult


Titlul: Răspuns: Rama
Scris de: George Marcus din Martie 24, 2013, 10:15:55
Liniile formate din elemente de 1 se considera si ele valide?


Titlul: Răspuns: Rama
Scris de: Ionescu Vlad din Martie 24, 2013, 10:17:24
Da, si liniile si coloanele!


Titlul: Răspuns: Rama
Scris de: Darius-Florentin Neatu din Martie 24, 2013, 14:37:17
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?


Titlul: Răspuns: Rama
Scris de: Popa Razvan din Martie 24, 2013, 15:53:34
Care era complexitatea oficiala ?


Titlul: Răspuns: Rama
Scris de: Cosmin Negruseri din Martie 24, 2013, 16:02:21
n^2 log n dar s-a luat 100 cu n^3


Titlul: Răspuns: Rama
Scris de: Popa Razvan din Martie 24, 2013, 16:14:31
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) ?


Titlul: Răspuns: Rama
Scris de: Gogu Marian din Martie 24, 2013, 16:16:32
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 :D


Titlul: Răspuns: Rama
Scris de: Andretti Naiden din Martie 24, 2013, 19:51:22
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.


Titlul: Răspuns: Rama
Scris de: Adrian Budau din Martie 24, 2013, 19:55:14
Ca hint pentru N^2 log:

Divide et Impera


Titlul: Răspuns: Rama
Scris de: Darius-Florentin Neatu din Martie 25, 2013, 08:39:16

Citat
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


Titlul: Răspuns: Rama
Scris de: Darius-Florentin Neatu din Martie 25, 2013, 09:54:56
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.