•dushmi
|
|
« : Mai 29, 2012, 21:42:57 » |
|
Aici puteţi discuta despre problema Radacina.
|
|
|
Memorat
|
|
|
|
•andreifirst
Strain
Karma: 4
Deconectat
Mesaje: 26
|
|
« Răspunde #1 : Mai 29, 2012, 21:48:10 » |
|
Testul 9 are ceva mai special? Caz particular?
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #2 : Mai 29, 2012, 21:51:39 » |
|
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.
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #3 : Mai 29, 2012, 22:06:45 » |
|
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 .
|
|
|
Memorat
|
|
|
|
•tzipleatud
|
|
« Răspunde #4 : Mai 29, 2012, 22:20:41 » |
|
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. Eu metoda aceasta am folosit-o, utilizand cautarea binara. Bafta!
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #5 : Mai 29, 2012, 22:28:58 » |
|
Multumesc ! .
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #6 : Mai 29, 2012, 22:31:27 » |
|
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 ).
|
|
|
Memorat
|
|
|
|
•darren
Client obisnuit
Karma: 106
Deconectat
Mesaje: 76
|
|
« Răspunde #7 : Mai 30, 2012, 08:47:58 » |
|
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. 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.
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #8 : Mai 30, 2012, 11:57:56 » |
|
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.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #9 : Mai 30, 2012, 14:34:31 » |
|
Eu in concurs am facut cu eps = 1e-10 si am luat punctaj maxim .
|
|
|
Memorat
|
|
|
|
•dushmi
|
|
« Răspunde #10 : Mai 30, 2012, 14:56:56 » |
|
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 .
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #11 : Mai 30, 2012, 15:04:07 » |
|
Poti sa le modifici. PS : Poti testa solutia cu wolfram alpha .
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #12 : Mai 30, 2012, 15:57:57 » |
|
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 ). 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?
|
|
|
Memorat
|
|
|
|
•dushmi
|
|
« Răspunde #13 : Mai 30, 2012, 16:28:12 » |
|
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.
|
|
|
Memorat
|
|
|
|
•darkseeker
|
|
« Răspunde #14 : Mai 30, 2012, 16:32:53 » |
|
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 .
|
|
|
Memorat
|
|
|
|
•dushmi
|
|
« Răspunde #15 : Mai 30, 2012, 16:42:51 » |
|
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).
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #16 : Mai 30, 2012, 16:59:45 » |
|
Multumesc, am inteles.
|
|
|
Memorat
|
|
|
|
|
•SpiderMan
|
|
« Răspunde #18 : Iunie 03, 2012, 14:28:12 » |
|
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.
|
|
|
Memorat
|
|
|
|
•paunmatei7
Strain
Karma: 28
Deconectat
Mesaje: 27
|
|
« Răspunde #19 : Septembrie 11, 2012, 08:38:16 » |
|
Nu inteleg fac la fel cum scrie in solutie si iau la 5 teste TLE.Ma ajutati va rog
|
|
|
Memorat
|
|
|
|
•visanr
|
|
« Răspunde #20 : Septembrie 11, 2012, 09:25:56 » |
|
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.
|
|
|
Memorat
|
|
|
|
•Mihai22e
Client obisnuit
Karma: 20
Deconectat
Mesaje: 74
|
|
« Răspunde #21 : Iulie 04, 2013, 15:18:49 » |
|
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.
|
|
|
Memorat
|
|
|
|
|
|