infoarena

Runda 2 (http://infoarena.ro/monthly-2014/runda-2) va avea loc astazi, 21 Februarie la ora 19⁰⁰.
Va uram mult succes!  :winner1:

Am decis sa reevaluez sursele la problema Gigel si Resturile (http://www.infoarena.ro/problema/gsr) acum. Va dura doar cateva minute, timp in care veti avea sursele in asteptare. Asa puteti vedea daca va intra sau nu problema, cu limita marita  :) . Imi cer scuze pentru limita stransa de timp la aceasta problema.

Nu pot submita din cauza ca am sursa in asteptare...

Evaluarea s-a terminat. Ne cerem scuze.

Runda s-a incheiat! Clasamentul este public. Solutiile sunt in curs de editare. Ne cerem scuze pentru problemele create de limita de timp. Felicitari tuturor participantilor!  :winner1:

Daca solutia oficiala la Triopalindrom este N ^ 2, atunci limita de timp e cam stransa :) am N ^ 2 pur si a luat TLE pe 2 teste....

E cam mica limita de timp la Triopalindrom. (asta in cazul in care solutia cautata e O(N^2)) :)

Felicitari pentru runda!
Mi s-au parut mai ok problemele runda trecuta, acum au fost 3/4 de matematica  :sad:  :)

Triopalindrom nu intra in timp cu hash-uri? Nu prea inteleg de ce sunt limitele asa stranse, adica eu cred ca ar trebui sa intre si sursele care au aceeasi complexitate ca cea oficiala, insa nu folosesc aceeasi metoda de rezolvare... (banuiesc ca sursa oficiala e cu KMP). Ar trebui macar sa puneti testele de feedback pe cele mai mari ca daca intra pe ultimul sa stii ca intra in timp/memorie si pe celelalte.

Ce urat :( : http://www.infoarena.ro/job_detail/1114668


Si etapa trecuta la fel, nu a intrat o solutie cu arbori de intervale, insa intra cea cu AIB. :D

La triopalindrom era stransa limita deoarece trebuia (N^2)/3. Ma rog, asa am facut eu.

Triopalindrom:

Solutia cautata este O(N^2), intr-adevar. Sursa oficiala, codata fara nici o optimizare are 50 ms. Sursa oficiala, codata optimizat are 16 ms.

Solutiile vor fi publicate in curand, acum se lucreaza la pagina. Acum adaugam si problemele in arhiva.

Nu uitati ca asteptam feedback :D !

Tot nu mi se pare ok, de unde ar fi trebuit sa stiu eu ca mai trebuie sa optimizez solutia mea sau sa o las asa, avand in vedere ca aveam OK pe ambele teste de feedback? :)

Am inceput cu Gigi si restrictii, si de noob ce sunt am stat ceva pe ea pana sa ma prind cum sa fac citirea :)). Oricum, ma mir ca la un start asa prost am iesit asa bine.Felicitari lui Teodor Plop pentru problemele foarte frumoase !  =D>  :ok:

Felicitari pentru probleme ! Au fost dragute.

Pacat ca in 3s nu am reusit sa dau submit la Gigel si Resturile  :'(

Referitor la probleme, ele au fost ok, dar nu cred ca scopul unui asemenea concurs e optimizarea unor solutii de complexitate buna. Cred ca ar trebui sa fiti mai putin stricti la capitolul asta. :)

Mi s-au parut grele problemele, poate le-am si abordat in ordinea gresita. Ar fi misto sa fie ordonate crescator dupa dificultate. Oricum felicitari pentru runda, mi-a placut.

