086 Luna

[•domino]

Aici puteţi discuta despre problema Luna.

[cristi8]

cam mare limita de timp.. ati putea incuraja la o rezolvare mai buna
eu am scos o(n^3 + K)

aa.. si o observatie:

* numarul de ordine a unei tari este un numar natural cuprins intre 1 si 2500 (nu uitati, sun­tem in anul 2507, s-au mai format niste tari...)

* numarul de ordine a tarii de provenienta a unei firme este un numar natural cuprins intre 1 si 5000

[vladut.forum]

e ceva strange la evaluator la Luna,
eu lucrez in c++, si citirea si afisarea o fac c standard, am trimis nustiu cate surse si am luat 0, primind mesajul Run Time erorr-Invalid Memory Reference, si tot am trimis, am ajuns sa pun in comentariu codu sa vad unde moare, si tot sa trimit, am trimis o sursa care face numa citirea matricei, tot acest mesaj, cand am schimbat citirea si afisarea in fstream, a mers... n-am mai primit acel mesaj.
am obtinut 55 cu O(n^5+k), la unele teste iau incorect da nustiu de ce
infine, problema e de ce nu mergea cu citirea fscanf...

[•domino]

e ceva strange la evaluator la Luna,
eu lucrez in c++, si citirea si afisarea o fac c standard, am trimis nustiu cate surse si am luat 0, primind mesajul Run Time erorr-Invalid Memory Reference, si tot am trimis, am ajuns sa pun in comentariu codu sa vad unde moare, si tot sa trimit, am trimis o sursa care face numa citirea matricei, tot acest mesaj, cand am schimbat citirea si afisarea in fstream, a mers... n-am mai primit acel mesaj.
am obtinut 55 cu O(n^5+k), la unele teste iau incorect da nustiu de ce
infine, problema e de ce nu mergea cu citirea fscanf...

Faceai ceva gresit probabil, fiindca sursa mea face tot cu scanf. Evaluatorul este sigur bun. (foloseste "diff" din linux)

[vladut.forum]

wow da
ai dreptate da nu credeam ca aici e vina, aveam ceva de genu

Cod:

int main() {
int k,l;
fin=fopen("luna.in","r");
fout=fopen("luna.out","w");
}

faptul ca am declarat int k,l; inainte de deschiderea fiserelor, omora programul acum am luat 100 cu O(n^5+k) cu citirea c standard;
si cu streamuri in O(n^5+k) am luat 95; am observat ca c standard folosit la citire si afisare, e cu mult mai rapid decat streamurile...
la ultimul test cu stream luam TLE si in c standartd 0.19. apai da...

[•sarabogdan]

Hrta lunii poate fi si de forma

1 2 1 1
1 2 1 1

?

[•domino]

Hrta lunii poate fi si de forma

1 2 1 1
1 2 1 1

?

da

[•Marius]

teritoriul pe de luna poate fi si asa:
1 1 1 1 1
1 2 2 1 1
1 2 1 1 1
?  

[•filipb]

DA

[•pauldb]

Deci cum e pana la urma: numarul maxim de ordine al unei tari e 2500 sau 5000?

[u-92]

daca lasi limita la 2500 merge de 100

[•peanutz]

In anul 2507 colonizarea Lunii a luat sfarsit, fiecare tara detine cateva parcele din teritoriul planetei.

Nu vreau sa par enervant, dar luna nu era cumva satelit? 

[•Marius]

In anul 2507 colonizarea Lunii a luat sfarsit, fiecare tara detine cateva parcele din teritoriul planetei.

Nu vreau sa par enervant, dar luna nu era cumva satelit? 

Pana in 2507 poate dispare Pamantul si ramane doar Luna, cine stie ?   

[•bogdan88]

Am si eu o intrebare...vreau sa implementez problema asta si eram curios cum se poate afla de ex pt. 1 care este dreptunghiul cel mai mare din matrice format numai din 1?

[•ionescu88]

CUM POT AFLA CARE ESTE CEL MAI MARE DREPTUNGHI FORMAT NUMA CU O ANUMITA CIFRA? CEL MAI OPTIM CA NU IMI VIN IDEi...pls help me

[•fireatmyself]

poti sa faci o preprocesare pentru linie:

M[ i, j ] = lungimea maxima a unei secvente care se afla pe linia i, incepe la pozitia j si care apartine                                      tarii cu idul A[ i, j ] (matricea din input)

cu ajutorul acestei matrici se pot calcula ( in O(N^4) ) lungimea, respectiv latimea maxima pe care le poate folosi o tara in scopul unei constructii.

[•ionescu88]

MS MUUULT.......DAR sa stii ca nu inteleg

[•fireatmyself]

dupa ce calculezi matricea M, fixezi doua linii (l1, l2) si o coloana (c1). acum trebuie sa determini o coloana c2, a.i. dreptunghiul avand colturile in (l1, c1) si (l2, c2) sa cuprinda doar zone ce apartin aceleasi firme. acest c2 se afla cu ajutorul matricii M, astfel: c2 = min{ M[l1][c1], M[l1+1][c1], ..., M[l2][c1]}.

[•drag0s93]

Puteti sa mi dati si mie un exemplu extrem pentru aceasta problema:D ......ca nu inteleg dc iau punctajul  :annoyed:asta ....

[•Bogdan_tmm]

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

[•taloibogdan]

Buna intrebare.
Cum?

[•Mishu91]

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

Buna intrebare.
Cum?

Ideea e sa-ti precalculezi o matrice in care sa retii pentru fiecare tara si o lungime, cat de mare poate fi inaltimea.
Adica ceva de genu A[ i ][ j ] = k, inseamna ca inaltimea maxima pt un dreptunghi din tara i cu inaltimea j este k. Evident A[ i ][ k ] = j.
Si asta se poate calcula in O(N^3).

[•zloteanu.adrian]

poate nu inteleg eu bine  problema...
dar in exemplul dat,suprafata tarii 1 este
1 1 1
1 1 1
si tara vrea sa construiasca 2 cladiri:
2 3
3 2
in exemplu, zice ca a doua cerere poate fi satisfacuta, dar (3 2) nici nu intra in suprafata, mai ales daca mai construiesc si o alta cladire!!!
 

[•Tabara]

poate nu inteleg eu bine  problema...
dar in exemplul dat,suprafata tarii 1 este
1 1 1
1 1 1
si tara vrea sa construiasca 2 cladiri:
2 3
3 2
in exemplu, zice ca a doua cerere poate fi satisfacuta, dar (3 2) nici nu intra in suprafata, mai ales daca mai construiesc si o alta cladire!!!
 

Constructiile NU au un efect 'cumulativ' ( deci, daca ai construit o cladire, respectivul teren NU este ocupat pentru o viitoare cerere ).
Cat despre exemplu, cladirea este pusa in matricea de '1' transpusa. ( poate fi pusa in orice forma, atata timp cat incape in proprietate ).

[•zloteanu.adrian]

multumesc