Блог пользователя TranThuyLuc

Автор TranThuyLuc, 7 лет назад, По-английски

In many contest problems in Codeforces where the results require float point number, there is often something like this:

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

However, the normal way to check whether two float point numbers are equal is something like this:

const double EPS = 1e-9;

bool isEqual(double x, double y){
    return abs(x - y) < EPS;
}

Is the way Codeforces use more precise? Should I use this way for comparing float point numbers instead of the normal way?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

I think they use both ways and your answer is considered correct if it's equal to the jury's answer by at least one of the two ways. More information here.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I think so.

    Anyway, the first way tends to work better for me, especially when I need to compare an integer with a double.

    Is there any reason to use the second way instead of the first way?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you define better in this case?

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        As stated in the formula, the first way also considers with the magnitude of 2 numbers.

        Therefore in case of comparing very large numbers and the precision preserved is very small, the first way will output more precise result.

        Moreover, when I extend this formula to support smaller and larger operators, the first way seem to be the only way.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

If the checker uses testlib, then the source code used is available at GitHub.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится
  1. A large fraction of contest problems uses Testlib for checkers. The standard Testlib checkers include both absolute-or-relative error and absolute error checkers.

  2. Note that the absolute-or-relative check accepts strictly more answers than just the absolute check. For numbers less than one in magnitude (probabilities are an example), they are essentially the same. For large numbers, however, the absolute-or-relative check accepts more answers.
    As an example, consider EPS=1E-9 and answers of order 1E+6. If the jury answer is 1 000 000, the relative error check accepts numbers 999 999.999 through 1 000 000.001. As most solutions to contest problems use floating point for real numbers, the relative error check makes a lot of sense here.

  3. The Testlib accounts for double precision at the point of comparison as well, see what TianyiChen linked.