Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

priojeet_priyom's blog

By priojeet_priyom, history, 5 months ago, In English,

I used double for this problem and my solution were hacked. when I changed the variable from double to long double it got accepted. hacked submission , accepted submission.

I tried printing out numeric limits of the double and long double with these

cout<<numeric_limits<double>::max()<<endl;
  cout<<numeric_limits<long double>::max()<<endl;

  cout<<sizeof(double)<<endl;
  cout<<sizeof(long double)<<endl;

OUTPUT: 1.79769e+308 1.18973e+4932 16 8

my question is how can double store 10^308 in 8 Byte memory. If it can, why it is giving WA for 10^18(approx problem limit)?

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

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Where is no better way to answer you question than go to google and read about how are floating point numbers made in C++.
why it is giving WA for 10^18
Double can't store all ~64 digits of numbers up to 10^18 (cause it's 8 byte), so here goes significant precision error.

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Yes, double can store numbers up to 10^308. But in order to archive this, it has to use some tricks. From the 8 bytes of data, 1 bit is used for the sign and 11 bits are used as an exponent e. The represented number will be equal to the remaining bits multiplied by 2e. This way it can also represent also very big numbers, but since only 52 bits are used for the actual number, it cannot represent every one of them accurately. E.g. try this short code:

double x = 1e18;
cout << (x + 1 == x ? "Equal" : "Not equal") << endl;

The precision is not good enough to distinguish between x + 1 and x. But that is not a new thing. There are obviously infinitely different numbers between 0 and 1, and you can't express everyone of them using double. And something like the following will also give the "wrong" result:

double x = 1;
cout << (x + 1e-30 == x ? "Equal" : "Not equal") << endl;

That's the dangerous thing about double. The values are usually only an approximation, and not the exact value.

For more information read: Double-precision floating-point format

Btw, there are lots of solutions to the problem without using long double. I've even saw a solution with float. I recommend learning from them, as long double will not be able to save you every time.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fun fact, cout << (x + 1 == x ? "Equal" : "Not equal") << endl; actually gives "Not equal" for numbers less than 2 * 1e19 (afaik even without optimizer).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Double starts giving Equal about 1e16. Long double start giving Equal about 2e19. Tested on my device.