Infoarena Monthly 2014, Runda 2

[•Teodor94]

Runda 2 va avea loc astazi, 21 Februarie la ora 19⁰⁰.
Va uram mult succes!  

[•Teodor94]

Am decis sa reevaluez sursele la problema Gigel si Resturile 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.

[•SRadu]

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

[•Teodor94]

Evaluarea s-a terminat. Ne cerem scuze.

[•Teodor94]

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! 

[•visanr]

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....

[•tzipleatud]

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

[•Cristy94]

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

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.

[•PlayLikeNeverB4]

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

[•Teodor94]

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 !

[•visanr]

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?

[•Kira96]

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 !    

[•popoiu.george]

Felicitari pentru probleme ! Au fost dragute.

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

[•tzipleatud]

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.

[•S7012MY]

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.

[•Teodor94]

Triopalindrom era o problema de nivel B. Pentru rezolvarea ei nu erau nevoie de cunostinte de hashing / KMP. Cititi solutia oficiala pe pagina solutiilor.

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.

[•danalex97]

Felicitari pentru runda ! Mi-a placut si a fost interesanta.   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).

[•Cristy94]

Triopalindrom era o problema de nivel B. Pentru rezolvarea ei nu erau nevoie de cunostinte de hashing / KMP. Cititi solutia oficiala pe pagina solutiilor.

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

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.

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?

[•Teodor94]

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.

[•visanr]

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

[•Cristy94]

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.

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)

[•Teodor94]

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.

[•maritim]

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 .

[•visanr]

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

[•CosminRusu]

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?