infoarena

Aici puteţi discuta despre problema Lacusta (http://infoarena.ro/problema/lacusta).

ati putea pune si o explicatie. cum se obtine suma 28? nu reusesc sa inteleg cum se fac acele deplasari. Din ce am inteles eu la o deplasare ma mut pe o linie invecinata in orice coloana, dar asa as putea obtine suma 14 si ar fi mai mica decat 28.

am impresia ca se misca asa
cost 3 +
1 1 - > 1 3  + 5
1 3 - > 2 3  + 3
2 3 - > 2 2  + 6
2 2 - > 3 2   + 3
3 2 - > 3 3  + 3
3 3  -> 4 3  + 3
4 3  ->  4  5 + 2
= 28
sper sa te ajute

idee e ca esti obligat ca pe fiecare linie sa "calci" de 2 ori, si de aceea sunt 2m sarituri si nu poti pur si simplu sa te duci
1-1
1-5
5-5
ca sa obtii 14
LE: in enuntu initial al problemei era si explicatia, si cred ca nu s-ar supara nimeni daca s-ar adauga si in arhiva

S-a rezolvat!  :ok:

Deplasarea se face intotdeauna in ordinea saritura-pas, sau pot avea intai pasul si apoi saritura?

deci cam da

Nu reiese de aici ordinea. Deci pot avea 2 salturi consecutive sau 2 pasi consecutivi (care fac parte din doua deplasari diferite)?

O deplasare = salt + pas. Asta inseamna ca o sa ai o insiruire de miscari salt + pas + salt + pas + salt + pas + ...

Nu poti avea doua salturi sau doi pasi consecutivi (iar daca fac parte din doua deplasari diferite nu mai sunt consecutive... n-am inteles ce ai vrut sa zici cu asta)

In file included from /usr/include/c++/4.2/backward/fstream.h:31,
                 from user.cpp:1:
Asta ce eroare mai este???????????? ](*,)

Ce ai selectat tu este doar locul unde apare problema. Nu este o eroare, ci un warning:
Ti se sugereaza sa folosesti headerul <fstream> in loc de <fstream.h> pentru a scrie cod in conformitate cu noile standarde C++. :)

Se intampa ceva ciudat .. Cand initializez matricea A[20][20] imi da evaluare completa : 0 puncte iar la A[250][250], asa cum ar trebui sa fie matricea imi da eroare de compilare...dar exact cu acelasi mesaj de eroare in ambele cauri (vb  de mesajul care l-am postat mai sus)...PS Acasa merge problema ...rezultatul este 28 pentru exemplul care este pe infoarena..Am rezolvat cu programare dinamica

Eroarea de compilare o primesti din cauza ca nu sunt declarate cout si endl. Incearca sa pui la inceput linia

Ce ma dispera problema daca imi declar doua matrice de 250 iau memory limit exces pe ultimu test iar daca pun 249 iau incorect pe primu test ... asta inseamna ca primu test este de 250/250 si aveti vreun sfat pentru mine ce as putea sa fac ?

LE: Am reusit sa o rezolv .. de 100 chestia era ca trebuia sa imi declar toate variabile unsigned int ca sa scot memoria la mine erau de tip int scz ptr mesajul de dinainte.  Iarasi ma luat gura pe dinainte si mam apucat sa postez pe forum cu toate ca am promis ca nu mai fac asa ceva ...

int si unsigned int ocupa tot atata memorie

Nu cred pentru ca aveam doua matrice de 250 /250 si memoria era la maxim luam si Memory limit exces pe ultimu test iar dupa ce am pus unsigned int a scazut memoria de la 654 la 420 deci cred ca e diferenta astfel nu imi explic de ce a fost asa mare diferenta dupa ce am pus unsigned int.

Am creeat doua tablouri asa:

unsigned char a[252][252];   //252*252*1/1024=62KB
int b[252][252];   //252*252*4/1024=248KB

62+248+cateva variabile int...... sigur e mai putin de 600KB...
De ce Memory limit exces pe primul si ultimul test? Calculez eu cumva memoria folosita gresit?

Incearca sa pui unsigned short :)

Tot imi da "Memory limit exces" pe primul si pe ultimul test....insa nu inteleg de ce.....pt ca dupa calculele mele, eu nu folosesc 600KB de memorie :(.....

LE: Scz....n-am fost atent...acum cand am modificat cu unsigned short imi da "Time limit exceeded." la primul si ultimul test ;))
Cum se rezolva problema?....eu am facut-o in o(m*n^2)......

LE: Am reusit pana la urma 100 in (M*2*n)  :yahoo: ... si am vazut k acum imi incape o matrice de tip char si una de tip int.....asta e cam ciudat....

Stie cineva ce au mai special testele 5 si 9? La alea iau incorect...de ce?

nu prea e nimic special  :-k

cel putin eu nu am intalnit problema asta... mai verifica o data implementarea... poate nu iti gasesti corect valorile alea minime  :)