Triopalindrom era o problema de nivel B. Pentru rezolvarea ei nu erau nevoie de cunostinte de hashing / KMP. Cititi solutia oficiala :) pe pagina solutiilor (http://www.infoarena.ro/monthly-2014/runda-2/solutii).

Concursul nu a avut ca scop optimizarea unor solutii de complexitate buna.

La problema lui Gigel, a fost ceva neintentionat si am incercat pe cat posibil sa reparam acest lucru.

La problema Triopalindrom, solutia oficiala folosea un O(N^2) curat, din cate se poate observa. Cel mai probabil solutiile care foloseau hashing / KMP, de aceeasi complexitate, erau mult mai lente.

LE: Vom adauga in scurt timp si solutiile celorlalte probleme.

Felicitari pentru runda ! Mi-a placut si a fost interesanta.  =D> Singura problema pe care am intampinat-o a fost coada lunga de evaluare si nu am putut afla feedbackul decat dupa ceva timp. Pe de alta parte , problemele mi-au placut insa limita la triopalindrom a fost cam stransa : am luat TLE pe un test cu complexitate O(N^2).

Mi se pare chiar aiurea

Asta sa intre: http://www.infoarena.ro/job_detail/1115596
Asta sa nu: http://www.infoarena.ro/job_detail/1114668

Stiu ca nu e bine sa faci citire cu cin (la concursuri), dar sa iasa din timp pentru o singura operatie de citire a unui sir scurt de caractere?

Tu folosesti niste operatii de tip modulo pe acolo, care sunt destul de lente, din cate se poate observa. Solutia oficiala este mult mai simpla si mult mai directa. Timpul de executie a fost setat pentru acea solutie si atat.

Eu am KMP, fara operatii modulo, si tot iese din timp... Si am O(N ^ 2), nu mai mult, nu mai putin.

Stiu, exact asta ziceam. Voi considerati ca solutie corecta doar solutia oficiala, nu si alte solutii de aceeasi complexitate dar cu o constanta putin mai proasta.  :)

Si, lasand la o parte asta, solutia mea intra in timp citind sirul cu scanf, insa nu intra citind sirul cu cin, deci era la limita solutia aceasta. (oricum e vina mea ca am uitat sa schimb citirea)

Am considerat corecta solutia cea mai simpla atat din punct de vedere al implementarii cat si din punct de vedere al cunostintelor necesare. Recunosc ca restul complexitatilor, cu sau fara constante nu m-au interesat.

LE: Voi incerca sa tin mai mult cont de aceste detalii pe viitor.

Amandoi am considerat ca cea mai buna idee la care se gandeste cineva este si cea mai simpla. Recunoastem ca aceasta problema care s-a vrut a fi a doua ca dificultate a devenit cea mai grea. Ne cerem scuze si vom incerca pe viitor sa ne apropiem de gandirea elevilor din timpul concursului :) .

Aceeasi chestie s-a intamplat si la problema Baruri, de la ONIS, cand solutia cu aint lua TLE, iar cea cu aib lua 100. Problema e ca inca se intampla ca o solutie cu complexitate teoretica la fel cu cea a solutiei oficiale, dar cu constanta diferita, sa ia TLE. Diferenta e ca, in cazul de fata, feedback-ul nu imi dadea de inteles (si nici celorlalti care sunt in aceeasi situatie) ca ar trebui sa caut alta idee sau sa o optimizez pe cea care o aveam deja.

PS: Inca se poate remedia problema ;)

Eu iau wrong answer pe doua dintre teste...
Am O(N ^ 2) si fac in felul urmator:
fixez o lungime k, parcurg un i (1, N) si
imi construiesc un vector dp[ i ] = d[i - 1] + (s[ i ] == s[i + k])
La fiecare i verific daca dp[ i ] - dp[i - 2*k] == 2*k, iar in cazul in care e adevarat incrementez solutia...
Imi poate da cineva un contra exemplu sau sa imi explice mai detaliat solutia, si anume cum fac in O(1) verificarea daca secv[i, i + 3*k] este triopalindromica?

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.

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  :)

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! :D

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 :)

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)

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? :)

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

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.

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.

Cand se da update la rating ?

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

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

nu prea inteleg ce ai vrut sa zici  ???

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?

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

Mersi  :shock: