Eu am comandat editia a 3-a in engleza de aici (alternativa la Amazon - desi am citit pe undeva ca parca au fost cumparati de Amazon). Cred ca au si editia a doua. Poate un avantaj ar fi ca vine prin posta. Plata am facut-o prin paypal (alta varianta ar fi direct cu cardul). Mie imi place site-ul asta. Am mai comandat cateva carti de pe el. Cartea mi-a ajuns cam in doua saptamani si cateva zile.

Deseori te omoara timpul rau de tot daca faci toate operatiile pe long long  .

Intr-adevar, dureaza cu pana la 150% mai mult la inmultire si cu 100% mai mult la adunare daca faci asa:

Cod:

long long v = 0, i;
for (i = 0; i <= 1000000000; ++ i) {
    v = v + i;
}

fata de asa:

Cod:

int v = 0, i;
for (i = 0; i <= 1000000000; ++ i) {
    v = v + i;
}

Dar dureaza cu 83% mai mult la adunare si 24% mai mult la inmultire daca faci asa:

Cod:

long long v = 0, i;
for (i = 0; i <= 1000000000; ++ i) {
    v = v + i;
}

fata de asa:

Cod:

long long v = 0;
int i;
for (i = 0; i <= 1000000000; ++ i) {
    v = v + i;
}

Daca programul tau e la limita, intr-adevar conteaza optimizarile astea, dar daca nu consuma nici macar jumatate sau o treime din limita de timp, de ce sa te complici?
(Pe topcoder limita e de 2 secunde cam la toate problemele, desi 0.1 secunde ar fi arhisuficient la majoritatea).

Ce nu inteleg e de ce te zgarcesti la o variabila? Crezi ca faci economie? De regula, intr-o problema in care e necesar sa am o variabila long long, le fac toate long long, ca sa ma asigur ca nu am probleme legate de domeniul de valori al variabilei. Exceptie fac sirurile care pot duce la "Limita de memorie depasita". Acolo, intai fac un calcul sa vad daca imi ajunge memoria, si daca nu imi ajunge sau daca cred ca daca folosesc mai putina memorie imi va imbunatati sesizabil viteza de executie a programului (adica daca imi cresc sansele sa prind teste in plus), atunci folosesc int (bineinteles doar daca valorile incap pe int), iar mai apoi urmaresc cu atentie toate locurile in care folosesc sirul respectiv ca sa nu am probleme. In general, cu cat e mai simplu codul, cu atat mai bine. Nu are rost sa te complici pentru cativa bytes in plus sau in minus.

P.S.: Cum faceai descompunerea "ca sa fie bine"?

Tot int in loc de long long  La variabila i

Puteti sa stergeti/mutati postul asta daca nu bine.

Sambata 21 Aprilie va avea loc runda 2A de la TCO Algorithm. Cred ca de la ora 19:00 la noi (pe site e trecuta ora 12). Poate puteti ajusta putin de tot programul algoritmiada ca sa prindem si runda asta? Multumesc.

Poate sa verifice cineva exemplul 1 de la problema video?
In:
1024 2048 100 20
Out
20480
Conform enuntului se asteapta la inceput pana se umple buffer-ul, adica s/d = 20480/1024 = 20.
Iar durata totala a pauzelor trebuie sa fie <= p = 20. Deci dupa ce se umple bufferul ar trebui sa mearga video-ul pana la sfarsit. Adica 100 de secunde. Bucata din buffer se reda in 20480/1024 = 10 secunde, timp in care se mai incarca 5 secunde de film. Asa ne iese ca nu se redau mai mult de 20 de secunde din film. Daca calculam t(x) cat avem in buffer la momentul x de la inceputul rularii filmului avem t (x) = t (0) - x * b + x * d, unde t(0)=20480. Luam t (x) = 0.
Si avem t (0) = x (b - d), de unde x = t (0) / (b - d) = 20. Si asa ne iese ca se vor reda 20 de secunde din film dupa care bufferul e gol. => ca mai e nevoie de o pauza pentru a incarca bufferul din nou, asa ca timpul total al pauzelor p se depaseste. Unde gresesc? Sau e chiar gresit exemplul?
In mod normal unde pot intreba asta?
Si stie cineva daca s-au afisat rezultatele de la runda precedenta?

Vroiam sa zic ca sunt oameni care participa la concursuri fara a se inscrie in prealabil. Astfel ei apar ca participanti la unele concursuri si nu li se modifica ratingul (ratingul se modifica doar daca te inscrii). La vladii poti sa vezi ca, de exemplu, la runda a 4-a a concursului Algoritmiada 2012 a participat (a trimis probleme), dar nu s-a inscris (vezi lista persoanelor inscrise).

"Trebuie sa te inscrii pentru a ti se modifica ratingul" - e ceva ce scrie inainte de orice concurs. Apar ca participanti toti cei ce au submitat o problema in timpul concursului.

Ati refacut si ratingurile?

La open mi s-a parut ca a cam lipsit lumea  

Problemele au fost ok, desi muncitori se rezolva cam ca si Order, iar pentru puteri3 trebuia sa scoti doar recurenta din cartea lui Tomescu (intr-adevar nu era destul de originala ...) ...