Imi zice si mie cineva ce este gresit la metoda asta de rezolvare, sa luam exepmlul din problema :
4 5
3 4 5 7 9
6 6 3 4 4
6 3 3 9 6
6 5 3 8 2
initial s=a[1][1]+a[n][m],adica s=5;
apoi incep pe linia n calculez suma de pe fiecare pozitie, adun nr de deasupra, execptand  pozitia m si linia devide : 12 8 6 17 x(unde se afla lacusta),
selectez minimul 6 si apoi pun lacusta pe el, apoi restaurez linia  :)  si urc pe linia n-1.
fac dinou suma  si linia devine 12 9 x 13 10 selectez minimul si tot asa pana ce  linia ==1 unde  ma opresc
La exemplu suma devine  28
Dar pentru exemplu 
5 5
9 1 9 8 8
6 6 9 4 4
1 2 7 9 6
2 6 3 3 8
5 8 2 3 8
Programul meu afiseaza  45 in loc de 42

Pt exemplul asta, drumul optim este: (1,1) -> (1,2) -> (2,2) -> (2,5) -> (3,5) -> (3,1) -> (4,1) -> (4,3) -> (5,3) -> (5,5). Insumand, 9+1+6+4+6+1+2+3+2+8 = 42. Problema se rezolva cu programare dinamica. Ce ai facut tu se numeste greedy, si nu da solutia optima tot timpul, desi s-ar putea sa prinzi ceva puncte. Spor!

Multumesc,da  am  prins  10 pct si la programare dinamica trebuie sa mai lucrez ca nu inteleg nimic din ea , din pacate :(

Stie cineva un site in care este explicata ( pe intelesul oricui )dinamica?

Acilea (http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg)

Se poate afisa testul 1 sau testul 10?....ca deja turbez  ](*,)...am incercat programul meu pe toate testele de la oji 2005 si afiseaza rezultatul corect  si se incadreaza in timp..... :(

ce primesti? WA, TLE sau KBS?

pentru kbs rezolvi daca iti declari matricile de tip short pentru a intra in memorie

Vezi ca ai nevoie doar de ultimile doua linii, nu de toata matricea [ la dinamica ]. Deci, retine doar ultimile doua linii si o sa intre in memorie. Am impresia ca daca declari short matricea de la dinamica, nu o sa iti dea raspunsuri corecte [ pt ca depasesti domeniul de valori  - short e pe 8 biti (nu?) ] Spor!

In gcc short este pe 16 biti.

nu, imi afiseaza  Incorect :P ... assta ma deranzeaza.
Eu folosesc o matrice de tip int :d...:D

cred ca si in borland short e tot 16 biti, ca doar char e pe 8 biti

Am gasit  greseala, la mine  a[n][m] era doar de 101X101, in loc de 251X251 :D.
Dar e un lucru ciudat folosind  functiile din stdio.h ...nu imi aparea KBS11, ci  Incorect si la un moment dat Wa. Dar daca folosesc functiile din fstream , imi apare. Imi explica si mie cineva de ce se intampla acest lucru?
@Marcu Florian  pentru a genera matrice la dinamica n-ai nevoie decat de o varibila, nu de o matrice , sau un vector :P

Cred totusi ca ai nevoie de cel putin patru variabile. ( doua minime pt linia curenta si inca doua minime pt linia anteriora. Si probabil si pozitiile lor (coloanele), deci inca 4 = > 8 variabile) Gresesc? :)

Pai  ai nevoie de  2 varibile pentru  minimile de pe linia anterioara +pozitia "celui mai mic minim :P" + alte 2 minime pentru linia curenta + inca  o varibila pentru pozitia "celui mai mic minim :P", si o varibila pentru construirea drumului curent => 7 varibile :P
[later]:.....am uitat si  un minim pentru ultima linie, da vin 8 :)

sal,dati-mi si mie un sfat..ce trebuie sa fac...treb sa generez toate posibilitatile unui drum,iau din marginea dreapta a matricii si incerc sa gasesc minimele pentru orice drum pe care l-a luat...cum fac asta?

Ce spui tu se numeste backtracking, si nu ti-ar intra in timp sub nicio forma. Problema se rezolva prin programare dinamica. Daca nu stii programare dinamica, iti recomand niste probleme clasice ( a se citi "mai usoare"), precum subsir crescator maximal  (http://infoarena.ro/problema/scmax) (incearca mai intai de 70 de puncte), cel mai lung subsir comun (http://infoarena.ro/problema/cmlsc), suma in triunghi, etc. Ca sa vezi rezolvarea la problema asta, vezi ca exista si un articol cu solutii in arhiva OJI 2005, din sectiunea Downloads. Spor!  :)

mersi...la prog dinamica am inteles cum e treaba la problema cu monede, sau la energii...faci programu sa compuna ceva din ce ai aflat pe parcurs...dar nu vad cum poti aplica aici acelasi principiu

Notezi cu b[ i ][j] - cel mai scurt drum ca sa ajungi pe pozitia (i,j). Evident, rezultatul va fi in b[m][n]. Acum, trebuie sa te gandesti cum poti ajunge in pozitia (i,j). Evident, sunt mai multe variante, asa ca trebuie sa alegi minimul. Spor!

e ok sa fac suma minima dintre configuratii de genu asta , aplicate pe toate liniile si coloanele?

0 0 0 0           0 0 0 0
0 0 0 *   sau   0 * 0 0
0 0 0 *           0 * * *
 
0 0 0 0         0 0 0 0
0 0 * 0  sau  * 0 0 0
0 0 * *          * * * 

Nu. Citeste solutia oficiala si sa o sa intelegi.  :)

