Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: Feedback Runda 1  (Citit de 14066 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« : Decembrie 22, 2012, 15:20:46 »

Hai cu feedback-ul!!!!!!
Memorat
darren
Client obisnuit
**

Karma: 106
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #1 : Decembrie 22, 2012, 15:52:11 »

A fost ales destul de naspa feedback-ul la probleme. La Ismquery am fost convins ca cel din feedback e testul maxim...
In rest runda a avut probleme bune.
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #2 : Decembrie 22, 2012, 15:55:35 »

Da, trebuia sa dau testul 6 nu 5.
Memorat
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #3 : Decembrie 22, 2012, 15:59:11 »

Au existat anumite cazuri particulare mai ciudate la problema X? Eh? http://infoarena.ro/job_detail/839704

In rest, felicitari pentru probleme si organizare Applause
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #4 : Decembrie 22, 2012, 16:01:07 »

La Ismquery trebuia sa se ia 100 cu ~O(M*N) cu multe optimizari? :-"
  • memoizare
  • obsesrvatia ca pana la primul element mai mic sau egal cu cel de pe pozitia P toate sunt mai mari.
  • inceperea cautarii celor K elemente mai mari incepand de la primul mai mare ca elementul curent, ci nu de la elementul de pe P+1
http://infoarena.ro/job_detail/840203 Smile)
« Ultima modificare: Decembrie 22, 2012, 16:10:55 de către Buleandra Cristian » Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #5 : Decembrie 22, 2012, 16:04:02 »

Matrice6 cum se facea ? Eu nu m-am prins...

La X presupun ca era ceva dinamica , nu ? Am avut ceva idei insa nu am finalizat.
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #6 : Decembrie 22, 2012, 16:05:59 »

Au existat anumite cazuri particulare mai ciudate la problema X? Eh? http://infoarena.ro/job_detail/839704

In rest, felicitari pentru probleme si organizare Applause

Ai facut cu KMP? Eu asa am facut si exact pe aceleasi teste primesc incorect. La mine problema era ca daca aveam sirul A="aaab" in care cautam sirul "aaa". Eu luam cel mai lung prefix(de lungime q) care se termina pe pozitia i si actualizam pozitia i-q+1 ca fiind inceputul unei secvente de lungime q. Asa ca pentru al treilea "a" din sirul A aveam q=3 si actualizam pozitia 1, apoi treceam la "b" si q devenea 0, deci nu actualizam pozitia 3 ca fiind inceputul unei secvente de lungime 1. Poate nu ai facut asa, zic si eu  Whistle Smile
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #7 : Decembrie 22, 2012, 16:07:24 »

 Problema X nu se facea cu dinamica. Se facea cu Z-Algorithm.

Au existat anumite cazuri particulare mai ciudate la problema X? Eh? http://infoarena.ro/job_detail/839704

In rest, felicitari pentru probleme si organizare Applause

Ciprian: Nu. Doar busesti tu ceva.
Memorat
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #8 : Decembrie 22, 2012, 16:09:24 »

Am facut KMP pentru primul sir si pentru primul sir inversat. Acolo la KMP cand gasesti potrivirea era if(x==m) poz_sol=i-x , in loc de asta la orice pas actulizez lungimea maxima de inceput de pattern la pozitia i-x,indiferent de x.
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #9 : Decembrie 22, 2012, 16:10:24 »

Se facea cu Z-Algorithm.

Cine-i ăla ?  Aha

LE : Am gasit : http://codeforces.com/blog/entry/3107.
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #10 : Decembrie 22, 2012, 16:15:11 »


Un algoritm mai necunoscut.

Ciprian: inteleg ce faci. Pai faza e ca solutia ta teoretic nu e optima. Dar practic e greu sa faci teste astfel incat sa pice.  E bine ca ai busit totusi Smile)))
Memorat
Challenge
Strain


Karma: 18
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #11 : Decembrie 22, 2012, 16:16:06 »

Mi-a placut problema X, pentru ca este probabil singura problema (din cate stiu eu) de pe infoarena la care chiar se recomanda Z-Algorithm.  Applause
Problema ismquery putea fi trasa de par cu o solutie N*(logN+5)+M daca se parsa si citirea si afisarea.  Rolling Eyes

In rest runda a fost OK, insa totusi, pentru evitarea neplacerilor din timpul concursului ar fi de preferat sa se evalueze pe loc doar feedbackul si la final pe toate testele.  
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #12 : Decembrie 22, 2012, 16:17:54 »

