Feedback Runda 1

[•eudanip]

Hai cu feedback-ul!!!!!!

[•darren]

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.

[•eudanip]

Da, trebuia sa dau testul 6 nu 5.

[•scipianus]

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

In rest, felicitari pentru probleme si organizare

[•Cristy94]

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 )

[•danalex97]

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.

[•tzipleatud]

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

In rest, felicitari pentru probleme si organizare

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 

[•eudanip]

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

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

In rest, felicitari pentru probleme si organizare

Ciprian: Nu. Doar busesti tu ceva.

[•scipianus]

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.

[•danalex97]

Se facea cu Z-Algorithm.

Cine-i ăla ?  

LE : Am gasit : http://codeforces.com/blog/entry/3107.

[•eudanip]

Se facea cu Z-Algorithm.

Cine-i ăla ? 

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

[•Challenge]

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.  
Problema ismquery putea fi trasa de par cu o solutie N*(logN+5)+M daca se parsa si citirea si afisarea.  

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.  

[•eudanip]

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. 
Problema ismquery putea fi trasa de par cu o solutie N*(logN+5)+M daca se parsa si citirea si afisarea. 

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. 

[•harababurel]

sunt curios care era solutia la subset2...  poate posta cineva ideea de rezolvare?

[•Schumi]

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.

[•mihaipopa12]

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.  
Problema ismquery putea fi trasa de par cu o solutie N*(logN+5)+M daca se parsa si citirea si afisarea.  

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

[•danalex97]

Matrice cum se facea pana la urma ? 

[•scipianus]

Matrice cum se facea pana la urma ? 

Mai bine sa completeze cineva articolul cu solutii decat sa se explice pe forum fiecare problema
La fel poate completeaza cineva si la articolul cu solutii de la algoritmiada runda 1

[•proflaurian]

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

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

[•Cristy94]

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...  , ciudat ca a luat 100p.

[•Mihai22e]

Felicitari pentru aceasta runda!  Toate problemele au fost reusite. Imi explica si mie cineva cum se face Ismquery?

[•elfus]

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

[•Mihai22e]

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

[•danalex97]

OFF

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

Epic  

[•SpiderMan]

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 ?