086 Luna

[•APOCALYPTO]

Dar cum se poate afla in o(1) daca firma poate construi respectiva cladire...?

Buna intrebare.
Cum?

Si asta se poate calcula in O(N^3).

Eu am facut in O(N^4) si am luat 100.
Cum poti face in O(N^3)?

[•DanceKriss]

O(M*N^4) se genereaza posibilitati de dreptunghiuri din (i,j) in (ii,jj) .... fiind colturi ale dreptunghiului. ?? 

[•SpiderMan]

In niciun caz, problema se face in O( N³ ) , dar se poate si in O( N⁴ ), care intra de asemenea in timp.

[•DanceKriss]

ar fi bine mai intai sa descopar cum se face corect in o(n^4) ....:d  

Later edit : ce fel de citire ati adoptat cei care ati luat 100 (cu parsare) 
mie imi iese din timp pe prima sursa care am pus-o chiar daca are complexitate n*m + 2500*k(10^5)
// e busita sursa orikm ca idee....

[•SpiderMan]

Nu, desi volumul de date nu este mare, nu prea are rost sa se utilizeze citire parsata. Ti-am spus complexitatile optime, nu incerca altceva ca nu prea merge .... doar asa ca sfat.

[•swim406]

Daca o tara 1 vrea sa construiasca o cladire de dimensiune 2 3 sa zicem... Poate si in cazul

1 1 1
1 1 1

si in cazul

1 1
1 1
1 1

? Sau numai in primul caz?

[•skull]

Se poate construi in ambele cazuri.

[•S7012MY]

Ce are testul 7 ?

Testul 7 are la query-uri dimensiuni mai mari decat matricea

[•ctlin04]

Rog pe cineva care a rezolvat pe 100 sa se uite peste sursa mea http://infoarena.ro/job_detail/782469 sa-mi spuna ce e gresit sau macar dati-mi un test pe care sa nu mearga ca eu am testat mai mult de o ora si inca nu am dat peste un test care sa-mi dea gresit, dar totusi iau doar 45 cu incorect pe celelalte  

[•DorelBarbu]

Salutare! Am incercat si eu sa rezolv aceasta problema. Ati putea da un mic hint, va rog ?

[•dariusdarius]

Am o intrebare. Am facut problema cu complexitate O( N^4 + M ) (ia 100), pregenerand o matrice cu d[ i ][ j ] = inaltimea maxima care poate sa o aiba un dreptunghi al firmei i, cu lungimea j ( O(N^4) ). Intrebarea era cum se poate face aceasta pregenerare in O(N^3)?

[•vendetta]

Ideea pentru n ^ 3 ar fi : dinamica e buna adica dp[ i ][ j ] = inaltimea maxima ce o poate avea o tara de tipul i daca are lungimea j;
si fie h[ i ][ j ] = cat de mult ma pot duce in sus pe coloana j; acum tu te afli la pozitia i,j; ii afli tara si acum presupui cu coltul dreapta jos a dreptunghiului se afla in (i,j); acum fixezi lungimea dreptunghiului; pentru fiecare lungime fixata raspunsul va fi minimul( h[ i ][ k(indicele lungimii) .. j]); si acest minim il actualizezi la fiecare noua lungime.

[•DorelBarbu]

Multumesc de ajutor! Indirect, ultimele doua comentarii m-au ajutat foarte mult . Am facut o sursa de 45 pct, care insa se incadreaza in timp si memorie. La celelalte teste iau wrong answer. Printre testele care le pic sunt si primele 2. Nu inteleg care este greseala. Ma puteti ajuta, va rog? Am folosit o matrice d, cu semnificatia data de voi ( voi= Salajan Razvan si Marian Darius). d[j]=inaltimea maxima pe care o poate avea un dreptunghi al firmei i, cu lungimea j. Stiu ca nu pot posta o sursa intreaga (nici nu vreau, pentru ca nu vreau mura-n gura) , asa ca o sa postez bucata din main, in care citesc cererile si le analizez:

Cod:

scanf("%d", &nr_requests);
    for(i=1; i<=nr_requests; i++)
    {
        scanf("%d%d%d",&color, &lg2, &lg1);
        if(d[color][1]==0) printf("Tara de provenienta nu are parcele pe luna!");
        else if(lg2<=d[color][lg1] || lg1<=d[color][lg2]) printf("Cererea poate fi satisfacuta!");
        else printf("Cererea nu poate fi satisfacuta!");
        printf("%s","\n");
    }

Ma puteti ajuta va rog? Imi scapa ceva aici, sau trebuie sa mai verfic construirea matricei d. As aprecia mult un raspuns.