Mi-a placut problema X, pentru ca este probabil singura problema (din cate stiu eu) de pe infoarena la care chiar se recomanda Z-Algorithm.  Applause
Problema ismquery putea fi trasa de par cu o solutie N*(logN+5)+M daca se parsa si citirea si afisarea.  Rolling Eyes

In rest runda a fost OK, insa totusi, pentru evitarea neplacerilor din timpul concursului ar fi de preferat sa se evalueze pe loc doar feedbackul si la final pe toate testele. 

Mai este si problema Arbfind care se face cu Z-Algorithm. 
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #13 : Decembrie 22, 2012, 16:21:40 »

sunt curios care era solutia la subset2...  poate posta cineva ideea de rezolvare?
Memorat
Schumi
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #14 : Decembrie 22, 2012, 16:25:46 »

La subset2 trebuie sa observi ca doua numere au suma divizibila cu un al treilea numar daca suma resturilor impartirii primelor doua numere la al treilea numar este egala cu al treilea numar. Din aceasta observatie reiese ca dupa fiecare numar divizibil cu k poti lua k/2 numere si sa le adaugi la solutie. Dupa ce construiesti solutia poti sa mai adaugi inca un numar care e divizibil cu k, deoarece in solutie nu ai ceva care adunat cu el sa dea divizor de k.

LE: Exista caz particular pentru 1 si pentru 2 cand trebuie sa afisezi 1, respectiv 2.
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #15 : Decembrie 22, 2012, 16:27:04 »

Mi-a placut problema X, pentru ca este probabil singura problema (din cate stiu eu) de pe infoarena la care chiar se recomanda Z-Algorithm.  Applause
Problema ismquery putea fi trasa de par cu o solutie N*(logN+5)+M daca se parsa si citirea si afisarea.  Rolling Eyes

In rest runda a fost OK, insa totusi, pentru evitarea neplacerilor din timpul concursului ar fi de preferat sa se evalueze pe loc doar feedbackul si la final pe toate testele.  

Nu am stiut inainte sa fac testele de solutia N*(logN+5)+M. Smile
Cred ca problema a fost in primul rand faptul ca evaluatorul se bloca si nu neaparat ca se evaluau toate testele (cu toate ca daca s-ar fi evaluat doar feedbackul ar fi fost putin mai ok)
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #16 : Decembrie 22, 2012, 16:29:24 »

Matrice cum se facea pana la urma ?  Huh
Memorat
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #17 : Decembrie 22, 2012, 16:39:59 »

Matrice cum se facea pana la urma ?  Huh

Mai bine sa completeze cineva articolul cu solutii decat sa se explice pe forum fiecare problema Smile
La fel poate completeaza cineva si la articolul cu solutii de la algoritmiada runda 1 Rolling Eyes
Memorat
proflaurian
Client obisnuit
**

Karma: 46
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #18 : Decembrie 22, 2012, 16:42:53 »

&Sergiu : Se poate observa ca


  • nu se pot lua doua numere ce rest 0 la impartirea cu K
  • pentru K par nu se pot lua doua numere care dau rest K/2 la impartirea cu K
  • daca luam numere de rest R atunci le putem lua pe toate ( exceptand cazurile de mai sus bineinteles )
  • daca luam numerele de rest R atunci nu putem luam numere cu rest K-R

Cam astea sunt ideile de la care poti sa pornesti si trebuie avuta in vedere o grupare pe seturi de cate K numere consecutive plus cele care raman la urma si din ele sa opresti numai numerele de resturi mici. 

& Comisie: Felicitari. Probleme frumoase. Pe mine personal m-a deranjat gruparea testelor dar bineinteles ca aici sunt subiectiv pentru ca am pierdut multe puncte la X    Evil or Very Mad .

& Dani. Cred totusi ca solutia cu KMP la problema X e pe complexitate optima. Eu am facut exact la fel cu Ciprian dar nu stiu exact unde am gresit pentru ca am pierdut 3 teste cu " incorect" . Nici vorba de iesire din timp.
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #19 : Decembrie 22, 2012, 16:50:46 »

Matrice6 cum se facea ? Eu nu m-am prins...

La X presupun ca era ceva dinamica , nu ? Am avut ceva idei insa nu am finalizat.

La X eu am retinut toRight[ i ] cel mai lung sir ce incepe pe pozitia i in sirul A si are literele identice cu sirul de aceeasi lungime din B (de pe pozitia 0): A[i+k]=B[k];  la fel si toLeft[ i ], doar ca A[i-k]=B[k].

