AT_80's blog

Doubt in CSES' Inversion Probability after addition of new test cases
By AT_80, history, 17 months ago, In English

Recently, CSES updated the test cases of its problem Inversion Probability. This resulted in a large number of previously Accepted solutions getting a WA on one or more of the new cases.

My submission too was part of this. In particular, even after revision and rechecking from my side, it passes all but one of the 19 tests.
Here is the code:

Code

The test case on which it is giving a wrong answer is:

Input
Expected Output as per CSES
Output by my code

This, at least to me, seems like a scenario where my logic is certainly correct, but perhaps my implementation, or my understanding of how rounding of decimal point numbers in C++ works, is flawed.
And judging by the drop in the number of correct submissions after the addition of these new cases (was over 900 earlier, if I remember correctly, but is now at about 160), there definitely appears to be a catch in these new additions.

I tried the abovementined test case locally, and even at a 12 decimal point precision, the output was 53.418336500000
This only further perplxes me about where I am going wrong, as the question clearly mentions that half is to be rounded to even.
I would thus be really grateful if someone could explain what this is all about, and additionally, also advise me on how to correct my code.

  • Vote: I like it
  • +29
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
17 months ago, # |
  Vote: I like it +17 Vote: I do not like it

My python submission which tracks precision up to 18 decimal places using the Decimal class outputs 53.418336499999999534 on that test case. It really is just precision.

Here is the relevant comment from the programmer who added the hacks: https://codeforces.me/blog/entry/67743?#comment-1028372

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I certainly agree; it did feel weird that they wanted the exact answer instead of just a certain cut-off precision.

    Thank you so much for this.
    I still don't understand how to correct my submission though. If possible, could you please assist me with that too?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      To be honest, I do not understand precision enough to know why some C++ solutions AC and some WA. I would recommend just rewriting this one in Python and keeping track of the answer to high precision.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Thank you so much, this same error had been driving me mad for a really long time :-)

        → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Right, I shall do that. Thank you once again, you've really been a great help

        → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OP is right. 18 decimal places is not enough to get the correct answer. The answer is 53.4183365000000000000943313030 with 30 decimal places which is confirmed by the author of the hack (in the very link you provided).

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol why in test 17:

4 5 38 64 95

Exact answer is 0.920312500000000 (I calculate by calculator). So we need to write 0.920313 (because the next is 5) But "Correct" answer is 0.920312 ??

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    The reason for this is that the problem wants us to round half to even, i.e., whenever there is a number of the form ...ABC.DEX5000..., we must round it to ...ABC.DEX0000... if X is even, else to ...ABC.DEY0000... (where Y = X + 1, of course).

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rounding half to even is the default rounding method in C++ and other languages, so if your code calculates the answer accurately enough the rounding should work automatically.

This is what Antii told me when I had mailed him regarding the very same issue.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah, that was what I was expecting too, and as mentioned in the comment above (link), it turns out that the rounding off part isn't a problem, after all. The issue seems to be in the fact that C++ (or my submission, at least) isn't storing the number precisely enough for the program to realize that the final answer is just the slightest bit greater than 53.4183365000... (in this case).

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How dare you to blame C++? Blame yourself for not knowing its features, like __float128 type.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I certainly did not mean to insult or blame C++, and I am really sorry if I came across that way.
        In fact, just a few hours back, I managed to AC the problem using Decimal in Python, and have since been trying to replicate that using __float128 in C++, but without any success. It would be really helpful if you could give me any tips regarding that.

        The major issue I am facing pertains to how I should print the answer without losing the precision.
        As far as I know, __float128, being a non-standard C++ data type, requires quadmath to get printed. However, I don't think this approach would work when submitting on CSES, would it? Cause it requires -lquadmath to be added to the LIB_PATH, right?

        My knowledge isn't very vast regarding __float128, so I apologize in advance for any obvious solutions which I might be missing.

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Don't rely on built-in printing approaches, write your own.

          → Reply
          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh okay, I'll try doing that. Thank you so much for your inputs

            → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't know, I wrote a solution in Python using just integer arithmetic, so it should be always correct. If I get hacked, probably the author's solution is wrong.

And just because someone uses Decimal with xyz digits doesn't mean their solution will be correct.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah right, that's actually a great idea. I too will try coding something like that.
    One doubt though, about the second part of your comment.

    Given that both n and arr[i] are within $$$[1, 100]$$$ in the question, it feels intuitive to me that there shouldn't be a calculation which gives an offset from $$${10^{-6}}$$$ so minute that even a 128-point precision cannot keep track of it.
    This thus makes me think (albeit without any formal proof) that Decimal should be sufficient to tackle this problem. Would really like to know your thoughts on this.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      If you think about the resulting fraction in the answer, it could be $$$\frac{a}{b}$$$, with $$$a$$$ and $$$b$$$ being huge numbers. Because if you add fractions, then the denominator could become as big as the $$$LCM$$$ of all the denominators of the individual fractions. This intuitively could give something like $$$LCM(1,\dots,100)$$$ in the denominator. With a clever testcase, this can be exploited to give a number really close to the rounding point, but just a bit above or under it.

      So I guess there's some value of "calculate with xyz digits of precision", where it will actually be correct, it is just really big.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Oh yes, that makes sense. I had thought about this kind of a worst-case scenario, but it hadn't struck me that we could come up with such a close-shave test case. Was, for some reason, a little counter-intuitive to me. I do understand it now though.
        Thank you so much.

        → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was not able to get the AC in C++, so I coded it in Python using decimal library.

However, I am curious to know if C++ provides easy-to-use means of computing floating point values with higher precision than long double offers.

→ Reply