| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| What is test 35? | Egor | 1503. Многочлен | 6 мар 2023 02:52 | 1 |
What in 35 test, I always get WA
Edited by author 06.03.2023 04:44
Edited by author 06.03.2023 04:50 |
| hint: | xurshid_n | 1503. Многочлен | 23 июн 2012 19:02 | 1 |
hint: xurshid_n 23 июн 2012 19:02 |
| Test 5 | Plamen Markov | 1503. Многочлен | 16 июн 2012 04:15 | 4 |
Test 5 Plamen Markov 2 июн 2010 04:25 Someone give me test 5, please. 4
1
-10
35
-50
24
for example...
Answer:
1
2
3
4
Edited by author 28.02.2011 06:43 You can try this test:
5
1
-100
1
0
0
0
Answer (with true 20 digits precision):
0
0
0
0.010001000200050014004
99.989998999799949986 Re: Test 5 Amirbekov Artem[Ivanovo SPU] 16 июн 2012 04:15 I had WA on test 5 when I forgot to sort the result array. |
| Statement mistake | Yaroman | 1503. Многочлен | 26 июл 2011 12:03 | 3 |
Statement is mathematically incorrect and misleading: polynomial equations of degree > 4 are unsolvable by radicals.
Teacher (I assume, author as well) ought to be ashamed! You are mistaken - polinimials of degree > 4 can't be solved by CLOSED ANALYTICAL formula (Abel's theorem) but there exist numerical methods! There is no mistake: equations of degrees higher than FOUR cannot be solved in radicals in the general form, so equations of degrees higher than FIVE cannot be solved in radicals too. |
| what answer? | Vit Demidenko | 1503. Многочлен | 28 фев 2011 21:07 | 2 |
What answer for
3
1
0
3
0
?
0
0
0
or
0
? |
| how you compare doubles? | Baurzhan | 1503. Многочлен | 10 фев 2011 20:20 | 5 |
Persons, who got AC without long arithmetics,tell me how did you comapre doubles? I used construction: fabs(r-l)>eps,where eps=1e-15, and i'm getting wa5 every time. Please,somebody, help me to find the bug, I need it in my work to solve polinomial of 5-th degree.My code available for looking - my judge id - 77493FG, password - shared, last submissions - 1503 problem. If somebody will find bug in my code,please write it on this thread.
Edited by author 01.02.2011 09:52 I dont use binary-search with double all in my life but i think you can use long long instead of double, and for every expresion you devide the parameter by 10^7.
like this:
double a= 1.1234567;
cout << a * 1e-1 << endl; ---> 0.11234567
you can use:
long long a= 11234567;
cout << ((long double)a * 1e-7) * 1e-1 ---> 0.11234567
I hope can help you
Edited by author 10.02.2011 17:59 thanks for advice, but it seems impossible for me to use long long because my aim is not submit 1503 problem, but care about cases when coefficients of polinomial is large enough - 10^20,10^30 - i need it in my work.Long long doesn't allow to store such large numbers as I need. Also, I red in the forum that somobody accepted this problem with algorithm similar to mine, so my approach is correct but has some troubles with precision. Anyway, a lot of thanks for advice! |
| A HUGE hint | 2rf [Perm School #9] | 1503. Многочлен | 10 июл 2010 01:05 | 1 |
This problem can be easily solved using only double.
Just check if every integer number between -100 and 100 is a root of polynomial.
Edited by author 10.07.2010 01:07 |
| Has anybody had WA 14? | mai7 | 1503. Многочлен | 15 май 2010 22:20 | 3 |
I can't understand, why?! I've tried for many times to change accuracy value and borders of searching (is -10000..10000 enough?), can anybody? please, help me? There is fine mathematical theory about
precision for multyple roots(symbolic algebra of polinomials,Gries,...)
Acording it to achive precision 10^-6 will enouh to
use near 200 digits in all calculations. Thus Java
and BigInteger best way to pass tests. Did anybody solve this test without long arithmetics?
I found roots of a polynom and then check if they are roots of its derivatives to determine their repeatness, but got WA#14. Is there a better way to calculate roots? |
| precision questions (!) | nikonoff (ONPU) | 1503. Многочлен | 3 сен 2009 13:08 | 1 |
It is amasing, but I have AC without using long arithmetics and some advanced math!
Just recurrently solving equations P'(x) = 0 with binary search for polynomial roots between stationary points taking into account multiplicity of roots on each step.
C++ double is enough! with epsilon = 1e-12.
BTW. epsilon = 1e-9 give WA_35... |
| precision | Dirty Man | 1503. Многочлен | 30 янв 2008 16:16 | 14 |
Should i use long ariphmetics???
How should i correctly calculate the value of polynom for given variable? Interesting question. I think that is important to understand distinction between root and point of small value. Now i am solving 1503 but have wa9. I have program for finding all roots in complex plane but can't improve precision from 0.0001 to 0.000001. For it would enough to have float with 30 right digits. Question depend also on position of testmakers. I think that if we have
a +0.000001*i complex root then answer a+-0.000001 must be right. To approach root near 0.000001 we must have 30 digits int results. I've calculated precision up to last digit of standard pascal's type Extended, so, my precision should be up to 1e-16. But still WA #9...
Edited by author 03.11.2006 14:45 example:
x^5==0
x0=0-root;
x1=0.00001- bad value
but x1^5=1.0*E-25- very small My reqursive approach of solving equation P(x)=0 is: to solve equation P'(x)=0, and then binary search on all the intervals, whose ends are roots of equation P'(x)=0. So, I haven't problems with "excess psevdoroots", but still WA #9... Eqution P'(x)=0 is also bad because P'(x) may has multiple roots. It should start from d(N-1)P/dx=0 which is linear and go up applying binary search on each stage. If root multiple then on previous stage it was simple and is founded. As result all candidates for roots will be found with hight precision. The problem is to make choice which of them are roots of P(x)=0. Here we must use existence theoren of Sturm . Simplest variant is P(a)*P(b)<0=> x in [a,b]. I used with success long aritmetic and now on WA16.
AC finally.
In Java only using my BigFraction baseg on BigInt
I implemented famous Stourm's theorem which garantees
absolutely correct considering multiple roots
without any eps and so on.
But in question what degree of found multiple root
I needed in unknown constant h which garantes that if
d/dtP(t)!=0 and P(t)==0 than in (t-h,t+h) d/dtP(t)!=0.
I taken h=1e-12. In other words I think that if
P(t)==0 and in (t-h,t+h) exists t1 such that d/dtP(t1)==0
then t==t1.
h=1e-6 works also.
Edited by author 08.12.2007 19:43 Eqution P'(x)=0 is also bad because P'(x) may has multiple roots. It should start from d(N-1)P/dx=0 which is linear and go up applying binary search on each stage. If root multiple then on previous stage it was simple and is founded. As result all candidates for roots will be found with hight precision. The problem is to make choice which of them are roots of P(x)=0. Here we must use existence theoren of Sturm . Simplest variant is P(a)*P(b)<0=> x in [a,b]. I used with success long aritmetic and now on WA16. i do it more simply. int r[n] - array of int which represent roots P'(x) int i,j; for (i=0;i<n;i++) for (j=0;j<n;j++) if (i!=j) trytofindroot(P,r[i],r[j]); Edited by author 04.11.2006 15:41Should i use long ariphmetics???
How should i correctly calculate the value of polynom for given variable? I think it's impossible to calculate P(x) with given accuracy (10^-6), without long arrithmetics Fortunatelly, it is possible... :)
I don't know what in fact is the problem with test #9 but I had WA10 and the problem with is was the equal roots. If you concern about these particular cases, you won't have the need of long arrithmetics (I don't wish long float arithmetics to anyone!!!) And what problem with my approach, when P'(x) has multiple roots? At some stage we make binsearch from x to x, where x - multiple root, and, as a result, we'll get still 3 new roots of P(x). For input
5
1
0
0
0
0
0
my program outputs
0
0
0
0
0
I think, it is right answer. Isn't it?
Edited by author 06.11.2006 00:54 Fortunatelly, it is possible... :)quote>
and how I can do it? Vedernikoff Sergey: yes, this output is correct.
Alexander Prudaev: I had a precision error but eliminated it by checking whether the given function has zero value for the borders of the searching interval.
p.s. I am sorry for the late post. I haven't seen your posts (it might be usefull the admins to create an informational/notificational system)
Edited by author 17.01.2007 06:59
Edited by author 24.01.2007 02:22
Edited by author 24.01.2007 02:23 I solve it problem with long double!! Did you use Ferrary method or Euler solution for polynomial of fourth degree? I understood that you don't find root using general methods because of your time. |
| test 67 | svr | 1503. Многочлен | 7 дек 2007 10:08 | 1 |
What specific of test 67 may be?
I am using absolutely coorrect methods using
BigInteger and Sturm's theorem and in test 67 we have
situation when
1) (b-a)<1.e-21
2) exist t in (a,b) that p(t)==0
3) exist t1 in (a,b) that d/dtP(t1)==0
4) t!=t1
It Seems that hard to create such test.
Excuse me.
Was bag in polinom dividing.
Edited by author 08.12.2007 19:17 |
| TO ADMINS: test # 6 | Zhukov Dmitry | 1503. Многочлен | 17 дек 2006 00:20 | 3 |
I think, test #6 is incorrect.
Check it, please.
And for this case:
5
1
-11
47
-97
96
-36
answer =
1.000000
2.000000
2.000000
3.000000
3.000000
? I'm sure that test #6 is correct.
5
1
-11
47
-97
96
-36
answer =
1.000000
2.000000
2.000000
3.000000
3.000000
? yes
Edited by author 17.12.2006 00:47 |
| Clarification (+) | Vedernikoff Sergey | 1503. Многочлен | 4 ноя 2006 23:13 | 2 |
Is it guaranteed that all tests for this problem are "good", that is, among them there are no tests like
1
0
0
??? Read the problem statement more carefully. a0 <> 0
Edited by author 04.11.2006 23:15 |
| I am getting lots of WA in test4. can any one plz help? | mahbubul | 1503. Многочлен | 1 ноя 2006 00:44 | 3 |
Here is my code:
//See below new code
Edited by author 01.11.2006 00:44
Edited by author 01.11.2006 00:45 Try this test:
Sample input:
5
1
0
0
0
0
0
Sample output:
0
0
0
0
0 New code: WA in 43rd case:((
[code deleted]
Edited by moderator 29.12.2006 09:17 |
| Question | svr | 1503. Многочлен | 31 окт 2006 14:07 | 2 |
Number of solutions depend on untold rounding rules.
For exaple, let our algorithm gave comlex root
1+0.0000001*i. What descision, include 1 to real roots or not. For me right answer may vary in root numbers but contain in it's 0.000001 - neighbornhood ideal mathamatical set of roots. It seems that with type double and 16 righs digits in results the problem impossible to solve. For examle if we try compair solutions x1=0.999988 and x2=0.999982 for equation f(x)=(x-1)^4=x^4-4*x^3+6*x^2-4*x+1=0 computer
says that x2 is better. If we have 30-digits floats we would correct answer by optimization near initial approximation. If somebody knows internet resources with such module I shall be grateful. |
| What is Test#9? | xurshid_n | 1503. Многочлен | 31 окт 2006 11:26 | 1 |
My program always WA is TEST#9 |
| Changes for 1503 "Polynomial" (+) | Vladimir Yakovlev (USU) | 1503. Многочлен | 30 окт 2006 14:11 | 1 |
Problem statement was updated: "a0 ≠ 0" was added.
Validator was corrected.
Submissions made during contest and after contest have been rejudged. |
| sample output wrong | Alexander Prudaev | 1503. Многочлен | 30 окт 2006 04:50 | 4 |
"The accuracy must be not less than 10^-6"
i think we must replace 1 with 1.000000
how to output roots? "%lf"? "%0.6lf"?
and, there is an complex roots? this means, that you can use any output format, but the difference between your answer and correct answer should not be greater then 10^-6 read the statement!
"Output all real roots of the polynomial..." |
| To admins: Bad checker. | ICh(USU) | 1503. Многочлен | 29 окт 2006 13:40 | 1 |
It seems, that there is a bug with checker for problem 1503.
On some tests my program outputs "-0.000000", when i'v changed it to "0.000000" i'v got AC. |
