Avand in vedere numarul mare de probleme care se propun pe campion, e destul de greu sa gasesti la fiecare runda probleme noi si interesante. Problemele frumoase de informatica nu iti vin in minte chiar in fiecare zi iar uneori chiar e foarte greu sa aduni un set de astfel de probleme. In orice caz nu vad care e problema, atata timp cat problemele sunt adecvate grupei de concurenti la care s-a dat si poti sa faci o departajare corecta in functie de asta eu consider ca problema si-a indeplinit scopul (chiar daca era copiata).

Gandeste-te in felul urmator, ti se pare normal ca la clasa a 9-a sa zicem, sa dai sa se calculeze subsecventa de suma maxima dintr-un sir? E un algoritm clasic, numai bun atunci cand vrei sa departajezi pe cei care stiu cat de cat ceva de cei care nu stiu absolut nimic. Si totusi problema asta se gaseste probabil in toate arhivele de pe toate online judge-urile din lume. E clar ca nu e o problema originala, insa scopul tau e sa dai o problema cu care sa departajezi concurentii.
Acuma probabil o sa intrebi ca "bine bine, dar daca unii concurentii stiau problema dinainte de pe sgu atunci nu cumva risti sa faci o departajare proasta?". Nu prea, e normal sa ai un mic avantaj daca ai lucrat mai mult. La fel de bine ai putea spune acelasi lucru si daca eu lucrez toate problemele de flux de pe infoarena si la oni primesc un flux. E foarte probabil ca eu sa rezolv acea problema. O sa zici cumva ca autorii problemelor m-au avantajat pe mine ca au dat flux? Nu, pentru ca un concurs e format din mai multe probleme care intr-un final vor face o departajare clara si vor stabili cine e mai bun. Si avand in vedere numarul mare de probleme date la campion pana sa se stabileasca lotul care merge la finala, e destul de clar ca in clasamentul final vor conta skillurile pe care le ai in toate categoriile informaticii. Faptul ca ai stiut sa faci o problema pentru ca o stiai dinainte de pe sgu nu o sa iti aduca calificarea in runda finala.

[offtopic] @Spiderman si Dani: Lasati omul in pace pentru ca a procedat corect. Solutiile nu se pun pe forum pentru a nu strica distractia celorlalti (nu stiu daca ati observat dar asta e una din regulile acestei sectiuni a forumului, stiu ca multa lume o incalca insa ea exista si ar trebui respectata). Daca solutia lui nu va fi buna, adminii vor vedea acest lucru si vor scoate solutia lui de acolo. De asemenea adminii au dreptul sa vada toata sursele trimise , deci paul inainte de a ii da aprobarea sa scrie solutia putea sa se uite pe sursa lui si sa vada daca e sau nu buna (nu stiu daca chiar a facut asta dar nu are importanta). O sa va rog ca de acum incolo sa nu mai folositi forumul infoarena pentru dispute personale si sa va respectati colegii de studiu oricine ar fi acestia. Daca vreti sa va certati folositi IM/Hi5 sau alte instrumente  care au fost facute pentru asa ceva, nu infoarena. Infoarena a fost facuta pentru a ajuta elevii sa devina mai buni la informatica, daca postul nu are ca scop acest lucru atunci o sa va rog sa il tineti pentru voi.

O sa bag si eu un ultim post in discutia care intr-adevar e putin offtopic.

Mie imi place filmuletul postat de gabitzish (ai un + la karma de la mine). De ce imi place? Imi place deoarece e una din rarele ocazii cand vina pentru ce este in tara nu mai este aruncata pe clasa politica, ci pe oameni, si mi se pare ca asa ar trebui sa fie. O ducem rau in Romania? Da o ducem rau. E vina politicienilor? Poate. E vina oamenilor? Cu siguranta.

@Apocalypto: Sa dai vina pentru limbajul colorat folosit in viata de zi cu zi a oamenilor pe faptul in pozitiile importante erau adusi oameni fara valoare este pur si simplu absurd. Noi ca oameni ar trebui sa invatam sa traim intr-o societate si sa decidem cum putem sa imbunatatim tara in care traim, fara sa asteptam ca oamenii pusi in "pozitii importante" sa faca totul.

Daca vreti sa continuam discutia am putea face un thread nou si sa mutam toate posturile acolo.

Sunt mai multe chestii pe care le putem face pentru a evita rezolvarea hardware a problemei, vom incerca sa vedem ce merge mai bine .
In orice caz echipa infoarena este destul de alertata de problema aceasta si promitem sa facem ceva in privinta asta pana la urmatorul concurs.

