Infoarena Monthly 2014, Runda 2

[•Teodor94]

Feedback-ul a fost setat pe testul 1 si testul 10. Practic, testul 10 a fost unul dintre testele maxime. Constructia testelor a facut insa, ca "worst case-ul" sa pice pe alt test.

[•visanr]

Avand in vedere ca, din cate vad, este exclusa o reevaluare cu o limita de timp mai mare, de acum incolo ma voi gandi de 2 ori inainte sa scriu o sursa care teoretic ar trebui sa intre in timp, ca nu se stie daca ia 100 sau nu.
Nu vreau sa luati personal ce spun, nu am nimic cu nimeni, doar faptul ca e limita mica nu mi se pare in regula.
Per total, mie mi-a placut concursul, e ok faptul ca nu au mai fost punctajele asa stranse si s-a facut departajarea cum trebuie. Sper sa updatati si ratingurile cat mai repede 

[•Teodor94]

Limita de timp a fost setata astfel incat solutia cea mai simpla sa intre cat se poate de lejer in timp. Nu ne-am gandit si la alte solutii de aceeasi complexitate, dar mai complicate. Multumim pentru feedback, o sa tinem cont la runda viitoare de parerile voastre . Am adaugat si ultima problema in pagina cu solutiile. Felicitari tuturor si ne vedem in martie cu runda 3!

[•Vman]

Mi se pare foarte natural sa trebuiasca sa iei in considerare si constanta atunci cand estimezi timpul de executie. Constanta nu conteaza cand limitele tind catre infinit sau catre zero, altfel conteaza chiar foarte mult.

