Da, intra pe long long.

Niste statistici interesante:
link 1
link 2

Romania ocupa niste locuri f. onorante.

[long long]

Pentru long long pe compilatoarele de pe sgu eu declaram long long, iar formatul de citire/scriere pe care il foloseam era %I64d (ala e i mare, nu L mic).
Cat despre WA... tu cum ai facut? Tratai 4 cazuri, in functie de paritatea lui A si B?

Pacat de Stefan ca nu a prins forma de la loturi si nu a reusit sa obtina macar un bronz...
Felicitari echipei Romaniei pentru medaliile obtinute si felicitari profesorilor care, sunt sigur, au ajutat la departajarea celor mai buni 4 care sa ne reprezinte.

Ce-i cu gluma asta? Pe 1 octombrie incepe facultatea. Si oricum, cred ca nu am muncit atat ca sa isi bata cineva joc de noi. Meritam macar o organizare decenta, nu un concurs regional undeva prin... iarna 

[Felicitari echipei Romaniei. Asteptam sa vedem repartizarea pe medalii.]

La ultima problema trebuie facuta infasuratoarea convexa a gropilor (se demonstreaza ca nu are rost sa construiesti stalpi decat in punctele de pe infasuratoare), iar apoi iese o dinamica cu N^2 stari, recurenta N (in total O(N^3)).

Daca te referi la fence, nu e chiar asa. E intuitiv ca solutia e mereu poligon convex (daca ar fi concav am lua infasuratoarea care contine un numar mai mic sau egal de varfuri si cel putin tot atatea puncte in interior), dar nu e mereu pe varfurile infasuratorii convexe a celor N gauri. Uite un contraexemplu: un patrat cu 2 pomi in interior, de parti diferite a celor doua diagonale, si un triunghi in interiorul patratului care sa contina ambii pomi. E clar ca solutia e triunghiul, deci niciun vf. nu e de pe infasuratoare.

Personal as fi bagat urmatoarea solutie: pentru fiecare punct (sa-l notam O) se considera ca fiind originea si se sorteaza dupa unghi punctele din dreapta lui O. Facem programare dinamica de genul M(i,j) = nr. maxim de pomi continuti intr-un poligon cu i varfuri in care ultimul varf sa fie punctul j. Avem relatia: M(i,j) = maxim(M(i-1,k) + TRI[O-k-j]), unde TRI[O-k-j] este nr. de puncte din triunghiul de varfurile alea. Asta poate fi aflat in O(1) daca preprocesam la inceput pt. fiecare pereche de puncte cati pomi sunt sub segmentul respectiv.
Dupa ce am construit tabloul M raspunsul va fi minim(20 * p + M[p][k]). Desi nu se impun restrictii in algoritmul de dinamica, solutia va iesi mereu un poligon convex (se observa ca nu avem nevoie sa intoarcem trei puncte B, C, D "la stanga", pentru ca exista mereu un alt triunghi care il include).
Complexitatea pt. O fixat este N^3 de constanta 1/2.

Complexitatea totala este 1/2 * O(N^3 + (N-1)^3 + (N-2)^3 + ... + 1^3) = 1/2 * O( [N(N-1)/2]^2 ) = 1/8 * O(N^4), adica cam 12.5 milioane de operatii, care intra intr-o sec. S-ar putea sa mearga si mai repede decat zic, nu m-am gandit.

Felicitari echipei Romaniei. Asteptam sa vedem repartizarea pe medalii.

1. Am pus problemele in arhiva.
2. DA

Bagati mare.

Aici puteti discuta despre problema Gropi.

Aici puteti discuta despre problema Reconst.

Aici puteti discuta despre problema Grigo.

A aparut articolul cu solutii: http://infoarena.ro/junior-challenge-2008/solutii.

De facut cateva precizari: sunt foarte importante punctele intr-un concurs. Nu uitati niciodata sa implementati brute-force-ul, care sa va asigure puncte in plus. De exemplu la problema gropi daca nu erati siguri cel mai bine era sa faceti asa:

Cod:

if (c <= 250) brute(); else optim();

Setul de probleme a fost unul foarte dificil la nivel de juniori, asa ca rezultatele le consideram a fi bune. Si nu in ultimul rand, mult succes celor care ne vor reprezenta la JBOI!

[Junior Challenge 2008]

Asteptam parerile voastre despre concursul Junior Challenge 2008. Exprimati-va orice sugestie referitoare la organizare sau la subiectele propuse.

Castigatorii tricourilor vor fi anuntati in curand, dupa terminarea evaluarii!

Concursul Junior Challenge 2008, un concurs marca infoarena ajuns deja la editia a doua, se va desfasura online sambata, 5 iulie. Pagina concursului se gaseste aici.
Castigatorii concursului care sunt elevi in ciclul primar sau gimnazial vor primi cate un tricou infoarena. Va invitam sa participati insa pe toti, deoarece subiectele sunt cu adevarat provocatoare. Mult succes celor care vor participa si nu uitati sa va inscrieti daca doriti sa vi se modifice ratingul.

Am incercat si eu si nici eu nu am reusit.

Se va tine si anul acesta a doua editie. Concursul va fi sambata, 5 iulie, incepand cu ora 10⁰⁰, si va dura 4 ore. Concursul va fi unul cu rating, asa ca trebuie sa va inscrieti. In plus, primii 3 juniori (elevi in clasele 1-8) in urma clasamentului final vor primi cate un tricou infoarena.
Mai multe detalii gasiti pe pagina concursului.

Desi concursul este unul "de juniori", problemele pot fi o provocare pentru oricine. Asa ca va asteptam in numar cat mai mare.

Cred ca da. Anunt zilele astea.

A fost intr-adevar un lot foarte reusit. Felicitari celor care s-au calificat. Cred ca vom avea rezultate foarte bune la IOI.

Mare minune ca Olanda sa nu castige Euro 2008.

Portugalia mi s-a parut mai puternica si foarte spectaculoasa, nu stiu de ce.

Testele sunt sigur bune? Am redus problema la a afla in cate moduri se poate scrie o suma daca coeficientii pentru fiecare termen sunt cunoscuti (coeficientii respectivi sunt combinarile).
Problema e ca sursa oficiala face exact acelasi lucru care il fac si eu, cu singura deosebire ca (,) calculeaza combinarile modulo 10000. Faza asta cred ca e gresita, din moment ce doar rezultatul trebuie considerat modulo 10000. Poate nu ma prind eu de ceva

Aici puteti discuta despre problema Cautare binara.

Problema cp e dubioasa, pur si simplu se afiseaza numai NU . In rest fain.

O sa fie articol cu solutii?

Si eu tot aici am picat la repartizare .

Era impotriva scopului arhivei educationale. La o problema de RMQ trebuie sa inveti sa faci RMQ, nu sa parsezi citirea. Pentru asta merge alta problema, desi e cam dificil sa faci teste datorita marimilor care pot aparea.

Aici puteti discuta despre problema Subsir crescator maximal.