pfcntoorga's blog

Why the optimization of GNU C++ took me to Wrong Answer?
By pfcntoorga, 14 years ago, In English
I tried to submit my code with GNU C++ Compiler for 126A, then I got Wrong Answer on test #31 sadly.


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;

const double eps=1e-8;
int main()
{
    long long t1,t2,t0,x1,x2;
    cin>>t1>>t2>>x1>>x2>>t0;
    if (t1==t2)
    {
        printf("%I64d %I64d\n",x1,x2);
        return 0;
    }
    else if (t1==t0)
    {
        printf("%I64d 0\n",x1);
        return 0;
    }
    else if (t2==t0)
    {
        printf("0 %I64d\n",x2);
        return 0;
    }
    double t=10000000;
    long long a1,a2,sum=0;
    for (long long i=0;i<=(long long)x2;i++)
    {
        long long y1=((t2-t0)*i)/(t0-t1);
        for (long long yy=min(x1,max(0ll,y1-10));yy<=max(min(x1,y1+10),0ll);yy++)
        {
            double tt1=(double)(t1*yy+t2*i)/(double)(yy+i);
            if (tt1+eps>=(double)t0 && (fabs((double)t0-tt1)<fabs(t-(double)t0) || (fabs((double)t0-tt1)==fabs(t-(double)t0) &&
                                                                  yy+i>a1+a2)))
            {
                a1=yy;a2=i;
                t=tt1;
            }
        }
    }
    printf("%I64d %I64d\n",a1,a2);
}


But, strangely, I can pass the test #31 in my own IDE with GNU C++ Compiler just modify a little bit.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<string>
using namespace std;

const double eps=1e-8;
int main()
{
    long long t1,t2,t0,x1,x2;
    cin>>t1>>t2>>x1>>x2>>t0;
    if (t1==t2)
    {
        printf("%I64d %I64d\n",x1,x2);
        return 0;
    }
    else if (t1==t0)
    {
        printf("%I64d 0\n",x1);
        return 0;
    }
    else if (t2==t0)
    {
        printf("0 %I64d\n",x2);
        return 0;
    }
    double t=10000000;
    long long a1,a2,sum=0;
    for (long long i=0;i<=(long long)x2;i++)
    {
        long long y1=((t2-t0)*i)/(t0-t1);
        for (long long yy=min(x1,max(0ll,y1-10));yy<=max(min(x1,y1+10),0ll);yy++)
        {
            double tt1=(double)(t1*yy+t2*i)/(double)(yy+i);
            if (yy==4953 && i==4533) printf("%.10f\n",tt1);
            if (tt1+eps>=(double)t0 && (fabs((double)t0-tt1)<fabs(t-(double)t0) || (fabs((double)t0-tt1)==fabs(t-(double)t0) &&
                                                                  yy+i>a1+a2)))
            {
                a1=yy;a2=i;
                t=tt1;
            }
        }
    }
    printf("%I64d %I64d\n",a1,a2);
}

Then, I tried to disabled the optimizations of speed in the compiler. Surprisingly, I can also pass the test #31 with my first version.

Knowing that the optimizations of speed is enabled in Codeforces for GNU C++, I submitted my first version with MS C++ and got Accepted finally.

Why?


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

14 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Codeforces has become a great stress-test for C++ compilers, and it looks like GNU C++ definetily fails it :)

(there have been about 10 topics here about the code that is wrongly compiled by G++ with -O2 option enabled)

→ Reply
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I am sorry, but I hate topics like "my program works wrong - is it a bug in GCC?" - so I allow myself a bit of sarcasm.

Your program is a sinful collection of potential bugs, but what was critical in your case - you just forgot to use "eps" which you declared when it was necessary

replace
fabs((double)t0-tt1)-fabs(t-(double)t0)

with
fabs(fabs((double)t0-tt1)-fabs(t-(double)t0))<eps

→ Reply
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I think this problem is relevant to a question in C++ FAQ.  In short, the floating point processor may have more bits than double per register (which is the case with x86 architecture), and if GCC decides that some variable should reside in registers, some floating point operations become more precise than others.
→ Reply