pfcntoorga's blog

Why the optimization of GNU C++ took me to Wrong Answer?
By pfcntoorga, 13 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

13 years ago, # |
  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
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    yep... It's internal mistake about GNU C++ compiler. So strange...

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    And almost all of these topics are about stupid errors in DNA. :D
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      it's true that the optimization of compiler has some bugs...
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Make your own code bugless before blaming compiler.

        (G++ bugs are known and mostly documented - this compiler is used by millions of programmers for more than 20 platforms - so be sure it is good enough product)

        → Reply
13 years ago, # |
  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
13 years ago, # |
  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