infoarena

Aici puteţi discuta despre problema Expresii min-max (http://infoarena.ro/problema/emm).

va rog...dati un exemplu mai complicat...sa vad ce nu imi iese...iau 40 de pct....restu WA

Fii atent la codurile pe care le-ai atribuit operatorilor 'm' , 'M' si parantezelor, s-ar putea sa fie aceleasi cu unele numere din fisier.   
Uite si un mic test:
Nu prea sunt teste complicate , trebuie doar sa fi atent la implementare. Sper sa ajute.

Buna am facut si eu problema asta si am o mica problema. Iau TLE la 7 teste ma poate ajuta cineva? id-ul meu de mess este bogdanpopescu88

7 TLE? Faci recursivitate? Adica cum dai de o "(" mai apelezi odata functia care rezolva o expresie gen "5m3M1"? Chiar nu vad cum ai putea sa iei TLE, mi se pare destul de liniara treaba :P

Later edit: Vezi sa nu-ti ruleze la infinit pe anumite cazuri, mai fa niste teste.

Da asa am facut.....cand am gasit o paranteza am apelat inca o data functia

Atunci incearca un test de genu

Am folosit recurenta! Am testat si cu teste de genu cum ai spus Cosmin, imi da bine, dar depaseste timpu.....ce pot face pt a optimiza? id-ul meu de mess este bogdanpopescu88

Ma ajuta si pe mine cineva?

Poate te ajuta http://en.wikipedia.org/wiki/Shunting_yard_algorithm. Poti transforma sirul in notatie poloneza, care se evalueaza foarte usor si intra in timp.

Unul dintre exemplele din enunt este
12m23M13m192)M(90m89m88m87)m((298M7)M2)     si raspunsul e 87....

nu ar trebui sa fie parantezat corect,  avand in vedere ca prima paranteza intalnita este ")" ? :-s

Ba da, am corectat.

M-am saturat am facut problema in toate felurile si iau TLE (numa 65 de puncte). Imi poate da si mie cineva vreo idee cum o pot face fara sa mai iau TLE? (cineva care a facut-o va rog)

Ti-am dat un link unde practic ai algoritmul de rezolvare... ai incercat sa-l implementezi?

De transformat in expresie poloneza e usor...dar imi spui dup-aia cum fac? ca imi va depasi timpul daca fac cu un vector

Pai descrie exact cum faci. Transformarea o faci nerecursiv, iar evaluarea la fel. Pentru evaluare iti mai iei o stiva, parcurgi vectorul in care ti-ai format sirul in notatie poloneza, iar in momentul in care pui un operator in acea stiva, vei avea operanzii deja adaugati, deci ii scoti din stiva, calculezi, adaugi rezultatul inapoi in stiva, iar la sfarsit stiva va contine o singura valoare: rezultatul care te intereseaza.

Ideea asta e, cu asta am luat 100... poate te complici pe undeva, da si tu mai multe detalii si incerc sa te ajut.

Sau in aproape orice culegere gasesti evaluarea unei expresii(folosind recursivitate)... e cam aceeasi chestie, daca urmezi modelu' iti iasa sigur!

Deci eu am incercat asa: am facut o procedura care sa calculeze rezultatul de la pozitia i pana la j. cand am dat de o paranteza deschisa am apelat procedura, dupa care stergeam tot ce era in paranteza din sir si adaugam numai rezultatul.......programul mergea foarte bine numai ca imi da TLE la 7/20 de teste

Eu am o variabila i globala  care imi zice pana la ce pozitie am evaluat, si o functie recursiva care returneaza rezultatul pana in acel moment daca  intalneste ')' sau daca i = n. Ea rezolva o operatie gen 1m2, sau 4M5, si daca da peste o situatie gen 1m(...... face rez = min(rez, solve()), inainte sa apelez solve() trec cursorul i dupa '(' .. Deci am O(n), atat doar ca se cam incarca stiva. :) Sper ca ai inteles, asa tre sa mearga. 

Desi cel mai elegant e cu notatie poloneza :P Si trebuie sa intre in timp.

Am implementat in expresie poloneza asa cum mi-ai spus...si de ex pt testul 178m66m234M89m54M13M22m67 in expr poloneza da 178 66 234 89 54 13 22 67 m M M m M m m nu? e bine pana acum.......si acum daca evaluez expresie si iau pentru fiecare m sau M intalnit numerele cele 2 din fata imi da alte rezultate decat cele de la teste!!! Ce nu e bine? Unde gresesc?

