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

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #25 : Decembrie 22, 2012, 19:59:15 »

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


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  Smile ). 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.
Memorat
vld7
Strain


Karma: 7
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #26 : Decembrie 22, 2012, 21:48:16 »

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.
Memorat
proflaurian
Client obisnuit
**

Karma: 46
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #27 : Decembrie 22, 2012, 22:23:59 »

& 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.
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #28 : Decembrie 22, 2012, 23:34:54 »


Iar plangerea mea cu gruparea testelor nu era chiar o plangere. Mai degraba incearca sa o iei ca pe o gluma.


Dar nici nu m-am gandit ca e o plangere  Smile. 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.
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #29 : Decembrie 23, 2012, 21:36:03 »

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
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #30 : Decembrie 23, 2012, 22:27:06 »

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:
Cod:
19
121
121
1665
771
22979
4913
317259

Sper sa te ajute, succes!
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #31 : Decembrie 25, 2012, 17:10:32 »

Cand dati update la rating?
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #32 : Decembrie 26, 2012, 13:08:37 »

Cand se vor afisa solutiile oficiale? Sunt tare curios sa vad rezolvarile.
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #33 : Decembrie 26, 2012, 13:16:14 »

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

Nu cred ca exista solutii "oficiale" Smile)
Solutiile vor aparea cand isi vor face timp cei care au luat 100 de puncte sa posteze cum au reusit Smile
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #34 : Decembrie 26, 2012, 15:20:56 »

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.
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #35 : Decembrie 26, 2012, 17:42:26 »

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!
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #36 : Decembrie 26, 2012, 17:47:35 »

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.
« Ultima modificare: Decembrie 26, 2012, 18:43:01 de către Simoiu Robert » Memorat
deneo
Vorbaret
****

Karma: 185
Deconectat Deconectat

Mesaje: 160



Vezi Profilul
« Răspunde #37 : Decembrie 26, 2012, 18:07:52 »

Are complexitate O(N^2 + M) ... Si cred ca se poate demonstra ca de fapt are complexitatea O(N * K + M) d'oh!
(Am fost spidermanit Neutral)
« Ultima modificare: Decembrie 26, 2012, 22:01:29 de către Adrian Craciun » Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #38 : Decembrie 26, 2012, 18:32:22 »

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.
« Ultima modificare: Decembrie 26, 2012, 21:17:57 de către Mihai Calancea » Memorat
deneo
Vorbaret
****

Karma: 185
Deconectat Deconectat

Mesaje: 160



Vezi Profilul
« Răspunde #39 : Decembrie 26, 2012, 20:48:23 »

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)  Very Happy
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #40 : Decembrie 26, 2012, 21:16:55 »

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

Karma: 46
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #41 : Decembrie 29, 2012, 03:46:50 »

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. 
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

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