Spirala3 si Go2 m-au naucit ... N-am avut nicio idee de unde sa le apuc.

Totusi felicitari tuturor!

@Andrici Cezar: Acum sunt 4 grupe, nu 3 ca anul trecut. S-ar putea sa fie la 5-9 mai putini ca anu' trecut
@Ionescu Vlad: Are faptul ca te-ai clasat al doilea vreo legatura cu infrumusetarea dupa-amiezii?  


L.E.: Sa nu uitati de rating-uri.

Sa nu uitati, daca se poate sa trimiteti mailul cu anuntul concursului. Ca sa isi rezerve timp toata lumea. Poate ar trebui trecuta si ora pe pagina principala infoarena.

Si eu cred ca am gasit solutia:

http://pastie.org/private/kyheitcuspp4bosfxhkq

Se poate sa existe doua noduri diferite care sa aiba cel de-al doilea pointer spre acelasi element?

For-ul interior executa m instructiuni, unde m ia valori, pe rand: 2*n, 4*n, 8*n, ..., 2^k * n unde k este de cate ori se executa corpul while-ului. Adica k = 1+ floor (log n). De unde timpul total de executie Theta (2*n + 4 * n + 2^k * n) = Theta (n^2). k este egal cu numarul de biti din scrierea lui n in baza 2. Impartirea la 2 este echivalenta cu o shiftare la dreapta. In suma dai factor comun pe n si ramane sa calculezi suma unei progresii geometrice.

Data viitoare o să încerc să scriu mai incendiar.

Poti sa scrii ca romanii nu sunt programatori buni si o sa se revolte multa lume

[Totusi ma gandesc ca s-ar putea sa fie gresita solutia asta.]

Nu am terminat-o, dar ideea mea e asa: Pentru fiecare secunda i de la prima pana la ultima din zi, incercam sa determinam cat de mult poate dormi Ghita, daca incepe sa doarma in secunda i, ignorand cel mult k telefoane. Cat de mult poate dormi (l secunde), determinam cu o cautare binara pe intervalul [0, 86400]. Verificam daca poate dormi incepand din secunda i, timp de l secunde, facand doua cautari binare. Cu una gasim ultimul telefon care se termina inainte de secunda i, si cu cealalta, primul telefon care incepe dupa secunda i + l.

L.E.: Complexitatea ar fi O (S * log S * log N). Unde S e numarul de secunde din intervalul de timp pe care se poate dormi si N e numarul de telefoane. In cazul nostru S=86400.
L.L.E: Totusi ma gandesc ca s-ar putea sa fie gresita solutia asta. Ironic, avand in vedere titlul "Cautarea ta binara este gresita"

Poti sa incerci problema: http://codeforces.com/contest/158/problem/E
E din ciclul cautare binara doua cautari binare in cautare binara in cautare liniara. Ca sa exersezi invariantii astia.  Succes

L.E.: Daca vrei sa iti fortezi creierii, fa-o fara functii.

Ca si consolare e un VK Cup Quali Round dupa SRM. Pacat ca tine 24 de ore.

Tu unde ai lucrat pana acuma de ai intalnit astfel de oameni?

[sectiunea Downloads a site-ului]

Aceasta problema nu permite vizualizarea testelor folosite in evaluarea pe infoarena. Adica nu se poate.
Poti sa vezi, insa, testele folosite la evaluarea de la Olimpiada Judeteana din 2003. Acestea le gasesti in arhiva pentru OJI 2003, din sectiunea Downloads a site-ului.

Prin sectiunea Downloads a site-ului m-am referit la site-ul infoarena. Pe pagina principala a site-ului este un meniu care contine optiunea Downloads si care te duce la adresa: http://infoarena.ro/downloads. Acolo gasesti arhiva pentru OJI 2003, la adresa: http://infoarena.ro/downloads?action=download&file=oji2003.zip&safe_only=false
M-am uitat prin arhiva asta pe care ti-am linkat-o si contine, cel putin pentru taxe, solutii oficiale, teste si toate cele. Banuiesc ca e la fel si pentru celelalte probleme.

Aceasta problema nu permite vizualizarea testelor folosite in evaluarea pe infoarena. Adica nu se poate.
Poti sa vezi, insa, testele folosite la evaluarea de la Olimpiada Judeteana din 2003. Acestea le gasesti in arhiva pentru OJI 2003, din sectiunea Downloads a site-ului.

Am scris eu solutia problemei Bal in articolul cu solutii.
P.S.: Daca am gresit ceva,  va rog corectati!

In enunt scrie:

Exista posibilitatea ca, din neatentie, un baiat sa dea mai multe biletele cu numele aceleiasi fete.

Astfel testul:

Cod:

2 4
1 1
1 1
2 2
2 2

este valid, nu?

Am vazut mai multe solutii care au luat 100 de puncte, care dau "NU" pe asta, desi eu cred ca ar trebui sa fie:

Cod:

"DA"
1
2

Printre solutiile care dau "NU" se numara si a mea si a autorului.

Iarasi nu merge evalul.