Ce e codificarea echipei? Numele echipei? Pot sa schimb numele echipei?

Eu nu va inteleg, sincer. Majoritatea dintre voi stiti foarte bine ca streamurile sunt mai incete decat functiile standard si totusi continuati sa le folositi in concursuri ca sa veniti dupa aia sa va plangeti ca nu ati luat 200.

@fm_strategy: Operatia modulo este o operatie foarte inceata, deci rezolvarea ta la prima problema nu este mai eficienta, ba chiar este mult mai ineficienta.

Din cate stiu eu cel mai bun algoritm e N^3. Sunt mai multe metode de a face asta si majoritatea se bazeaza la reducerea matricii la o forma triunghiulara (toate elementele de deasupra sau de sub diagonala principala sunt 0). Mai multe detalii poti sa gasesti aici http://en.wikipedia.org/wiki/Gaussian_elimination.

In primul rand am impresia ca pe testul 4 8 algoritmul tau o sa dea 2 (nu iei in calcul ca cmmdc poate fi chiar unul dintre numere). De asemenea algoritmul tau e ineficient. Pentru o rezolvare eficienta cauta algoritmul lui Euclid.

In primul rand nu inteleg de ce ai nevoie de 3 numere cand tu vrei sa calculezi cmmdc-ul a 2 numere :-" (deci ai o greseala in gandire aici).
In al doilea rand algoritmul e foarte ineficient. Daca incerci sa calculezi cmmdc-ul a nr destul de mari algoritmul tau va face foarte multe operatii si va dura foarte mult. Nu folosim algoritmi complicati doar ca se ne aflam in treaba sau ca sa ne dam noi mari, ci pentru ca sunt mai rapizi.

Interesant, nu ar trebui sa poti sa faci asa ceva. Nu iti inteleg exact motivatia pentru care vrei sa scrii in fisiere auxiliare (nu inteleg de ce ti-ar fi mai simplu asa), insa acest lucru nu este permis la olimpiade si nu ar trebui sa fie permis nici pe infoarena.

[offtopic]
Debuggerul nu e neaparat mai productiv.

Observ din ce in ce mai mult o tendinta a elevilor in romania de a nu mai pune mare importanta pe implementare. Am vazut elevi care doar citeau problema, scoteau solutia si nu o mai implementau. Sau cand implementau stateau cu mii de variabile in watch. Si dupa olimpiada va plangeti toti si faceti clasamente cu cat ati fi avut daca nu ati fi busit implementarea. Sau elevi care ziceau ca "am luat 100 dar daca nu busheam luam 250 si intram in lot". Hai sa va zic o chestie. Busheala face parte din skill, un skill care se creaza implementand multe probleme si obisnuindu-va sa scrieti problema curat din prima. De acea e mai ok sa folosesti printf-uri in loc de debugger. O sa va obisnuiti sa va ganditi codul in timp ce il scrieti, sa nu mai scrieti chestii de aiurea in cod avand in cap ca "daca e gresit o sa il vad cu debuggeru". Inteleg sa il folositi in concurs, cand chiar conteaza sa iti gasesti repede greseala, insa cand esti acasa si nu te preseaza nimeni va recomand sa folositi printf. E un fel de a antrena cu o mana la spate.
[/offtopic]

Incearca (*it).second

Ai putea sa incerci sa deduci si singur formula, nu e chiar asa complicata, asta denota mai mult faptul ca nu ai inteles algoritmul. De altfel formula pe care o folosesti este ineficienta.

rmq[i ][j] = minimul pe sirul care incepe la pozitia j si are lungime 2^i
rmq[i ][j] = min(rmq[i - 1][j], rmq[i - 1][j + 2 ^ (i -1)])

Nu e din cauza ca numarul de intoarceri e prea mic. E din cauza ca fiecare numar va fi procesat o singura data. Algoritmul e echivalent cu urmatorul algoritm. Trec prin fiecare element in parte si il adaug intr-o stiva. Vreau sa mentin acea stiva sortata descrescator, astfel ca daca elementul din varful stivei e mai mic decat elementul pe care vreau sa il bag acuma incep sa scot din stiva pana cand in varful stivei ramane un element mai mare. In acest moment elementul din varful stivei este de altfel si primul element din stanga mai mare decat el (pentru dreapta faci la fel). De ce e acest lucru O(N). Simplu, pentru ca fiecare element intra in stiva o singura, si iese o singura data. E drept ca poate parea mai mult din cauza ca la fiecare pas trebuie sa mai si scoti niste elemente din stiva, insa gandestete ca suma numarului de elemente pe care le scoti e N.

@Vlad Tarniceanu: Ba da. Am spus si mai sus, complexitatea optima este O(N).

Hint: Ca sa calculati primul turn din stanga/dreapta strict mai inalt folositi o stiva (e un algoritm destul de clasic). Acum ca sa determinati maximul pe intervalul vizibil din turnul incercati sa va folositi de elementele pe care turnul i le-a scos din stiva.

Poti sa tii niste sume partiale si astfel sa calculezi recurenta in O(1)

Pentru 100 de puncte trebuie O(N).

@Sebastian: Fara comentarii.
@Vald: Da, trebuie sa iei in considerare si turnul de inaltime 3.

@Florin: Fara comentarii.
@Adrian Craciun: Fara comentarii. Citeste mai bine enuntul.

@Alx: Nu, turnul 3 nu este vizibil de pe turnul 1.
@Vlad: Nu, de pe turnul 3 nu poti vedea turnul 1, in exemplul dat de tine.

Totdeauna trebuie sa existe o penalizare

Fara comentarii.

Am updatat enuntul. Imi cer scuze pentru neplaceri.

@George Popoiu: 150 de milioane de instructiune e mult pentru o secunda. Nu poti sa verifici cu un simplu for de genul acela timpul de rulare pentru un anumit numar de pasi deoarece c++ mai optimizeaza si el. De ex:

Cod:

a = 0;
for (int i = 1; i <= 1000000000; i++) a++;

Va merge destul de repede iar a va avea valoarea 1 000 000 000 deoarece c-ul si-a dat seama ca acea instructiune e echivalenta cu a += 1000000000.

In general eu foloseam ca golden rule 30-40 de milioane pentru 1 secunda, 1-2 milioane pentru 0.1 secunde.

@Liviu: Mergea sa anuntati asta oleaca mai din timp . Can't wait.

Nu stiu exact ce ar merge imbunatatit la design, doar ca e am dureros asa la ochi galbenu ala pe verde.
Nu poti sa iti pui pe pagina de profil ca sunt dezactivate tagurile de html din textile. Ca sa poti sa faci ar trebui sa faci un macro (in codu infoarena) pentru asta, ceea ce nu e chiar asa greu, dar tre sa fii putin mai implicat. Daca vei poti intra pe hackers.devnet.ro/wiki si e acolo un tutorial despre cum sa downloadezi codul infoarena. Daca ai ceva nelamuriri poti sa imi trimiti un pm si o sa incerc sa te ajut in masura in care pot. Banui ca din moment ce ai reusit sa faci widgetu asta ai cunostinte cel putin elementare de web development.

Cool. Sariti cu + pentru initiativa. Ar mai merge putin la design dar e super ideea.

De curiozitate, de ce te-ai dus la o facultate de mate info daca nu ai facut mate in liceu? Si cum ai trecut admiterea?

Te sfatuiesc sa iti cauti manualele de liceu de matematica sau sa iti rogi colegii sa te mediteze. De curiozitate despre ce facultate/universitate vorbim?

Ideea e ca pentru fiecare numarul din vectorul vrei sa afli primul numar din stanga si din dreapta lui care sunt mai mici de cat el (practic vrei sa construiesti un dreptunghi cu inaltimea egala cu elementul de pe pozitia si vrei sa vezi cat de mult il extinzi). Acuma pentru a afla pentru fiecare numar primul element din stanga mai mic el, bagi pe rand elementele intr-o stiva sortata crescator. Ideea e ca atunci cand adaugi un element in stiva, scoti din varful stivei elementele mai mari decat el. Dupa ce ai scos toate acele elemente, elementul din varful stivei e fix primul numar din stanga lui mai mic decat el. Faci fix la fel ca sa gasesti primul element din dreapta mai mic decat el.

[va incerca]

Zice bine Cezar. El se referea la faptul ca in cazul functiilor recursive nu are nici un efect. Inline poti in principiu sa il pui la orice tip de functie doar ca nu intotdeauna va avea si efect. Prin inline compilatorul va incerca sa copieze codul functiei acolo unde e apelata, eliminand astfel overheadul creat de apelul functiei (overheadul asta e mic insa daca apelezi de 1 milion de ori functia maxim(a, b) o sa conteze). Problema e ca in cazul anumitor functii (din pacate nu stiu exact conditiile) compilatorul va ignora acel inline pentru ca nu poate copia codul acolo (cum e cazul functiilor recursive). Pare destul de bine explicat aici care e smenu cu functiile astea http://www.parashift.com/c++-faq-lite/inline-functions.html#faq-9.3 (nu am gasit insa si conditiile ca acel inline sa aibe efect).