Hai romanii! 

Bravo! Cel mai bun rezultat al Romaniei de multi ani!

Functia delta este data de tabelul de mai jos. Prima coloana reprezinta nodul sursa, iar ultimele doua reprezinta nodurile destinatie in functie de caracterul citit (a sau b).

Hai baietii! 

Nu cred ca intelegi rostul acestei categorii a forumului. Noi nu ajutam cu teme aici ca sa ne distram in timpul liber, ci ca sa ajutam oameni seriosi sa-si dezvolte cunostintele la informatica.

Aaaa, numa' atat?

Da.

Comentarii la postul Remember Mihai Patrascu.

Este probabil omul cu cele mai importante rezultate din comunitatea romaneasca de olimpici la informatica. Odihneasca-se in pace!

Susțin cu desăvârșire opinia lui wefgef.

Bacul nu ar trebui modificat, ci scos de tot, cu sau fără informatică, nu e prea mare diferență.

De ce?

Unde sunt rezultatele?

Like a sir!

Imi place mult ideea acestui top, te ajuta sa gasesti probleme interesante din arhiva fara prea mult efort. De aceea voi mentiona si eu 10 probleme care mi se par tari (nu neaparat cele mai tari) si pe care nu cred ca le-a mentionat cineva pana acum:

• Telegraf - smechera problema, n-am avut nici o idee cum s-o abordez initial
• Dreptunghiuri - rupere cu cunostinte de clasa a 9-a
• Cerc - interesant ca se reduce la o problema de grafuri si la teorie nu prea des intalnita in probleme
• Obiective - grafuri, arbori, algoritmi, structuri de date, tot ce vrea sufletul
• Ndap - o dinamica 3^n misto
• Copaci3 - relativ simpla rezolvarea, greu/interesant de demonstrat de ce e corecta
• NKPerm - o abordare neobisnuita pentru problemele cu stari
• Trenuri - subiectiv: pentru ca am venit o rezolvare misto la problema lui Alex, motiv pentru care a ajuns sa fie o problema tare de lot
• Posta - imi place genul asta de probleme (greedy + structuri de date) avand input destul de minimal
• Gard4 - interesant modul de utilizare al configuratiilor, desi problema nu e atat de dificila

Dintre problemele care au mai fost mentionate imi plac foarte mult Cabane si Reg.

Pentru ca daca ai folosi acelasi modulo, nu ai miscora deloc probabilitatea unei coliziuni.

Daca intrebi de ce se folosesc uneori doua sau mai multe hash-uri, raspunsul e urmatorul: daca functia ta hash genereaza numere uniform in intervalul [0, M1), atunci ai probabilitate 1/M1 pentru o coliziune. Daca mai adaugi o alta functie hash independenta de prima care returneaza numere uniform in intervalul [0, M2), atunci probabilitatea unei coliziuni scade la 1/M1 * 1/M2. Poti sa vezi tehnica asta ca si cum ai creste intervalul in care returneaza functia hash valorile la [0, M1*M2), dar in acelasi timp eviti calculul pe numere mari.

Si, si, dar problema mai mare a fost TLE-ul.

Eu cred ca e destul de folositor sa avem asta.

Sunt foarte de acord cu ideile prezentate in acest post.

In plus, la intrebarea: "Pot fi astfel de experienţe, dacă nu evitate, măcar minimizate?", cred ca un alt raspuns foarte bun este "Prin exercitiu." (Atentie, aici ma refer la eveniment in sine si nu la antrenarea calitatilor oricum necesare pentru eveniment.) Voi doua doua exemple mai jos pentru a ma face inteles:

