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:
The test case on which it is giving a wrong answer is:
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.
My python submission which tracks precision up to 18 decimal places using the Decimal class outputs
53.418336499999999534on that test case. It really is just precision.Here is the relevant comment from the programmer who added the hacks: https://mirror.codeforces.com/blog/entry/67743?#comment-1028372
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?
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.
Thank you so much, this same error had been driving me mad for a really long time :-)
Right, I shall do that. Thank you once again, you've really been a great help
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).
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 ??
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).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.
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).How dare you to blame C++? Blame yourself for not knowing its features, like
__float128type.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
Decimalin Python, and have since been trying to replicate that using__float128in 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, requiresquadmathto get printed. However, I don't think this approach would work when submitting on CSES, would it? Cause it requires-lquadmathto be added to theLIB_PATH, right?My knowledge isn't very vast regarding
__float128, so I apologize in advance for any obvious solutions which I might be missing.Don't rely on built-in printing approaches, write your own.
Oh okay, I'll try doing that. Thank you so much for your inputs
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.
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
nandarr[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.
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.
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.
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.