In the latest contest, i got trouble in problem H.
When i want to compare x is lager than y, i use x>y+eps (i learn this from a book), but i get WRONG ANWSER , but when i just use x>y ,then i accept .
I just wonder which one is true. Thx first.
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | djm03178 | 152 |
In the latest contest, i got trouble in problem H.
When i want to compare x is lager than y, i use x>y+eps (i learn this from a book), but i get WRONG ANWSER , but when i just use x>y ,then i accept .
I just wonder which one is true. Thx first.
Name |
---|
In my experience, I've only seen epsilons used when comparing for equality, not for greater-than or less-than.
I can see where the y + ε comes from — we consider x and y to be equal if they are within ε of each other, so it makes sense that for a "strictly greater than" operation we would rule that out — but I think we can make a safe assumption that a greater-than or less-than relationship is, unlike equality, preserved in floating-point operations, if you're not going to the limit of the number's precision boundary. This is relevant.
(Anyone please feel free to prove this incorrect if you have a counterexample.)
i think you use a large eps, try smaller one
try 1e-15 for example
Contrary to popular belief that you always need to use eps when working with floating point numbers, there are some situations when eps is not needed and it may decrease the precision. If it was like that then it would be builtin. Keep in mind that floating points are deterministic and they perform operations correctly within limits of their precision, and performing operation with the same arguments twice will give exactly the same result. I will give some examples:
When possible try to think of what problem are you trying solve by using eps and choose appropriately. It depends on the task if it is worse to have false positives or false negatives.
Thanks for your detail explanation. :-p