ShubhamAvasthi's blog

By ShubhamAvasthi, history, 2 months ago, In English

I solved a problem recently using floating point arithmetic. I suspect the solution should not work for some test case because of floating point precision errors, but cannot find a case where it would fail. Moreover, the solution gets "Accepted" verdict.

Link to the submission (Codeforces Round #660 E): 89366718

The submission is an implementation of the Convex Hull Trick approach mentioned in the editorial of the problem.

If you look through the code, you will find that I have maintained forbidden ranges of cotangents of an angle and then iterate over the critical angles (i.e. extremeties of some range of forbidden angles, which are not forbidden themselves).

I suspect that float(xr[j] - xl[i]) / (y[i] - y[j]) should return unequal values for some mathematically equal fractions (like $$$5/3$$$ and $$$15/9$$$) because of precision errors.

In such case, let's say there are two ranges $$$[a, b]$$$ and $$$[c, d]$$$ with $$$b = c$$$ (mathematically). In such a case a possible value that is not forbidden is $$$b$$$. This obviously will not work if there are precision errors which make the calculated values of $$$b$$$ and $$$c$$$ such that $$$b$$$ is slightly greater $$$c$$$. Then, $$$b$$$ will become part of a forbidden range.

My question is, does the above case not show up in the test cases of the problem or is the floating point arithmetic in my code guaranteed to be exact because of some reason?

Can you suggest a case where the program would break?

The following program shows though that the precision errors I mentioned do occur:

#include <cassert>
#include <iomanip>
#include <iostream>
#include <random>
using namespace std;

float foo (int n, int d, int c)
{
    return float(n * c) / (d * c);
}

int main()
{
    default_random_engine generator;
    uniform_int_distribution<> dist(1, 10000);
    while(true)
    {
        int n = dist(generator), d = dist(generator), c1 = dist(generator), c2 = dist(generator);
        float f1 = foo(n, d, c1), f2 = foo(n, d, c2);
        cerr << "Testing with n=" << n << ", d=" << d << ", c1=" << c1 << ", c2=" << c2 << '\n';
        cerr << fixed << setprecision(10) << "Received f1=" << f1 << " and f2=" << f2 << '\n';
        assert(f1 == f2);
        cerr << "OK\n";
    }
}

Read more »

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

By ShubhamAvasthi, history, 9 months ago, In English

I tested the following code with three different compilers and saw some peculiar results. First of all, I am not sure why the program compiles (no errors with isalpha) indicating that cctype/ctype.h is being automatically included allowing the compilation of the program.

As far as I know and according to cplusplus.com, neither cctype namespace nor ctype.h header file is amongst the automatically included header files for iostream. Also, iostream does not inherit from cctype/ctype.h.

#include <iostream>
using namespace std;

int main()
{
	cout<<isalpha('a');
}

On my local machine with MinGW (32 bit), it prints 2.

On Codeforces compiler, it prints 2.

On ideone, it prints 1024.

All the above compilations were done for C++14.

It would be great if someone could share the reason for this behaviour.

Read more »

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

By ShubhamAvasthi, 3 years ago, In English

I am sure that my submission for problem A is correct, but the judge says "Idleness Limit Exceeded". It may be due to some issue with C++17 Diagnostics, which I mistakenly selected during the contest to submit the problem. What should I do now?

UPD: Thank you Reyna for putting it on rejudge.

UPD2: The submission got accepted.

Read more »

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