rationalisering — more issues with floating-point numbers

rationalisering — more issues with floating-point numbers

By xiaowuc1, 6 hours ago,

I was motivated to write this blog post after reading this blog post about possible precision issues in output and requiring printing a rounded answer exactly instead of printing an answer within a tolerance. This blog post feels somewhat related insofar as that it has an issue with floating point numbers, and also a doubt as to the correctness of the underlying data. Alternatively, someone can find the mistake in my logic.

The problem in question is Rationalization which asks to find a positive rational that is within a range . Among all such fractions, minimize , and among all such with minimal , minimize . The judge data guarantee that .

My solution path is as follows: If , then . Therefore, we can just check all in increasing order and find the smallest where contains some integer, and the smallest such integer should be our .

Now, and are floating-point numbers, so in order to make sure that we can represent and exactly, we scale them up by powers of 10 until they are exactly integers. Fortunately, we're guaranteed that these numbers are written in decimal form.

This gets 60 points on Kattis with a WA verdict on the final subtask, so it does print something which is deemed incorrect (as opposed to printing nothing or printing a value of that is too large and getting RTE). Since the solution does pass the first two subtasks, I am reasonably confident that it is not completely wrong. I presume that the second subtask is meant to admit solutions that have precision issues by representing values using floating point values (perhaps by scaling each of the floating point values directly by ), though I haven't bothered to experiment much there.

I do have a weak prior that some Kattis problems with floating point numbers do something incorrect — for example, for this problem, all reference solutions say that three points are collinear if and only if the turn would be at most degrees, as opposed to checking collinearity exactly.

Because of this prior, I'd like to identify the test case to see where I went wrong. Sadly, I can't find the input data for this problem, so I'm stuck trying to find a bug in my solution/logic or conclude the test data are wrong. I'd just like to ask the author for test case 77 to verify it by hand. In the interim, I might be able to get the test case in a few hours if I can find a way to AC the first 76 cases and differentiate that I'm in test case 77. (Kattis only allows 10 submissions within a 10 minute window.)

Alternatively, did I go wrong somewhere?

Update 1: Test case 77 has c = 7.80212 and f = 0.0000000684. I wrote a slow program that seems to generate the same output as what my program prints.

This fraction is not equal to either of and .

Update 2: jeroenodb was able to AC the problem and with his solution we were able to prove that the test data are indeed incorrect. I have contacted Kattis to try to get this rectified.