Ai incercat sa implementezi dinamica cu memoizare? S-ar putea sa mearga ceva mai bine...

Nu cunosc nici o competitie la care limita de timp pe problema sa fie diferita pentru C++ si Pascal. Pentru Java da, diferenta e mare, stiu ca la USACO e limita diferita pentru Java... dar nu mi se pare ok sa ceri schimbarea limitelor de timp doar pentru ca la... ~10 probleme dintr-o arhiva de peste 1000 (adica in jur de 1%) iei 90 cu un TLE daca scrii in Pascal.

Pentru utilizatorii Internet Explorer: link

Daca vrei pot sa incerc sa te ajut. Nu sunt nici pe departe un profesionist al domeniului, dar am participat la cateva SRM-uri si TCHS-uri.

Prima metoda mai detaliata ar suna cam asa:
Notam cu L lungimea laturii triunghiului echilateral, cu M mijlocul segmentului pe care tu il ai. Se stie ca inaltimea intr-un triunghi echilateral este egala cu L * sqrt(3) / 2. Afli ecuatia mediatoarei segmentului tau (dreapta care trece prin M si e perpendiculara pe segment) si in momentul asta te intereseaza un punct care se afla la distanta L * sqrt(3) / 2 de M (1) si satisface ecuatia mediatoarei (2).
Scriind relatiile (1) si (2) obtii un sistem de 2 ecuatii cu 2 necunoscute (coordonatele punctului). Din cauza ca sistemul o sa se reduca la o ecuatie de gradul II o sa obtii 2 solutii (varful poate fi de ambele parti ale segmentului). Sper ca am fost suficient de explicit.

Bravo baietii! Ati facut treaba!

Atasez brosura cu problemele si solutiile. Din pacate pentru ziua a II-a 3 dintre solutii lipsesc. Sper sa va fie utila!

Multumim . Cei de la Vianu: Ciprian Farcasanu si Andrei Poenaru au luat bronz, dar, din pacate, Cosmin Carabet a fost primul sub bronz.

Salut
Uitati aici niste rezultate:

Locul 1: Un rus - 673
Locul 2: O rusoaica - 670
Locul 3: Voroneanu Radu - 666 (din 800).
Locul 4: Mocan Cezar - 613
Locul 5: Un rus - 532
Locul 6: Farcasanu Ciprian - 515
Locul 7: Stan Serban Andrei - 506
Locul 8: Poenaru Andrei - 485
Locul 9: Carabet Cosmin - 360

Medaliile probabil vor fi 3:3:3 dar inca nu stim sigur.

Nu stiu daca este pe campion, dar si mie mi-ar placea sa fie o chestie dinasta cum zice Stefan. Sa vedem ce parere au cei din echipa

Am primit un mesaj personal de la un utilizator si in anuntul de pe mail imi scria ca l-am primit de la altcineva 

Felicitari pentru organizarea finalei, dupa parerea mea cel mai reusit concurs din anul acesta! Probleme frumoase, conditii bune, activitati din plin, premii mari si nu in ultimul rand distractie.
Nota 10 pentru echipa Infoarena! 

Aceasta problema se poate reduce usor la 2SAT si am observat ca solutia oficiala este un greedy. Are cineva o demonstratie ca acel greedy merge?

Felicitari echipei pentru noile feature-uri adaugate (sortatul problemelor si scoaterea "gaurilor" din arhiva)!!! Keep up the good work! 

Wikipedia. 1 si 2. Sper sa te ajute!

In 2005 a fost la Baia Mare, stiu ca am luat locul 2 la mate atunci  Si am impresia ca anul asta se tine la Zalau...

Uita-te pe subiectele din anii trecuti. Ar trebui sa stapanesti bine recursivitatea + backul, sa stii programare dinamica (nu se dau dinamici prea grele la a 9-a), greedy, cautare binara, geometrie basic... Nu sunt chestii teoretice foarte avansate, trebuie sa ai idei cat mai bune. Spor la treaba!

Exista evaluator, si pe testul 6 sursa ta chiar da prost pentru prima si a 3-a cerinta. Spor la debugat!

In functia "trage" e o greseala, pentru ca sirul tip are lungime 4 si tu faci tip[r], unde r apartine intervalului [0 .. 12]. Sper ca nu mai e si altceva.

Iti explic eu .
Prima problema ar putea fi reformulata in felul urmator: sa se gaseasca numarul de partitii ale lui N (partitie = sir de numere cu suma N), de lungime D (adica formate din D numere), astfel incat fiecare numar din partitie sa fie >= K. Pentru a rezolva asta facem programare dinamica: C[ i ][ j ] = numarul de solutii daca am fixat primele i numere din partitie si avem obtinuta suma j. Raspunsul se va gasi in C[D][N]. Te las sa te gandesti la recurenta, daca vrei ti-o zic. Se poate face in O(N^2 * D) - facand dinamica inainte, sau daca optimizezi in O(N * D), cu sume partiale.


La cea de-a doua e mai simplu, dupa ce ai determinat toate cuvintele tii sirul D[ i ] cu semnificatia lungimea maxima a unui lant avand proprietatea din enunt care se termina cu cuvantul i, si L[ch] = lumgimea maxima a unui lant pana la pozitia i (adica din ce am calculat pana acum) care se termina cu caracterul ch. D[ i ] = L[prima_litera_din_cuvantul_i] + 1. Si daca D[ i ] > L[ultima_litera_din_cuvantul_i] atunci actualizezi valoarea din L. Raspunsul va fi numarul de cuvinte - maximul din sirul D (numarul minim de cuvinte eliminate). Pentru a face reconstituirea se tine un vector suplimentar, prev[ i ] = cuvantul care vine inaintea cuvantului i in solutia care da valoarea D[ i ].

Sper ca ai inteles! Spor la implementat!

Ati putea adauga in calendar si TCHS Tournament.

Care sunt functiile astea complicate? 

As avea si eu o intrebare: Chiar daca am citit solutia oficiala si acolo este explicat altfel, as dori sa intreb de ce nu merge calculat

C (a,b) % p folosind invers modular, adica C (a,b)%p=(a! * b!^(p-2) * (a-b)!^(p-2))%p.

Multumesc anticipat. 

Se poate, doar ca am impresia ca iti creste complexitatea (spun asta pentru ca iau TLE pe 7 teste cu aceasta solutie). Pentru ca produsul sa dea restul bun si nu 0, trebuie sa scoti toti factorii de P din factoriale. Sa il luam ca exemplu pe B!. Cel mai simplu e sa scoti toate numerele divizibile cu P din produsul 1*2*3*...*B, si o sa iti ramana un B!_prim (egal cu B! / produsul_numerelor_divizible_cu_P). Dar tu ai scos toate numerele divizibile cu P, nu doar factorii de P. Si numerele astea divizibile cu P au forma 1*P, 2*P, ... K*P. Ceea ce inseamna ca pentru ca produsul sa fie valid ar trebui sa il inmultesti pe B!_prim cu K!. Doar ca si in K! o sa iti apara factori de P . Tot repeti procedeul pana cand ajungi sa nu mai ai factori de P. Asa ajungi sa obtii restul bun.
Sper ca am fost destul de explicit.

Sunt puse in arhiva educationala. Atunci cand trimiti o sursa la o problema si iei un punctaj < 100, in partea de jos a paginii cu enuntul problemei o sa iti apara 2 linkuri, unul dintre ele cu indicatii de rezolvare (de fapt aici "se ascunde" solutia oficiala) si al 2-lea cu primul test pe care nu ai luat OK.

Pai poate ca A[0] coincide cu maximul din sir