Intr-adevar se pare ca nu am fi avut aceste probleme daca nu ar fi fost monitorul de evaluare. Va trebui sa gasim o solutie acolo. Problema principala e faptul ca numarul de surse stocate pe infoarena a devenit absolut imens iar de fiecare data cand se face request la monitor trebuie sa facem un query intr-un tabel 600 000 de entry-uri, ceea ce e foarte mult. Vom incerca sa gasim o solutie sa facem monitoru ala sa se incarce mai repede ca vantu.

@Cosmin,Vali: Cacheuiesti cam degeaba avand in vedere ca vorbim de o pagina care e intr-o schimbare constanta. E drept ca sunt anumite linii care nu se schimba insa nu prea ai cum sa iti dai seama care.

@Coty: Da avem indecsi pe tabele

@Coty: Distribuirea ar fi solutia perfecta pentru long-term in cazul de fata, insa acest lucru nu se face chiar asa usor. In general daca vrei sa construiesti un site cu o baza de date distribuita trebuie sa il construiesti astfel de la bun inceput, iar infoarena nu a fost conceput pentru asa ceva. Adaptarea unui site care nu a fost gandit sa fie distribuit la un astfel de sistem e aproape imposibil.

@Everybody: Tin si eu sa imi cer scuze in numele echipei infoarena pentru tot ceea ce s-a intamplat. Vom incerca sa investigam problemele aparute in timpul concursului si sa gasim o solutie.

Mindblowing http://www.boingboing.net/2010/11/30/san-franciscos-steep.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+boingboing%2FiBag+%28Boing+Boing%29&utm_content=Google+Reader (si cand ma gandesc ca ma plimbam cu bicicleta prin san francisco pe drumurile alea)

@Spiderman: E bine ca de acuma cand mai repari ceva sa te uiti la revizia care era inainte de a se strica pagina. Ce ai corectat tu nu avea sidebar.

@toni: Esti sigur? Nu stiu ce solutie ai tu dar sunt destul de sigur ca merge si cu deque. De altfel as fi curios cum o faci fara deque.

Daca nu vrei sa inveti C/C++ asa cum ti-a recomandat toata lumea aici (e drept ca esti cam mic si la varsta aia pascalu pare mai usor de inteles decat C/C++) incearca incearca Delphi. E un program in care poti sa faci o interfata destul de ok si merge pe sintaxa de pascal.

Din cate vad problema aceasta nu are un evaluator atasat. Poti sa dai un exemplu in care ar exista mai multe solutii?

Cred ca e din cauza unui common mistake la ciur.

Cod:

for (i=3;i<=100000;i=i+2)
        if (a[i]==0)
            for (j=i*i;j<=100000;j=j+2*i)
                a[j]=1;

Aici, in momentul in care i ajunge la 50 000 sau ceva de genu, j = i * i va iesi din int si va face overflow => j-ul va deveni un numar negativ iar cand faci a[j] = 1 => Killed by signal 11.

Mi se pare ca ar trebui sa fie mai multe siruri ptr n=5 de ex sirul MAMAM respecta conditiile din enunt.

Din cate imi aduc aminte parca problema asta se facea cu flux. E posibil sa mearga si greedy-uri dar nu stiu daca sunt corecte.
Gandeste ca momentele de timp de la 1 la 100 sunt noduri intr-un graf iar cei N voluntari reprezinta muchii intre aceste noduri, practic daca un voluntar poate sa fie ghid in intervalul a b, ai muchie de la a la b. Iar acum problema s-a redus la gasirea a K drumuri distincte de la nodul 1 la nodul 100, problema care se rezolva cu flux.

Ai putea sa ne zici cum faci si abia apoi o sa putem sa te ajutam.

Vad ca a inceput o miscare de ceva vreme sa se tot dea linkuri pe forum catre arhive cu testele oficiale. Ei bine acest lucru nu e tocmai ok, ideea nu e sa treci toate testele, ideea e sa rezolvi problema corect. Nu vrei sa stai 2 zile pe un bug? Bine i-ati testele si vei descoperi imediat acel bug insa e foarte probabil sa repeti acel bug. Sa stiti ca si statu 2 zile pe un bug ajuta, pentru ca odata ce l-ai gasit iti va ramane in minte si nu il vei mai repeta. Incercati de acuma sa dati hinturi de rezolvare si sa nu mai trimiteti oameni direct la teste sau la solutia oficiala, exista un motiv pentru care echipa infoarena nu a facut testele si sursele publice la toate problemele.

