infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din August 29, 2005, 20:01:41



Titlul: 086 Luna
Scris de: Mircea Pasoi din August 29, 2005, 20:01:41
Aici puteţi discuta despre problema Luna (http://infoarena.ro/problema/luna).


Titlul: 086 Luna
Scris de: cristi8 din August 29, 2005, 23:21:46
cam mare limita de timp.. ati putea incuraja la o rezolvare mai buna :D
eu am scos o(n^3 + K)

aa.. si o observatie:
Citat
* 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


Titlul: curios la evaluator
Scris de: vladut.forum din August 30, 2005, 12:20:13
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...???


Titlul: Re: curios la evaluator
Scris de: Mircea Pasoi din August 30, 2005, 12:45:17
Citat din mesajul lui: 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...???


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


Titlul: 086 Luna
Scris de: vladut.forum din August 30, 2005, 13:53:24
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...


Titlul: 086 Luna
Scris de: Sara Nicolae Bogdan din August 31, 2005, 14:25:20
Hrta lunii poate fi si de forma

1 2 1 1
1 2 1 1

?


Titlul: 086 Luna
Scris de: Mircea Pasoi din August 31, 2005, 14:28:29
Citat din mesajul lui: sarabogdan
Hrta lunii poate fi si de forma

1 2 1 1
1 2 1 1

?


da


Titlul: 086 Luna
Scris de: Marius Stroe din Ianuarie 03, 2006, 19:00:37
teritoriul pe de luna poate fi si asa:
1 1 1 1 1
1 2 2 1 1
1 2 1 1 1
?   :?


Titlul: 086 Luna
Scris de: Filip Cristian Buruiana din Ianuarie 03, 2006, 20:24:02
DA


Titlul: 086 Luna
Scris de: Paul-Dan Baltescu din Martie 09, 2006, 21:29:32
Deci cum e pana la urma: numarul maxim de ordine al unei tari e 2500 sau 5000?


Titlul: 086 Luna
Scris de: u-92 din Martie 09, 2006, 21:46:57
daca lasi limita la 2500 merge de 100


Titlul: Raspuns: 086 Luna
Scris de: Andrei Homorodean din Decembrie 29, 2006, 01:30:54

Citat
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?  :-'


Titlul: Raspuns: 086 Luna
Scris de: Marius Stroe din Decembrie 29, 2006, 21:00:23

Citat
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 ?   8)


Titlul: Răspuns: 086 Luna
Scris de: Bogdan Popescu din Mai 19, 2007, 11:45:20
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?


Titlul: Răspuns: 086 Luna
Scris de: alex ionescu din Octombrie 04, 2007, 14:40:34
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


Titlul: Răspuns: 086 Luna
Scris de: Bogdan-Alexandru Stoica din Octombrie 04, 2007, 15:12:48
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.


Titlul: Răspuns: 086 Luna
Scris de: alex ionescu din Octombrie 04, 2007, 15:28:33
MS MUUULT.......DAR sa stii ca nu inteleg


Titlul: Răspuns: 086 Luna
Scris de: Bogdan-Alexandru Stoica din Octombrie 04, 2007, 15:40:22
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]}.


Titlul: Răspuns: 086 Luna
Scris de: Mandu Dragos din Ianuarie 06, 2009, 15:40:04
Puteti sa mi dati si mie un exemplu extrem pentru aceasta problema:D ......ca nu inteleg dc iau punctajul  :annoyed:asta ....


Titlul: Răspuns: 086 Luna
Scris de: Tirca Bogdan din Aprilie 08, 2009, 10:44:35
Dar cum se poate afla in o(1) daca firma poate construi respectiva cladire...?


Titlul: Răspuns: 086 Luna
Scris de: Taloi Bogdan Cristian din Mai 23, 2009, 16:53:38
Buna intrebare.
Cum? :?


Titlul: Răspuns: 086 Luna
Scris de: Andrei Misarca din Mai 23, 2009, 18:56:33
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). :)


Titlul: Răspuns: 086 Luna
Scris de: zloteanu adrian nichita din Iulie 02, 2009, 10:29:01
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!!!
 :read: :read: :read:


Titlul: Răspuns: 086 Luna
Scris de: Tabara Mihai din Iulie 03, 2009, 13:06:21
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!!!
 :read: :read: :read:

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


Titlul: Răspuns: 086 Luna
Scris de: zloteanu adrian nichita din Iulie 03, 2009, 13:38:39
multumesc


Titlul: Răspuns: 086 Luna
Scris de: Dragos din August 21, 2010, 16:32:33
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)?


