Aici puteţi discuta despre problema Paznici3.

Aici puteţi discuta despre problema 3secv.

Aici puteţi discuta despre problema Kgon.

Aici puteţi discuta despre problema Flux2.

Cine naiba scrie manualele astea? Sunt de o absurditate strigatoare la cer.

Posteaza in topicul problemei.

Algoritmul de rating e prost, foarte prost. Este in planurile noastre sa il schimbam .

Majuscula, punct, virgula .

Scrie corect. Am reusit sa ma plictisesc in trei randuri.

Din punctul meu de vedere astfel de artificii ar trebui descurajate, cu exceptia catorva ramuri obscure ale industriei.

Hint: Pentru un sir exista un numar liniar de palindroame distincte.

Exista 2 cazuri cand raspunsul pe un test e 0:

1) daca fluxul mai poate fi crescut cu cel putin 1 unitate (in acest caz nu ai nevoie sa folosesti si costurile : o simpla parcurgere de la S catre D e suficienta, tinand cont ca e posibil ca pt a incrementa fluxul global sa fie nevoie sa-l decrementezi pe unele muchii ; anyway, e practic o iteratie dintr-un algoritm de flux maxim fara costuri)

2) daca fluxul nu mai poate fi crescut, dar exista un ciclu de cost negativ in reteaua data (adica costul ar putea fi redus) Pentru a determina daca exista ciclu de cost negativ, fiecare muchie x->y de cost C se transforma in maxim 2 muchii :
-- muchie x->y de cost C daca flux(x->y) < capacitate(x->y)
-- muchie y->x de cost -C  daca flux(x->y) > 0

Cazul 2 e cazul mai greu, deoarece are complexitatea mai mare: teoretic se poate ajunge la O(N^3) sau O(N*(N+M)) folosind algoritmul Bellman-Ford sau Bellmand-Ford-Moore (practic Bellmand-Ford dar cu coada). Eu am implementat destul de eficient algoritmul asta (desi, aparent, ultima versiune submitata nu era cea mai rapida si eram aproape sa iau TLE pe unul din teste).

Sunt curios daca exista o solutie de complexitate (teoretica) mai buna.

Aceasta este si solutia oficiala. Felicitari, Mugurel!

Comenteaza in topicul problemei.

Intre doua noduri S si D exista un numar exponential de lanturi elementare. Backtracking e solutia .

[iostream.h]

Nu am participat la vreun concurs, asa ca nu-mi pot da cu parerea, dar: daca concursul este despre algoritmi si este analizata altceva in afara complexitatii algoritmului, atunci ceva nu-i in regula.

Si eu sunt de acord ca in general toate programele implementate corect care au complexitatea dorita de autori ar trebui sa obtina punctaj maxim. Prin ineficienta eu ma refeream la efortul/timpul necesar implementarii.

Nu pot fi de acord cu: "scrie-l oricum, numai sa fie rapid".

Nu programul trebuie sa fie rapid, ci timpul de implementare sa fie scurt. Un sfat pe care l-am primit in liceu (nu mai tin minte de la cine) era sa scriu cea mai scurta sursa care trece toate testele . Toata povestea asta despre cum e cel mai bine sa implementezi in regim concurs este extrem de subiectiva, si daca ne uitam pe TopCoder la cei mai buni din lume vedem stiluri complet diferite. Totusi, exista lucruri care in programarea reala sunt descurajate, dar care apar foarte des prin sursele concurentilor de la concursurile de programare. Exemple bune ar fi existenta variabilelor globale, sau folosirea excesiva a STL-ului.

Aplicatiile reale sunt mari si astfel de "solutii" duc la cod greu de intretinut/inteles si in final la aplicatii ratate. Viteza nu trebuie sa vina din artificii de programare, ci din algoritm. Artificiile de programare adauga un plus de viteza si ininteligibilitate, de cele mai multe ori.

Desigur, doar ca unui olimpic ii va fi extrem de usor sa scrie cod bun . Nu trebuie invinuite competitiile de algoritmi, care uneori incurajeaza "artificiile".

