I was trying to solve a problem on HackerRank, Devu and a Journey on Metro.
I wrote a solution using BFS and top-down memoization. Here is my submission: Submission.
When I compared my output with the judge output, I found that I am getting Wrong Answer due to precision error. The 6th decimal place seems to be different on some cases. So I looked into the analysis to see if they had some trick to reduce the precision error. Well, they did the same thing but just bottom up.
Bottom up is faster than top-down. For some cases, we can even save memory using bottom up. But I never heard about bottom-up being more precise.
I changed all double variables into long double later, which got more test cases correct but not all. Submission.
Any idea what is going on? Why is this happening?