Ah, la primul post pe care l-am dat am crezut ca update-urile sunt pe fiecare element nu pe interval. Pai in cazul asta in vectorul B tii minte ce update-uri ai facut (ma rog cred ca iti mai trebuie un vector aici pe care sa tii minte suma initiala pe fiecare bucata). In momentul asta cand faci query-ul pe 6-8, o sa parcurgi manual toate elementele, iar pentru 6 si 7 o sa vezi ca sunt 0 in A insa o sa vezi in B ca ai facut un update pe bucata respectiva si deci o sa aduni la valoarea din A valoarea respectiva din B la fiecare element.

@dacusorul: Avem o sectiune separata pentru teme in cadrul categoriei informatica. Ti-as sugera sa iti postezi temele de la facultate si de asemena sa incerci sa le postezi intr-o maniera mai usor de citit (de genu vreau o gramatica care sa imi dea cuvintele cu numar par de 0-uri sau ceva de genu) nu sa dai copy paste la ce a scris profesorul pe tabla. Ai mai postat un post de o natura asemenatoare si despre automate, iar infoarena nu e locul unde sa iti faci temele la informatica. Te putem ajuta dar pentru asta trebuie intai sa incerci sa le rezolvi singur, nu sa ajungi acasa sa postezi tema pe infoarena si apoi sa o iei de aici inainte de a pleca la curs.

De fapt calculezi manual cu for de la st pana la primu numar de forma k * sqrt(n). Apoi incepi sa mergi din sqrt(n) in sqrt(n) pana ajungi la cel mai mare numar care e multiplu de sqrt(n) dar mai mic decat dr. De acolo calculezi din nou manual pana la dr. Worst case o sa ai complexitatea 3 * sqrt(n) = O(sqrt(n))

Da iei minimul, parvu asta e cam neatent
Eu parca sa zic ca am vazut-o la o nationala pe la gimnaziu.

@parvu: la pointerii aia cred ca vroiai sa zici cel mai mic element din V care inmultit cu X (X = 2, 3, 5) sa fie mai mare decat V[k]. Cum ai zis tu toti pointerii ar fi pe V[k].

Singura soluție care ar merge în acest moment ar fi să schimb structura testelor, ceea ce ar însemna ca toată lumea să retrimită soluțiile => nu merită. Cum a zis și Mihai, pentru ciur există o problemă separată, ideea acestei probleme fiind cu totul alta.

Îmi cer scuze pentru neplăcerile cauzate.

Admini pot reevalua problemele daca numarul de surse nu depaseste o anumita limita. M-am uitat acuma si vad ca la problema asta numarul de surse nu depaseste acea ca poti sa schimbi testele si sa rogi un admin sa reevalueze.

In infoarena 3 deja avem de gand sa implementam si feature-ul spus de spiderman cat si sa introducem java.

S-a introdus la un moment dat optiunea de chat (e o componenta de smf) si nu a mers. Poate ar trebui sa o reactivam sa mai incercam odata, poate comunitatea a mai crescut intre timp.

Si eu sunt de acord cu Bogdan insa cred ca din alte motive.
Mi se pare ca acest feature de karma merge pe forumurile cu un user-base mult mai mare decat al nostru (unde sunt in jur de 1000 de membri activi zilnic) deoarece astfel ar chestiile de genu userul X are ceva cu mine si imi da minus intr-una, conturi multiple ca sa iti dai + la karme and so on ar deveni nesemnificative in momentul in care zici o chestie cu adevarat desteapta si iti vin 500 de plusuri.

O alta solutie ar mai fi ideea celor de la Facebook si anume sa existe doar plus, nu si minus. Daca ti se pare ca respectivu a zis o chestie desteapta ii dai plus, daca nu iti vezi de treaba. Practiv motivele pentru care noi vrem sa scoatem feature-ul de karma sunt motivele pentru care ei nu adauga un buton de dislike.

To sum up daca am reusi relativ usor sa nu mai poti sa dai minus I'd give it a try, altfel as scoate tot feature-ul deoarece strica user-experience-ul.

Mai bine propui chestia pe forumul smf. M-am gandit si eu la chestia asta intr-o zi, nu stiu exact cat de greu e, adica din punct de vedere logic in mintea mea nu ar trebui sa fie foarte greu, insa ar trebui sa faci modificari pe structura bazei de date de la smf si implicit sa updatezi tot codul. care e destul de stufos, sa mearga dupa noua structura ceea ce probabil ca nu e chiar asa usor, mai ales ca nu e o componenta dezvoltata activ de membri infoarena deci codul de acolo inca e un oarecare mister pentru noi.