problem with codeforces compiler .

Блог пользователя Steven-_-AbuAlkhair

Автор Steven-_-AbuAlkhair, история, 2 года назад, По-английски

in this code

main (){
    
  int n  ; cin >> n  ;
  double  arr[n] ;
  for(int i = 0 ; i < n ; i++)cin >>arr[i] ;
        int cnt  = 0; 
  for(int i = 0 ;  i < n-1  ;  i++)
  
  for(int j = i +1 ; j < n ; j ++ )
   {
       double l = log10(arr[i]+arr[j])/log10(2);
       int r = l ; 
      if(l-(double)r==0) cnt++ ;
   }
   cout<<cnt ; 
  }

when input is

4 7 3 2 1 it gives cnt = 1 because the the compiler of codeforces when arr[i] =7 and arr[j]=1 gives l=3 but r=2 ! (it dosent happen in other compilers)

even this similar code gives wa i think because of the same reason 147734731 thanks .

casting, log, algorithms, compilers

-9

Steven-_-AbuAlkhair
2 года назад
8

Комментарии (5)

Показать архивные | Написать комментарий?

-is-this-fft-

2 года назад, # |

Don't use == to compare doubles.

→ Ответить

Steven-_-AbuAlkhair

2 года назад, # ^ |

i did this if ( fabs(l - (double)d) < 1e-9 ) cnt++ ; but it stil gives the same answer , i think there is a problem in casting because the DOUBLE << log10(7+1)/log10(2) = 3 >> != the INT << log10(7+1)/log10(2) = 2>> so , what modification should i do ? thanks.

→ Ответить

-is-this-fft-

2 года назад, # ^ |

← Rev. 5 →

Oh, are you trying to use int r = l to get r to be the value of l rounded?

Then I think your issue is that it always rounds down. If l = 2.99999999999, then r = 2. Floating point calculations introduce small errors like that, especially if you use log10 and division...

→ Ответить

-is-this-fft-

2 года назад, # ^ |

Two additional remarks:

It is possible to check whether a number is a power of two without using floats, for example by using __builtin_popcount.
Your approach is altogether too slow — $$$\Theta(n^2)$$$. Just trying all possibilities is almost always too slow in cp, you need some kind of clever idea.

→ Ответить

TerraByte

2 года назад, # |

Even after making a few changes, this still gives TLE Here
I basically took into account the precision errors that are commonly ignored when people use "double"

Here

main (){
    
  int n  ; cin >> n  ;
  double  arr[n] ;
  for(int i = 0 ; i < n ; i++)cin >>arr[i] ;
        int cnt  = 0; 
  for(int i = 0 ;  i < n-1  ;  i++)
  
  for(int j = i +1 ; j < n ; j ++ )
   {
       double l = log10(arr[i]+arr[j])/log10(2);
       int r = l ; 
      if(abs(l-(double)r)<1e-9) cnt++ ;
   }
   cout<<cnt ; 
  }

However, to solve it under given constraints, you can simply precompute the powers of 2 you want to attain :)
Like this

→ Ответить