sajidhasan2021's blog

By sajidhasan2021, history, 6 weeks ago, In English

I was solving Div.2 114A. I have used the log function to solve this problem and repeatedly get wa for the 9th test case. I got the correct answer for that test case in codeblocks and idone but I got wrong answer for that test case in codeforces. My question is does the log function not always give the correct value or does the answer vary from compiler to compiler? Submitted code : https://codeforces.com/contest/114/submission/85798651

Thank you.

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

»
6 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

I tried adding following function to check what's going on and the result is


#include"bits/stdc++.h" using namespace std; void cmp(double x, int y) { cout << setprecision(50) << x << " " << y << " " << x - y << endl; } int main() { int n,m; cin>>n>>m; double a; a=log(m)/log(n); int b=a; // cmp(a, b); if(a==b) { cout<<"YES"<<endl; cout<<a-1<<endl; } else cout<<"NO"<<endl; return 0; }

When I comment out call of cmp the result is as it was, you get WA, but when adding it all of a sudden you get correct answer (at least on 32 bit machine with g++, on clang you get correct answer) here you have an explanation why sth like this can happen: https://www.linuxtopia.org/online_books/an_introduction_to_gcc/gccintro_70.html, but for uses in cp you don't really need to understand why it happens, what you need to know is that there is some (possibly nondeterministic) function fl such that $$$\frac{|f(x) - x|}{|x|} \leq \nu$$$, where $$$\nu$$$ is roughly $$$10^{-7}$$$ for floats, $$$10^{-16}$$$ for doubles and $$$10^{-19}$$$ for long doubles and whenever you apply any operation involving floating point, e.g. $$$a + b$$$ actual result is $$$fl(a + b)$$$ (except when overflow/underflow occurs)

In particular since any value you will calculate will be passed through $$$fl$$$ function multiple times comparing floats with == will hardly ever return true (and by != hardly ever return false). If you want to compare two double values do $$$abs(a - b) \leq \varepsilon$$$ for some small value of $$$\varepsilon$$$ (checking if something is an integer is the same as checking if it is equal to llround(x)). When the calculation is so short as in this problem eps = 1e-10 is usually fine, but if we want to be more rigorous we need to estimate how close to an integer a number of form $$$\log_{a}(b)$$$ with $$$2\leq a, b < 2^{31}$$$ be if it's not an integer.

$$$\frac{\log{a}}{\log{b}} - k = \frac{\log{a} - k\log{b}}{\log b} = \frac{\log{a} - \log{b^k}}{\log b}$$$ By Lagrange mean value theorem there is $$$\xi$$$ in $$$[a, b^k]$$$ (or $$$[b^k, a]$$$) such that $$$\log{a} - \log{b^k} = \log'(\xi)(a - b^k) = \frac{(a - b^k)}{\xi}$$$. Numerator is an integer and we assumed it's not $$$0$$$, so it's at least $$$1$$$ by absolute value, denominator is at most $$$2^31 \approx 2\cdot 10^9$$$, so we're off by at least $$$5\cdot10^{-10}$$$ divided by $$$\log(\xi)$$$, which is at least $$$\log(2) \approx 0.69$$$ (but of course assuming it's $$$\approx 1$$$ is good enough), so $$$|\frac{\log{a}}{\log{b}} - k| \geq \frac{1}{2\cdot10^9\log{2}} > 10^{-10}$$$, value we will actually calculate is off by roughly $$$10^{-19}$$$ if we use long doubles, so picking any epsilon in between will be fine. If on the other hand it turned out actual value can be off by e.g. $$$10^{-24}$$$ it would mean floating points aren't enough to determine if result is an integer and we need to find some different solution