Ce ma nemultumeste total este tendinta profeorilor de a lucra cu mijloace invechite. Angajatorii nu asta asteapta. Doar un exemplu: iostream.h in loc de iostream, asa cum prevede standardul curent.

Inertie mare, interes mic, etc.

[Variabilele globale]

Variabilele globale nu sunt alocate pe stiva sau heap; este folosita o zona de memorie dedicata. In c++ utilizarea variabilelor globale este descurajata.

Asa este, dar concursurile de programare sunt alta mancare de peste. Daca vei scrie codul conform standardelor acceptate in programare uneori vei fi ineficient.

Asta e vina noastra, nu a bibliotecilor din C++.

Noi nu tinem cont de programa cand facem subiectele. La 11-12 poti sa te astepti la orice .

Da, sigur.

Scopul vostru ar trebui sa fie sa invatati informatica, nu sa va calificati la concursuri. Mi se pare trist ca din ce in ce mai multi elevi se concentreaza pe "ce trebuie sa stii", in loc sa se bucure de placerea de a rezolva probleme. In mod paradoxal, cei care ajung cu adevarat buni sunt aceia pentru care rezultatele si premiile se situeaza pe un plan secund.

Pana la urma, olimpiada este (sau ar trebui sa fie) o modalitate placuta de a ne delecta intelectual. In ultimul timp in Romania mi se pare ca trecem printr-o perioada mai proasta in ceea ce priveste nivelul problemelor propuse. Prea multe structuri de date, prea multe tehnici, prea putina creativitate...

Elevii au ajuns sa lucreze sute de probleme pe infoarena degeaba. Este adevarat ca in ultimii ani gradul de dificultate a crescut continuu la nivel mondial, dar acum mi se pare ca in sfarsit s-a ajuns la un plafon. Sper sa nu fiu inteles gresit, munca este esentiala, dar trebuie ca intentiile care o insotesc sa fie altele.

Spor la treaba si distrati-va mai mult rezolvand probleme! Nu exista retete.

Poate undeva iti iese din vector si scrie peste alta zona de memorie si, deci, conteaza ordinea lor. Incearca sa aloci mai mult.

+1.

Mai mult ca sigur de la asta e.

Aint-ul trebuie sa aiba marimea egala cu cea mai mica putere a lui 2 mai mare decat 2 * MAX_N.

Am marit limita la 0.3

Daca vrei sa inveti programare iti recomand sa iti alegi un proiect open source si sa incerci sa contribui la el.

Nu cred ca e o idee buna. Tinand cont ca a precizat ca el cauta ceva pe langa materia de liceu/scoala, probabil ca mai mult de sintaxa in C nu stie. E imposibil, in opinia mea, sa inteleaga ceva dintr-un proiect. De ce nu scrieti un blog in care sa ghidati cat de cat elevii? Le scrie pe orarul de la scoala "Informatica" si ei chiar cred ca fac Informatica.

@Flaviu
In cazul in care nu ai un profesor cat de cat decent nu are rost sa te strofoci, iti sugerez sa iei mai degraba matematica in serios pana ajungi la universitate. Esti probabil in aceeasi situatie in care am fost eu, si destul de des posteaza elevii intrebari de genul acesta, vad ca chiar nu le pasa, siteul acesta este mai mult destinat celor initiati, nu este niciun fel de ghid pentru neintiati.
Peisajul e urmatorul, tu acuma vezi limbajele de programare ca si o lume virtuala in care poti sa faci anumite actiuni conform anumitor reguli. Ai citit in manual de la clasa despre un set de reguli si crezi ca iti ajungi setu ala si esti ok. Limbajele acestea sunt facute pe baza a unor notiuni abstracte care trebuiesc stiute in cazul in care nu vrei sa faci debugging ore in sir.

Nu exista alta metoda sa inveti sa programezi decat sa incepi sa programezi. Este foarte greu la inceput, mai ales daca nu exista cineva care sa te indrume.

Am primit problema ta si ti-am raspuns pe mail. Daca mai vrei sa propui, mai trimite-ne un email la aceeasi adresa.

Daca vrei sa inveti programare iti recomand sa iti alegi un proiect open source si sa incerci sa contribui la el.