Si ca sa calculezi toRight[ i ] si toLeft[ i ] in O(N) e o dinamica simpla ce se bazeaza pe ideea ca daca la pasul curent toRight[ i ] > 1 atunci la pasul urmator toRight[ i ] va fi diferit de 0 doar daca B[p] = B[p+1]. De fapt, ajunge sa vedem cate litere identice are sirul B la inceputul sau, pentru ca la fiecare pas din calcularea toRight[ i ] noi translatam sirul B de pe pozitia i pe pozitia i+1 in A.

A: YYYYYYYYYYYYYYYYY
i ->
B:   XXXXXXXX
i+1 ->
B:     XXXXXXXX

Deci toRight[i+1] va fi t=min( toRight[ i ] - 1, nrLitereIdenticeLaInceputulLuiB -1). (bine, plus cateva verificari sa nu iesim din sir). Deci, pentru pasul i+1 vom incepe sa comparam literele cu A cu cele din B incepand de la i+t (pentru ca stim sigur ca primele t sunt identice).

Evident, solutia va fi min(toLeft[x-1],toRight[y+1]).

LE: Acum am observat ca rationamentul e gresit intrucat nu se obtine complexitate liniara...  Whistle , ciudat ca a luat 100p.
« Ultima modificare: Decembrie 22, 2012, 23:44:59 de către Buleandra Cristian » Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #20 : Decembrie 22, 2012, 16:59:22 »

Felicitari pentru aceasta runda!  Applause Toate problemele au fost reusite. Imi explica si mie cineva cum se face Ismquery?
Memorat
elfus
Client obisnuit
**

Karma: 77
Deconectat Deconectat

Mesaje: 96



Vezi Profilul
« Răspunde #21 : Decembrie 22, 2012, 17:10:17 »

* Voce de SpiderMan * Cand se baga problemele in arhiva?
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #22 : Decembrie 22, 2012, 17:25:41 »

sunt curios care era solutia la subset2...  poate posta cineva ideea de rezolvare?
Eu am facut in felul urmator: un element x al carui rest prin impartirea la K este r nu poate fi pus in acelasi subset cu un element y al carui rest prin impartirea la K este K - r. Cele cu restul 1 nu pot fi puse in acelasi subset cu cele cu rest K-1, cele cu restul 2 nu pot fi puse in subset cu cele de K-2 etc. De aici se deduce urmatoarea idee: dintre toate elementele care au restul 0 prin impartirea la K poti pune intr-un subset doar un singur element (Evident, daca pui 2, suma lor % K = 0);  ai 2 cazuri:
1. daca K este impar, vei adauga in subset toate elementele care prin impartirea la K dau resturile 1, 2, ... K / 2 + un singur element care da restul 0. Pentru fiecare i de la 1 la N % K vei avea (N/K + 1) elemente care dau restul i, iar pentru fiecare i de la N%K + 1 la K/2 vei avea N/K elemente care dau restul i. Rezultatul va fi 1 (elementul cu restul 0) + Min(N%K, K/2) * (N/K + 1) + (K/2 - Min(N%k, K/2)) * (N/K).
2. daca K este par, vei adauga in subset 1 element care da restul 0 si 1 element care da restul K/2 (pentru ca daca adaugi 2, evident, suma lor % K va fi 0) si toate elementele care impartite la K dau resturile 1, 2, ... K/2 - 1. Similar primului caz, pentru fiecare i de la 1 la N%K vei avea (N/K + 1) elemente care dau restul i, iar pentru fiecare i de la N%K + 1 la K-1 vei avea N/K elemente care dau restul i. Rezultatul va fi 1 (elementul cu restul 0) + 1(elementul cu restul K/2) + Min(N%K, K/2 - 1) * (N/K + 1) + (K/2 - 1 - Min(N%K, K/2 - 1)) * (N/K).
Sper ca am fost destul de clar in exprimare Very Happy
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #23 : Decembrie 22, 2012, 17:50:20 »

OFF

* Voce de SpiderMan * Cand se baga problemele in arhiva?

Epic   Thumb up
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #24 : Decembrie 22, 2012, 19:38:16 »

Foarte haios, nu va inteleg "amuzamentul" pe baza mea, ce va deranjeaza pe voi faptul ca eu intreb dupa concurs cand se baga problemele in arhiva ?
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines