10200 Prime Time

The forum to report every bug you find or tell us what you'd like to find in UVa OJ

Moderator: Board moderators

Locked
misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

10200 Prime Time

Post by misof » Sat Dec 16, 2006 8:55 pm

The problem statement causes notorious problems with rounding the output. As making a special corrector costs time, I suggest the following change instead: After:

Code: Select all

For each pair a,b read, you must output the percentage of prime numbers produced by the formula in this interval (a <= n <= b) rounded to two decimal digits.
Add a new paragraph:

Code: Select all

The rounding has to be done using the "round half up" rule: In case the exact result is exactly between two possible outputs, output the larger. Note that if you compute the answer as a decimal number and print it using standard output routines, you may sometimes get a different output due to the precision loss.
And preferably include Arne's input "1423 2222" and the corresponding output "44.13" among the examples.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Dec 17, 2006 11:06 am

Well, I don't see any reason why this is necessary... I think NO floating point operations is ever required in this problem, so...
Note that if you compute the answer as a decimal number and print it using standard output routines, you may sometimes get a different output due to the precision loss.
Isn't this general knowledge? Whenever one uses floating point operations, he should always think about the potential precision errors they may get, shouldn't he? Just think about all those problems unsolvable by float but solvable by double. Do you complain about those? :wink:

Just my humble opinion. Please don't bother to reply to it.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Dec 17, 2006 12:34 pm

Whenever one uses floating point operations, he should always think about the potential precision errors they may get, shouldn't he? Just think about all those problems unsolvable by float but solvable by double.

I think that there's a difference between "you use floats instead of doubles, get a precision loss of 1e-2 in the worst case, and thus fail" and "you get a precision loss of 1e-15 due to the fact that some real numbers cannot be represented exactly, and thus get a WA". In the first case, it's the problem solver's mistake. In the second case, it's just a nuisance that will make people spend hours looking for bugs they didn't make. They computed the exact answer as precisely as it could be represented, but still they don't get their AC just because they are printing it wrong.

I agree that no floating point operations are necessary. What I originally did in my solution was the following:

Code: Select all

// .. compute the count of good numbers (IMHO this is what the task is about)
good = ...
// now print the result
printf("%.2f\n",100.0 * good / all);
To get AC I had to:
- browse the old discussions at the forums
- find out about the rejudging
- change the one "printf" line into several statements that did the rounding manually

I think that in general "computing the answer", and not "printing the answer" should be the hard part of the problem. If this is not the case, the problem statement should be specific about it.

Either way, for this problem the problem statement as is is too vague, it doesn't specify the rounding mode, and the solver must guess the correct interpretation. This is never a good thing.

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos » Sun Dec 17, 2006 3:54 pm

can you just...

Code: Select all

printf("%.2f\n",100.0 * good / all+1.e-10);
I'd say there is no possible input which produces a 4999999999 rounding situation; thus, using +EPS should work out.

Anyway, I've slightly modified the description and added that sample to judge's output. What I don't want to add is that "Note that if you compute the answer as a decimal number and print it using standard output routines, you may sometimes get a different output due to the precision loss" sentence. That's also part of the problem solving skills (general knowledge, as Observer said) :-)

Is that solution ok for both of you?
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Dec 17, 2006 5:42 pm

Carlos wrote:can you just...

Code: Select all

printf("%.2f\n",100.0 * good / all+1.e-10);
I'd say there is no possible input which produces a 4999999999 rounding situation; thus, using +EPS should work out.

Anyway, I've slightly modified the description and added that sample to judge's output. What I don't want to add is that "Note that if you compute the answer as a decimal number and print it using standard output routines, you may sometimes get a different output due to the precision loss" sentence. That's also part of the problem solving skills (general knowledge, as Observer said) :-)

Is that solution ok for both of you?
Adding an epsilon before printing does produce an AC solution.
(I knew I can do this to get the "right" output, but from my point of view, this is just a workaround, a low level hack necessary to convince the judge that my output is right.)

The current version of the problem statement is clear enough and does show that this low-level hacking may be necessary, so I'm okay with it. Thanks.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Dec 17, 2006 5:55 pm

Carlos wrote:Is that solution ok for both of you?
Yes, I think it's good too. :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos » Mon Dec 18, 2006 12:45 am

I'll close the topic then :-DD
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.

Locked

Return to “Bugs and suggestions”