@Buleandra Cristian:
Diferenta intre cele doua surse nu este citirea ci faptul ca folosesti stl string (http://www.infoarena.ro/job_detail/1115778?action=view-source). stl string este o clasa wrapper peste char*, ceea ce pe langa niste functionalitati dragute pe care le aduce, face insa ca operatorul [] sa mai faca un pas in plus cand acceseaza un element al sirului. Nu stiu daca e normal sa fie atat de lent, dar macar stim ca nu e de la citire

[•visanr]

Pai si in cazul unei surse care face functia prefix de la KMP pe fiecare sufix al sirului, cat ar fi trebuit sa estimez ca e constanta? (folosesc char, nu string)

[•Cristy94]

Mi se pare foarte natural sa trebuiasca sa iei in considerare si constanta atunci cand estimezi timpul de executie. Constanta nu conteaza cand limitele tind catre infinit sau catre zero, altfel conteaza chiar foarte mult.

@Buleandra Cristian:
Diferenta intre cele doua surse nu este citirea ci faptul ca folosesti stl string (http://www.infoarena.ro/job_detail/1115778?action=view-source). stl string este o clasa wrapper peste char*, ceea ce pe langa niste functionalitati dragute pe care le aduce, face insa ca operatorul [] sa mai faca un pas in plus cand acceseaza un element al sirului. Nu stiu daca e normal sa fie atat de lent, dar macar stim ca nu e de la citire

Da, ai dreptate. Oricum, in continuare parerea mea este ca nu ar trebui ca departajarea sa se faca in functie de aceste mici diferente .

Legat de solutia la DIV4. Solutia era destul de evidenta inca din timpul concursului, insa poate sa puna cineva un link catre un articol care explica cum sa calculezi combinari (n,k) % p eficient? (sa precalculezi folosind invers modular, sau ceva asemanator parca era). Sau nu era nevoie de asta?

[•klamathix]

Ca să-ți faci combinările rapid, îți precalculezi toate factorialele mod P și toate inversele modulare ale factorialelor mod P. Apoi răspunsul e fact[n] * invfact[k] * invfact[n - k] 

[•Cristy94]

Ca să-ți faci combinările rapid, îți precalculezi toate factorialele mod P și toate inversele modulare ale factorialelor mod P. Apoi răspunsul e fact[n] * invfact[k] * invfact[n - k]  

Mersi mult, chiar am cautat pe net in timpul concursului si nu am gasit niciunde explicat ok. Ar trebui sa fie un articol pe infoarena despre asta, stiu ca a mai fost data de curand o problema la care trebuia acelasi lucru.

LE: Am vazut ca este sumar explicat si aici: http://www.infoarena.ro/problema/inversmodular

[•Impaler_009]

In functie de ce combinari anume iti cere problema, exista mai multe moduri sa le calculezi. De exemplu, la problema Div 4, se putea face constatarea ca pentru un anumit n, o sa ai nevoie de o singura combinare comb(n,m). Pentru n = C - K - 2 (C-numarul de cifre din numar,K-semnificatia din enunt), o sa ai nevoie de comb(n,m) cu m = 0. Pentru n = C-K-1, o sa ai nevoie de comb(n,m) cu m = 1 (La fiecare pas, mergand catre dreapta, scade numarul cifrelor fixate din partea dreapta cu 1, deci creste numarul pe care trebuie sa le fixezi in stanga cu 1 si creste si numarul cifrelor din stanga din care poti sa alegi tot cu 1). Si pornind de la primul comb (C-K-2,0) = 1, poti sa le calculezi pe celelalte astfel: comb(n+1,m+1) = comb(n,m)*(n+1)/(m+1).

PS: In articolul cu solutii nu este cumva o greseala ? Spune : "Pentru ca cifra de pe poziţia i şi cifrele de după să fie ultimele cifre din număr, va trebui şă ştergem exact C-i+1 cifre". Nu este cumva C-i-1 ? Adica daca cifra i o sa ramana penultima inseamna ca trebuie sa stergem ultimele C-i cifre din numar din care o sa mai lasam una care va fi ultima (deci vom sterge C-i-1). Sau poate n-am inteles eu bine ce vreti sa spuneti.

[•Teodor94]

Da, este o greseala. Multumim pentru observatie.

De asemenea, vroiam sa anunt ca incepand cu runda 3, problemele vor fi afisate in ordinea dificultatii . Sunteti ok cu aceasta schimbare?

LE: Cum calculez eu combinarile este ca pornesc de la prima cifra din ultimele K+2 si retin pe parcurs valoarea combinarii la care am ajuns. Initial valoarea retinuta este 1. Cand trec mai departe, fac trecerea de la Combinari de i luate cate j la combinari de i+1 luate cate j+1, inmultind valoarea retinuta cu i+1 si impartind-o la j+1. Pentru impartire este nevoie de invers modular.

[•popoiu.george]

Cand se da update la rating ?

[•dutzul]

Nu vad care ar fi rostul ordonarii dupa dificultate , pana la urma sa iti dai seama de dificultatea unei probleme face parte din concurs , am incurcat o gramada de probleme din cauza ca mam gandit la o solutie prea complicata ,pe cand problema admitea o solutie simpla , pe codeforces-topcoder sunt ordonate din cauza ca si punctajele difera

[•Kira96]

Dureaza cam 4 minute sa citesti/intelegi problema + sa cauti ceva idei, deci daca le iei in ordine proasta pierzi chiar si 12 minute, care sunt destul de esentiale

[•S7012MY]

Nu vad care ar fi rostul ordonarii dupa dificultate , pana la urma sa iti dai seama de dificultatea unei probleme face parte din concurs , am incurcat o gramada de probleme din cauza ca mam gandit la o solutie prea complicata ,pe cand problema admitea o solutie simpla , pe codeforces-topcoder sunt ordonate din cauza ca si punctajele difera

nu prea inteleg ce ai vrut sa zici 

[•SRadu]

Mie mi se pare mai ok sa fie in ordine alfabetica problemele. Cum zicea si Dutzu, e important sa iti dai seama singur care ii problema cea mai abordabila.

@Denis Mita Cum ai calculat chestia asta?

[•deneo]

4 * 3 )
E bine sa te apuci de problema cea mai usoara pentru punctaj maxim.

[•SRadu]

Mersi