1. Un antrenament util pentru un interviu de job este chiar sa dati mai multe astfel de interviuri in prealabil. De ce? In primul rand, exista o serie de intrebari clasice si nu neaparat comode (mai ales pentru cei mai putini vorbareti, cum sunt programatorii in general), de exemplu: "De ce vrei sa te angajezi la aceasta companie?", "Ce ai schimba la un produs oferit de companie?", "Care este cel mai interesant proiect la care ai lucrat vreodata?", etc. Vei ajunge sa oferi raspunsuri mult mai bune si mai complete odata ce esti pus de cateva ori in ipostaza de a raspunde la ele. Imi amintesc, de exemplu, ca la primul meu interviu pentru Google am fost intrebat de proiectele la care am lucrat la facultate. Mi-era cam jena sa povestesc ce facusem mai ales ca erau lucruri nu foarte complicate (acum, gandidu-ma mai bine, nu cred ca intervievatorul se astepta neaparat la ceva complicat) si am insistat ca nu am facut nimic deosebit, in loc sa povestesc despre oricare proiect si cred ca acest lucru m-a costat. Intre timp, am devenit atat de obisnuit cu aceasta intrebare incat, daca nu m-as controla in mod special, probabil as reusi sa plictisesc intervievatorul sau sa nu-mi las suficient timp pentru intrebarile de coding. In al doilea rand, veti ajunge sa tratati cu mai multa usurinta situatiile neprevazute. De exemplu, cunosc cazul unei persoane care la primul interviu a spus ca limbajul preferat e C++ pentru ca vroia ca la intrebarile de coding sa lucreze in C++ dupa ce se antrenase pe infoarena, topcoder, etc. Apoi intervievatorul l-a intrebat de un proiect mai deosebit pe care l-a facut in C++ si asta l-a blocat, in loc sa povesteasca despre alte proiecte super cool pe care le-a facut si sa spuna ca foloseste C++ in special pentru "short coding challenges".

2. La concursurile de programare, elevii mai putin experimentati tind sa evolueze mai slab, chiar daca dovedesc o inteligenta comparabila sau chiar superioara primilor clasati. Cauzele sunt o multime: emotii, bug-uri frecvente pe care le intalnesc prima oara, lipsa unei strategii generale de abordare a unui concurs, etc. De exemplu, acum vreo 2-3 ani predam la ICHB celor care acum sunt primii in lot si trebuia sa explic adesea profesorilor ca rezultatele mai slabe la anumite concursuri nu se datorau lipsei pregatirii elevilor, ci a lipsei experientei de concurs care nu poate fi castigata peste noapte. O dovada suplimentara e faptul ca atunci stapaneau deja cam 80%-90% din cunostintele teoretice pe care le detin acum.

In concluzie, prin exercitiu poti imbunatati considerabil peformanta medie la o proba sau la orice eveniment dintr-o categorie asemanatoare.

http://infoarena.ro/algoritmiada-2009/runda-3/solutii#secvmax

Ideea e sa incerci sa calculezi len[ i ] = lungimea minima a unui sir care are un 1 in centru si diferenta dintre lungimea partii sirului la dreapta de 1 si lungimea partii sirului la stanga de 1 egala cu i (i poate fi si negativ, dar nu e o problema mare). Adaugarea de siruri noi la stanga si la dreapta te duce in stari noi. Daca vezi starile len ca noduri ale unui graf, atunci prin adaugarea unui sir la stanga/dreapta se formeaza muchii cu cost. Si de aici ideea de Dijkstra.

O idee buna e sa folosesti formula cu determinant pentru a calcula aria triunghiului. Operatiile sunt mai rapide si poti evita folosirea numerelor in virgula mobila.

Comentati aici despre post-ul: Google internships pentru studentii din anul intai.

Grija mare tot la long long cand faceti descompuneri. Codul urmator cicleaza cand incerc sa descompun un numar prim foarte mare:
http://community.topcoder.com/stat?c=problem_solution&rm=312577&rd=14732&pm=11135&cr=22895893

Am pierdut niste bani din cauza asta 

O alta greseala comuna si inrudita e la ciurului lui Eratostene:

Cod:

for (int i = 2; i <= n; ++i) {
   if (prime[i]) {
     for (long long j = (long long) i*i; j <= n; j += i) {
       prime[j] = 0;
   }
}

Daca nu pui acolo long long pentru n = 65 000 deja programul cicleaza. Ma rog, mai exista si alte moduri elegante de a evita asta (gen i*i <= n), dar am vazut ca lumea tinde sa faca asa. Fiti atenti.

Ai dreptate. Am crescut limita la 0.5s.

Cum nu? Se tine chiar in Romania la anul! 

Da, e cam ca celalalte SRM-uri.