Nu e buna forma poloneza, citeste mai cu atentie algoritmul. Trebuie sa-ti dea 178 66 -1 234 -1 89 -2 54 -1 13 -2 22 -2 67 -1, unde -1 = m, -2 = M. Operatorii au aceeasi prioritate.

Chiar daca nu are legatura cu subiectul in discutie, vreau si eu sa stiu cum pot accesa solutii ale problemelor din arhiva.  M-am lovit de urmatorul mesaj in incercarea mea de a ma uita la evaluator (nu stiu daca e unul si acelasi lucru cu rezolvarea unei p robleme):

"Nu ai permisiuni suficiente pentru a executa aceasta actiune! Te redirectez ..."

Si normal ca asa-zisa
"redirectare" nu a mai avut loc.

Multumesc anticipat,
Bogdan. :angry:

Calmeaza-te! Probabil problema urmeaza sa fie pusa in arhiva. De fapt, problemele. Akum cred k se fak ultimile "retusuri".  :-'

Daca zici ca vrei sa accesezi solutii ale altor concurenti, nu ai voie din cate stiu eu...  [-X Daca e vorba de solutia ta, atunci e o problema... asta o primesc si eu uneori, e posibil sa fi modificat oarecum regulile legate de securitate de pe site ... Si redirectarea trebuie sa vina, nu te duce pe pagina principala?

ce e cu testele 16,17,18..ca iau tle iar la restul am niste timpi asa de mici  :'(

Daca ai facut recursiv mai mult ca sigur iti intra in ciclu infinit.

da e  recursiv..da de ce sa intre in ciclu infinit ? :'(

Pai nu stiu, verifica citirea, marimea vectorilor, fii super atent la implementare. Daca nu rescrie sursa, sau daca nu incearca solutia iterativa cu stiva.

Cred ca e o conspiratie... si io am exact aceleasi probleme ca si robytzza

mishu cand scoti 100 ma anunti ;)  :peacefingers:

am trimis aproape aceeasi sursa(logic, q modificarile de rigoare) ca si la evaluarea de expresie din arhiva educationala si iau 85 cu 3 TLE iar la evaluarea expresiei iau 100 destul de lejer  :? oare, oare, ce-o fi oare?

LE: pan' la urma am scos 100  :yahoo: (refacand  cu totu' alta idee evaluarea) da' tot nu inteleg d c luam numa 85 inainte

Cum poate sa incapa intr-un sir de 100.000 elemente numarul 1.000.000 ?

Numarul 1.000.000.000 incape intr'un sir de 10 elemente. Fiecare cifra e un element.
Mai explicit: c[0] = 1; c[1] = 0; c[2] = 0; [...]; c[9] = 0;

Ce contin testele 13 si 19? Iau WA pe ele si restu dau bine. Am folosit RPN(Reversed Polish Notation). :-k

Doar de precizare. La emm e o greseala in text. Randul 3:"daca un sunt paranteze". Nu este nu in loc de un? Doar de verificare.

Se pare ca am mai pus intrebarea asta acum 4 ani.
Banuiesc ca raspunsul la intrebarea mea este ca nu pot vedea nicio rezolvare a problemelor propuse in concursuri...bummer!

Ok...multam.

Poate da cineva mai multe teste? Exista teste speciale, gen mai multe paranteze deschise decat inchise sau paranteze care sa nu contina expresii? Nu reusesc sa iau decat 70 de puncte cu WA pe 3, 5, 6, 8, 10 si 13.

http://www.infoarena.ro/job_detail/995083 (http://www.infoarena.ro/job_detail/995083)

Nu sunt astfel de teste. Te-ai complicat prea mult cu programul cela. Problema este foarte simpla si se face cu evaluare de expresii. Aceasta se face cel mai simplu cu recursie indirecta. Codul e foarte scurt si comod + complexitate liniara. Iti recomand mai intii sa faci problema cu evaluare de expresii din arhiva educationala si ai sa vezi ca asta e floare la ureche.  :)

Salut!
Personal iti sugerez sa incerci varianta a doua din arhiva, cea cu nivele de prioritate in care doar schimbi operatorii "+-" cu "Mm". Mie mi-a mers perfect!
La aceasta sursa ma refer: http://www.infoarena.ro/job_detail/144801?action=view-source. Bafta!

Am reusit s-o fac. Toata problema era la citire. Multumesc pentru ajutor :)

Ce au testele 13 si 19...vre-un caz mai ciudat sau ce e...doar alea imi dau incorrect ](*,) ](*,) ](*,)