infoarena

Aici puteţi discuta despre problema Radacina (http://infoarena.ro/problema/radacina).

Testul 9 are ceva mai special? Caz particular?

Nu. Ca fapt divers, cand faci cautare binara pe numere reale si urmaresti o anumita precizie, incearca sa faci un numar fix de iteratii, suficient de mare incat sa obtii precizia dorita. Gen eu aici am exact 50 de iteratii si nu ma joc cu niciun eps  :) Sa-mi spui daca nu rezolvi.

Cum pot determina un interval pe care functia este strict monotona ? Adica eu ma bazam pe faptul ca solutia e intr-un interval de forma [k,k + 1] ,determinam acest interval vazand in ce puncte intregi consecutive functia schimba semnul si iteram fiecare numar din acest interval cu o precizie de 10 ^ 5. Totusi nu trece testul 8 nicicum .

Poate te ajuta asta. (http://en.wikipedia.org/wiki/Bisection_method) Eu metoda aceasta am folosit-o, utilizand cautarea binara. Bafta!

Multumesc ! .

Nu ai nevoie sa gasesti intervalul de care vorbesti. Toata ideea e ca daca ai doua valori left si right astfel incat P(left) < 0 si P(right) > 0 (sau invers) atunci sigur ai o radacina in intervalul [left , right]. Iti iei o valoare X in intervalul asta. Daca P(X) < 0 restrangi intervalul la [X , right] altfel la [left , X] (sau simetriile implicite). Toata ideea e sa-ti mentii tot timpul semne diferite in capete ca sa fii sigur ca ai o solutie in intervalul respectiv. Daca alegi X-ul ca fiind mijlocul intervalului, se restrange super repede :).

Daca te gandesti un pic, tu nu urmaresti niciodata o anume radacina. Doar te duci incotro stii ca exista una.

Tot ce mai ramane e sa-ti gasesti valorile left si right initiale. -20 si 20 sunt ok pentru asta.

L.E. Da, in mod nesurprinzator chestia asta are un nume :)).

In concurs am incercat o rezolvare la care cautam din eps in eps, in intervalul (-20, 20), si testam fiecare valoare. eps l-am fixat pe 0.00001, si am luat 3 TLE-uri.
Am incercat dupa sa mai jonglez cu valoarea eps-ului, si se pare ca ia 100 cu 0.00002. :-k Ar trebui sa se poata gasi teste pentru care sa ia WA solutia asta.
Probabil s-ar putea rezolva si din limita de timp (am timpul maxim 32ms cu solutia asta, pe cand cu cautarea binara am ~0ms). Cu eps 0.00005 ia WA, deci daca limita ar fi cam 0.01s-0.02s, cred ca ar elimina si aceasta solutie.  :)

Da, am vazut ca in arhiva au aparut solutii cu eps. A fost destul de bine calibrata treaba totusi, n-a reusit nimeni sa faca asta in concurs. Si oricum te costa multe puncte sa tot incerci precizii diferite & stuff. Probabil o sa mai modificam testele un pic cand avem timp.

Eu in concurs am facut cu eps = 1e-10 si am luat punctaj maxim :).

Ei discutau despre solutia in care parcurgi pas cu pas fiecare numar dintre -20 si 20, nu despre solutia in care faci cautare binara :|.

Ontopic: O sa modific eu testele :). Nu m-am gandit ca va lua cineva din 2 in 2 :D.

Poti sa le modifici.
PS : Poti testa solutia cu wolfram alpha :).

De ce -20 si 20 sunt ok ca valori initiale? Pt polinomul P (x) = (x-1) * (x - 2) vom avea P (-20) > 0 si P (20) > 0. Cum gasim valorile initiale?

Tocmai din aceasta cauza gradul este impar. Pentru polinoamele de grad par limita la -inf si la inf este egala, pe cand la cele de grad impar cele doua limite sunt diferite.

Eu cred ca valorile acelea sunt bune deoarece se garanteaza ca intre ele exista o solutie . Poti lua un polinom de grad 3 de exemplu x ^ 3 + 2 x ^ 2 + x + 10000 , pentru care atat p(-20) cat si p(20) sunt pozitive .

In problema se garanteaza faptul ca toate radacinile sunt in intervalul (-20, 20) de unde rezulta ca pentru x <= -20 si pentru x >= 20 sigur nu mai este taiata axa Ox. Tinand cont si de faptul ca semnele limitelor la -inf si +inf sunt contrare (G impar) => semnul lui P(x) pentru x <= -20 este diferit de semnul lui P(x) pentru x >= 20, adica fix ceea ce ne trebuie (2 puncte, -20 si 20, pentru care semnele cu siguranta sunt contrare).

Multumesc, am inteles.

Ajutati-ma va rog cu testul 2, iau NON ZERO EXIT STATUS si deja le-am incercat pe toate, se pare ca e o problema la citire din fisier deoarece cind exclud totul si ramine doar citirea da aceeasi eroare ](*,) ](*,)

Testele sunt bune, din cate mi se pare la Pascal cred ca eroarea aia vine de la o impartire la 0. Citeste mesajele de eroare de pe IA si vezi.

Nu inteleg fac la fel cum scrie in solutie si iau la 5 teste TLE.Ma ajutati va rog :D

In primul rand, nu te folosesti de faptul ca trebuie sa ai semne diferite la capetele unui interval (in cautarea binara). In al doilea rand, daca vrei sa vezi daca p e un numar natural (in cazul nostru sa fie 0), trebuie sa iti alegi o precizie (sa zicem 0.0001) pt a elimina erorile de precizie.

Daca am un polinom in care P(-20) > 0, P(20) > 0 si P(0) > 0, de unde stiu in ce directie sa ma duc dup'aia? Am reusit sa fac problema, dar nu-mi dau seama cum merge pe acest caz.  :)

In cazul asta nu cred ca are importanta in ce directie o iei, fiindca exista in ambele parti cel putin o solutie. Uita-te la graficele polinoamelor de grad impar: http://www.purplemath.com/modules/polyends.htm.