Titlul: Răspuns: 086 Luna
Scris de: Cristian Oancea din Martie 13, 2011, 19:27:26
O(M*N^4) ??? se genereaza posibilitati de dreptunghiuri din (i,j) in (ii,jj) .... fiind colturi ale dreptunghiului. ??  ](*,) ](*,) ](*,)


Titlul: Răspuns: 086 Luna
Scris de: Simoiu Robert din Martie 13, 2011, 20:01:22
In niciun caz, problema se face in O( N3 ) , dar se poate si in O( N4 ), care intra de asemenea in timp.


Titlul: Răspuns: 086 Luna
Scris de: Cristian Oancea din Martie 13, 2011, 20:46:29
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....



Titlul: Răspuns: 086 Luna
Scris de: Simoiu Robert din Martie 14, 2011, 13:07:48
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.


Titlul: Răspuns: 086 Luna
Scris de: Teudan Adina din Martie 14, 2011, 23:05:14
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?


Titlul: Răspuns: 086 Luna
Scris de: Lepadat Mihai-Alexandru din Martie 15, 2011, 07:50:21
Se poate construi in ambele cazuri.


Titlul: Răspuns: 086 Luna
Scris de: Petru Trimbitas din Mai 28, 2012, 09:26:24
Ce are testul 7 ?

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


Titlul: Răspuns: 086 Luna
Scris de: UAIC.VlasCatalin din August 27, 2012, 22:28:19
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  ](*,)


Titlul: Răspuns: 086 Luna
Scris de: Barbu Dorel din Decembrie 21, 2012, 22:11:53
Salutare! Am incercat si eu sa rezolv aceasta problema. Ati putea da un mic hint, va rog :D ?


Titlul: Răspuns: 086 Luna
Scris de: Marian Darius din Decembrie 24, 2012, 11:43:09
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)?


Titlul: Răspuns: 086 Luna
Scris de: Salajan Razvan din Decembrie 24, 2012, 12:47:20
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.


Titlul: Răspuns: 086 Luna
Scris de: Barbu Dorel din Decembrie 27, 2012, 12:18:27
Multumesc de ajutor! Indirect, ultimele doua comentarii m-au ajutat foarte mult :D . 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.:D


Titlul: Răspuns: 086 Luna
Scris de: Andrei Stanciu din Decembrie 29, 2012, 14:42:38
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?


Titlul: Răspuns: 086 Luna
Scris de: Andrei Stanciu din Decembrie 29, 2012, 14:53:08
Ok. nu mai conteaza ](*,) ](*,) ](*,) ](*,) aveam functia de min(a,b) definita gresit...


Titlul: Răspuns: 086 Luna
Scris de: Barbu Dorel din August 12, 2013, 20:22:01
Primul test al evaluatorului este chiar exemplul problemei? Nu iau primul test si multe altele. Dar ma surprinde ca nu-l iau pe primul


Titlul: Răspuns: 086 Luna
Scris de: UAIC.VlasCatalin din August 12, 2013, 22:58:26
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??  :?


Titlul: Răspuns: 086 Luna
Scris de: Barbu Dorel din August 16, 2013, 11:14:37
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?


Titlul: Răspuns: 086 Luna
Scris de: Barbu Dorel din August 16, 2013, 12:57:32
@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 :))).



Titlul: Răspuns: 086 Luna
Scris de: Barbu Dorel din August 18, 2013, 20:41:50
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?


Titlul: Răspuns: 086 Luna
Scris de: Ilie Ovidiu Horatiu din Ianuarie 02, 2014, 14:34:51
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;
}




Titlul: Răspuns: 086 Luna
Scris de: Chiriac Andrei din Ianuarie 07, 2014, 20:42:19
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  :thumbup:


Titlul: Răspuns: 086 Luna
Scris de: Ilie Ovidiu Horatiu din Ianuarie 14, 2014, 22:57:47
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 :D


Titlul: Răspuns: 086 Luna
Scris de: Alpaca Gedit din Martie 26, 2014, 17:08:12
Salut....Se uita cineva pe sursa mea de 25pct va rog?   ](*,) ](*,) ](*,) ](*,) ](*,)
Multumesc :D  =D&gt; =D&gt; =D&gt; =D&gt; =D&gt; =D&gt;  :winner1: :winner1: :winner1: :winner1: :winner1: :winner1:


Titlul: Răspuns: 086 Luna
Scris de: Potra Vlad din Octombrie 07, 2014, 23:31:31
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


Titlul: Răspuns: 086 Luna
Scris de: Patrick Kristian Ondreovici din Iulie 16, 2019, 13:16:58
harta lunii poate arata asa 1 2 2
                                       1 1 1
                                       1 1 1