[•assa98]

Salut. Eu am o matrice d[ i ][ j ] unde d[ i ][j]=inaltimea dreptunghiului (de lungime 1) mergand in sus si o matrice r[ i ][j] unde patsrez  inaltimea maxima a unui dreptunghi al tarii i, cu lungimea j .
Totusi iau 40p. Stie cineva ce e gresit?

[•assa98]

Ok. nu mai conteaza aveam functia de min(a,b) definita gresit...

[•DorelBarbu]

Primul test al evaluatorului este chiar exemplul problemei? Nu iau primul test si multe altele. Dar ma surprinde ca nu-l iau pe primul

[•ctlin04]

Testele sunt tot timpul diferite de exemple, asa ca nu e nimic straniu ca exemplele iti merg iar primul test nu  
Apropo, dreptunghiurile pe care se construiesc cladiri au laturile paralele cu marginile hartii sau pot fi si oblice??  

[•DorelBarbu]

Ma poate ajuta cineva, va rog? Incerc sa maresc punctajul la aceasta problema. Iata cum am gandit eu. Intai creez o matrice auxiliara h, cu h[j]=cat de mult ma pot duce in jos, plecand din coordonata (i,j).

Dupa, contruiesc matricea d, cu d[j]=lungimea maxima a unui dreptunghi de culoare i, cu inaltimea j. Pentru construierea acestei matrici folosesc algoritmul de determinare a dreptunghiului de arie maxima dintr-o histograma.

E buna ideea? M-am complicat folosind problema histogramei?

[•DorelBarbu]

@Catalin, eu banuiesc ca laturile sunt paralele cu matricea.Cazul cu dreptunghiuri "oblice" mi se pare sub semnul intrebarii. Uite de ce cred asta: daca consideram unitatea de arie egala cu un patratel din matrice, pentru realizarea de dreptunghiuri oblice am avea nevoie de fractiuni de unitate iar asta ar complica putin problema.

Sper ca nu am luat-o pe aratura cu parerea mea )).

[•DorelBarbu]

Ok, am mai lucrat la problema. Am reusit sa iau 45 de puncte, iar la restul testelor sa obtin doar wrong answer, fara TLE-uri sau "killed by signal". Este ok daca am folosit ideea de la problema determinarii dreptunghiului de arie maxima dintr-o histograma? Sau m-am complicat?

[•horatiu11]

Buna!
Nu stiu de ce iau 50 de puncte. Pe restul iau incorect. Construiesc o matrice M[j] in care memorez pt tipul i si lungimea j, inaltimea maxima.
Apoi afisez in functie de datele citite.

Cod:

//horatiu11
# include <cstdio>
# define nmax 53
# define vmax 5003
using namespace std;
int n,m,k,a[nmax][nmax],M[vmax][nmax],type,l1,l2;
int main()
{
    int i,j,l,c,x,y;
    freopen("luna.in","r",stdin);
    freopen("luna.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            c=j;type=a[i][j];
            while(a[i][c]==type)--c;
            x=j-c;
            l=i;
            while(a[l][j]==type)--l;
            y=i-l;
            if(y>M[type][x])M[type][x]=y;
        }
    scanf("%d",&k);
    for(i=1;i<=k;++i)
    {
        scanf("%d%d%d",&type,&l1,&l2);
        if(M[type][1]==0)printf("Tara de provenienta nu are parcele pe Luna!\n");
        else if(M[type][l1]>=l2 || M[type][l2]>=l1)printf("Cererea poate fi satisfacuta!\n");
        else printf("Cererea nu poate fi satisfacuta!\n");
    }
    return 0;
}

[•chiriacandrei25]

horatiu11 :
vezi ca nu te opresti cand incepi deja sa ai elemente diferite pe linia respectiva cand construiesti matricea d.
gen, daca ai linia ta :
11122212211
tu actualizezi solutia pt ultimul 1, penultimul, dar cand dai peste 2 trebuie sa iesi din for, nu sa continui 

[•horatiu11]

Tu spui ca ar trebui sa trec pe linia urmatoare cand intalnesc o valoare diferita(adica sa parasesc forul cu j pt coloane)?
Poti da un exemplu mai bun sa inteleg ?
Merci

[•gedica]

Salut....Se uita cineva pe sursa mea de 25pct va rog?   
Multumesc    

[•japjappedulap]

Tare interesanta problema asta. Orice test ii dau, pe sursa mea merge, dar iau doar 50 de puncte...
Se uita cineva peste sursa mea?
http://www.infoarena.ro/job_detail/1239005?action=view-source