Am si eu o intrebare...
Pentru datele de intrare:
2 2
1 2
3 4

Ce raspuns e? Mie-mi pare imposibil pt ca nu ai voie sa faci un pas direct pe campul final (trebuie sa termini cu un salt), si de asemenea trebuie sa si incepi cu un salt...

am si eu o problema...un singur test imi da incorect si nu am idee de ce. Nu are nimeni testele ? ](*,) ](*,)

Testele nu se fac publice din cate stiu eu.  [-X

I-ale de la Downloads (http://infoarena.ro/downloads), sectiunea OJI 2005.
[LE] Skull, daca problema s-a dat la un concurs gen olimpiada, poti sa iei testele pentru ca sunt oficiale :).

sunt tare ciudate testele astea. Am facut tot felul de incercari din cauza ca primeam la ultimul test si la primul test MLE sau Signal 11.
Daca declarati cele 2 matrici ca short de 257x257 si restul variabilelor ca int, o sa functioneze bine

Teoretic nu ar trebui sa functioneze asa pentru ca ar putea fi n=m=250 si toate elementele matricii 250, caz in care depaseste short. Gresesc cumva?

Tipul de date short int retine numere pana la 2^16, deci dacă ai numere pana la 250, ar trebui sa intre.

Da, dar, din cate am inteles eu, el spunea sa declaram si matricea pentru suma minima tot short. 250*250 > 32767. Cred ca merge cu unsigned short.

Imi puteti da niste indicatii de rezolvare? Eu cred ca se rezolva cu ajutorul programarii dinamice dar nu stiu cum....va rog niste indicatii.
Multumesc!

Cauta solutia oficiala. (http://infoarena.ro/downloads)

Incearca sa vezi cum ai proceda pentru cazul cu m=1, iar apoi cu m=2. O sa te prinzi repede  :ok:
Apropo vezi ca in solutia oficiala limitele matricei sunt <= 100. Pe Infoarena 1 < n,m <= 250 deci nu uita sa modifici :)

am luat testele oficiale si pe testul 1 raspunsul meu este exact acelasi cu raspunsul oficial si totusi iau Incorect.
Are cineva vreo explicatie? :readthis:

Incearca sa afisezi cu streamuri .. dunno .. pare destul de ok, sincer ^^

Poate ti se duce de la unsigned short .. nu ar trebui .. nu stiu ce sa zic.
Tine si tu acolo o linie si pune int.

Ai grija ca testele pot fi in alta ordine ( primul de pe infoarena poate fi ultimul dintre cele oficiale ). Poti reduce memoria folosind doar
doua linii din matrice , iar apoi pune int in loc de short. Bafta!

SebiSebi e wa, nu kbs sau tle:-?

Am incercat testele si functioneaza toate...

Pai, nu iei KBS daca iesi din limitele unui tip de date. Eu cred ca tu iei incorect pentru ca depasesti limita short int-ului. Daca pui int
s-ar putea sa iti iasa din memorie , asa ca foloseste doar 2 linii din matrice.  :thumbup:

ok. multumesc  :D

intampin si eu o dificultate similiara :( primul test imi da wa si pe restul am ok, iar pe campion am ok pe toate... any idea, please?

Complexitatea ar trebui sa fie O(N*M) sau O(N*M²)??

Asa dupa tine, cat crezi ca e ?

am facut programu ca si la oji(exact) si i-au memory limit exced.Tot am citit forumul.Are de a face cu tipul datelor sau sa fac numai cu 2 linii.Precizez ca pe toate cazurile de la oji imi da corect

Nu trebuie sa lucrezi cu 2 linii, mie mi-a iesit cu toata matricea.  :) Ai grija la tipurile de date!

De ce nu este valid drumul : (1,1) -> (1,2) -> (2,2) -> (2,3)-> (3,3) ->(3,5) -> (4,5) cu costul minim 27   ??? pentru ca totusi respecta conditiile deplasarii ?

Care ar putea fi cauzele pentru care primesc Memory Limit Exceeded pe primul test? Țin să menționez faptul că am declarat toate variabilele de tip unsigned short int și dimensiunile maxime ale matricelor utilizate sunt de 251x251.

De ce e asa putina memorie? Pe varena sunt 2048 kbytes ...

 :angry: :angry: :angry: :angry: :angry:

traseul asta mie imi da suma 27.
1 1 - 1 2
2 2 - 2 3
3 3 - 3 5
4 5