infoarena

Hai cu feedback-ul!!!!!!

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.

Da, trebuia sa dau testul 6 nu 5.

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

In rest, felicitari pentru probleme si organizare =D>

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

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.

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

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


Ciprian: Nu. Doar busesti tu ceva.

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.

Cine-i ăla ?  :aha:

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

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

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

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. 

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

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.

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)

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

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

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

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.

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

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

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

OFF


Epic   :thumbup:

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 ?

Defapt motivul pentru care luati si dumneavoastra si ciprian incorect este deoarece nu trebuie sa actualizati doar pozitia i - x + 1. trebuie sa actualizati si i - pi[ x ]  + 1, si i - pi[ pi[ x ] ] + 1, etc. deoarece si acelea sunt variante bune.  Chiar daca modificati, o sa luati TLE deoarece complexitatea este O(n ^ 2) (plus care ar mai fi scopul la Z daca ar merge KMP  :) ). Gruparea la X nu a fost facuta sever ca sa scada punctajele concurentilor radical. Parerea mea a fost chiar indulgenta si am lasat sa se ia 50 cu un brute.  Nu cred ca a fost cineva care merita 100 si s-a trezit cu 50.

la KMP eu faceam actualizarea in while, inainte de q = pi[q] avem match[i - q] = q si complexitatea ramane aceeasi. Iau un wa din cauza secventei s[n - m + 1 .. n] cred.

& Dani: Da. M-am prins de greseala mai devreme. Iar plangerea mea cu gruparea testelor nu era chiar o plangere. Mai degraba incearca sa o iei ca pe o gluma. Imagineaza-ti ca la teste foarte bine alese cu sursele noaste se puteau lua si 0 puncte. Cat despre KMP si Z-algorithm exista similitudini si deosebiri. Am sa vad dupa ce intra problema in arhiva cum sta treaba pentru ca tot mai cred (fara sa fiu convins 100%) ca, dupa calculul functiei prefix se poate scoate partea a doua in timp liniar. Ar fi O(N^2) daca s-ar actualiza la pozitiile acelea de mai multe or. Eu cred ca se poate face actualizare o singura data la fiecare pozitie.  Cum,  inca nu stiu sigur,  dar am sa ma straduiesc si daca reusesc am sa prezint varianta de rezolvare.

L.E. Cred ca tocmai a dat Vlad Campeanu raspusul in postul de mai sus.

Dar nici nu m-am gandit ca e o plangere  :). Stiu ca e nasol sa iti pice 2 teste si sa pierzi 50 de puncte, ca urmare am vrut sa explic lumii de ce am facut asta. Sa ii asigur ca nu au pierdut puncte nemeritat si ca asa trebuia si se presupunea sa fie.

La matrice6 x-ul,y-ul si p-ul contau?Daca da puteti sa imi dati un exemplu pentru care conteaza?Daca nu puteti sa imi spuneti raspunsul pt valorile urmatoare ale perechii (n,m):
(2,2)
(2,3)
(3,2)
(3,3)
(4,2)
(4,3)
(5,2)
(5,3)
Multumesc anticipat

Eu am rezolvat problema fara sa citesc x, y si p (era esential doar faptul ca e un element fixat). Mie imi da asa:

Sper sa te ajute, succes!

Cand dati update la rating?

Cand se vor afisa solutiile oficiale? Sunt tare curios sa vad rezolvarile.

Nu cred ca exista solutii "oficiale" :))
Solutiile vor aparea cand isi vor face timp cei care au luat 100 de puncte sa posteze cum au reusit :)

Atunci imi puteti spune si mie va rog cum ati facut problema ISMQUERY de 100 de puncte? M-am gandit si eu la o varianta cu arbori de intervale, insa nu am reusit sa finalizez nimic.

Multumesc anticipat.

La Ismquery eu am facut asa: am calculat un vector de indici pe care ii inserez intr-o stiva descrescator dupa valoare, si cand un indice e scos de un alt indice, al k-lea element mai mare ca el devine indicele care l-a scos. Initial, vectorul de indici este 1, 2, 3, ..., N, si k = 1 (e primul element mai mare decat cel scos din stiva). Apoi, cand calculez vectorul de indici, pun tot 1, 2, 3, ..., N, dar mai adaug inca N elemente in felul urmator: sa presupunem ca elementul i este "Next" pentru o multime de elemente Prev[ i ]. Toate acele elemente Prev[ i ] le inserez in vectorul de indici imediat dupa pozitia i. Astfel, acele elemente vor fi scoase din stiva de doua ori, odata de primul element mai mare decat ele si odata de al k-lea element mai mare decat ele (care se gaseste dupa pozitia i). De asemenea, in vectorul de indici am inserat 0 la sfarsit si am setat Value[0] = infinit, si mai trebuie avut grija ca daca la un moment dat Next[ i ][k] = 0, atunci si Next[ i ][k+1] = 0 (e posibil ca un element sa nu fie scos de 0, dar de fapt sa nu aiba al k-lea element mai mare ca el). Complexitatea e 2 * N * K + M, deci O(N * K + M).
Sper sa te ajute, succes!

Este o solutie mai "smechera", desi complexitatea teoretica e O(N^2 + M), merge struna, si zice asa : pentru fiecare element v[ i], descrescator dupa i, vrei sa completezi next[ i], lista cu solutiile. Astfel, pentru un i fixat, mergi in dreapta in cautarea elementelor > v[ i], astfel : daca v[j] > v[ i], atunci adaugi pe j in lista next[ i], altfel daca nu este, atunci te duci pe primul element din dreapta lui j mai mare decat acesta, si anume next[j][1], astfel o sa scapi de multe elemente "neiterate". Se pare ca merge foarte bine solutia, si e usor de implementat.

Are complexitate O(N^2 + M) ... Si cred ca se poate demonstra ca de fapt are complexitatea O(N * K + M) #-o
(Am fost spidermanit :|)

Merge bine din intamplare.
Ganditi-va cum merge pe input de genul asta.

10 1 2 3 4 5 6 7 8 9 11 1 2 3 4 5 6 7 8 9 10 12 1 2 3 4 5 6 7 8 9...

Solutiile bune se folosesc de o stiva, dupa cum descrie si Andrei in raspunsul sau.

L.E Nevermind.

Pai la asta ma gandeam ... Gandeste-te ca o sa ai o gramada de elemente care merg in O(K), si o sa ai foarte putine elemente care merg in O(X * K). Ca sa ai un element care merge in X * K, trebuie sa ai X * K elemente care merg in O(K) (e ca idee afirmatia, stiu ca nu e perfect corecta). Daca nu zic prostii atunci complexitatea e O(N * K)  :D

Da, greseala mea. Eram sub impresia ca testul ala iese N * sqrt(N), dar am vazut prost.

Eu am dat o solutie O( N log N + M ). Sortez indicii dupa valori in ordine crescatoare si la valori egale iau mai in fata indicele mai mare. Procesez indicii in ordinea data de sortare folosind o lista dublu-inlantuita cu indicii initiali si folosind doi vectori ( predecesor - succesor).
Imediat ce un indice este procesat este scos din lista. La momentul procesarii sunt sigur ca urmatoarele (cel mult) 5 pozitii cu valori  strict mai mari sunt exact urmatoarele (cel mult) 5 elemente din lista deoarece pozitiile cu valori strict mai mici sunt deja iesite din lista fiind deja procesate iar cele egale (daca exista) sunt situate mai la inceputul listei.