Using std::ceil() gives wrong answer but editorial method works. Why??

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Problem Link : 1995C - Squaring

I have tried to implement the float method from the editorial.

I am using base 2 for log here. In the first code, I am calculating the difference of b[i-1] and b[i], tmp is the number of times log(2)=1 has to be added into b[i]. If b[i-1]-b[i]>0, We are adding it's ceil value to the total operations ( ops ) and also to b[i] itself.

However this solution gives wrong answer on test-case 2, my guess is my outputs are bigger than answer expected.

Note: I have removed input templates from codes to make them short, rest is intact. You can also refer to the submission links.

Code with wrong answer

code with ceil()

#include "bits/stdc++.h"
using namespace std;

// ================================== Macros ======================================================
#define int long long int
#define double long double
#define uint unsigned long long
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vvb vector<vector<bool>
#define vp vector<pair<int,int>>
#define pb push_back
#define el(a,v) for(auto& a : v)
#define fr(i,n) for(int i=0;i<n;i++)
#define rf(i,n) for(int i = (n)-1;i>=0;i++)
#define rep(i,a,n) for(int i=0;i<=(a);i++)
#define sz(v) = (int) v.size()
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define srt(v) sort(v.begin(),v.end())
#define rev(v) sort(v.rbegin(),v.rend())
#define dbg(var) cout<<#var<<" = "<<var<<nl;
#define unq(v)  v.resize(distance(v.begin(), unique(v.begin(), v.end())))
#define nl "\n"
#define ws " "


const int  MOD=1e9+7; 
const int INF = INT64_MAX-4;
void solve() {
    int n;cin>>n;
    vector<int> v(n);
    int ops = 0;
    cin>>v;

    reverse(v.begin(),v.end());
    while(v.back()==1)v.pop_back();
    el(a,v){
        if(a==1){
            cout<<-1<<nl;
            return;
        }
    }
    reverse(v.begin(),v.end());
    // dbg(v);
    n=v.size();
    vector<double> b(n);

    fr(i,n){
        b[i] =log2(log2(v[i]));
    }

    // dbg(b);

    for(int i =1;i<n;i++){
        int tmp = max((double)0.0,ceil(b[i-1]-b[i]));
        b[i]+=tmp*log2(2);
        ops+=tmp;
    }
    cout<<ops<<nl;
}


int32_t main()
{
 
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

submission : 272991530

While this code works

working code

#include "bits/stdc++.h"
using namespace std;

// ================================== Macros ======================================================
#define int long long int
#define double long double
#define uint unsigned long long
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vvi vector<vector<int>>
#define vvb vector<vector<bool>
#define vp vector<pair<int,int>>
#define pb push_back
#define el(a,v) for(auto& a : v)
#define fr(i,n) for(int i=0;i<n;i++)
#define rf(i,n) for(int i = (n)-1;i>=0;i++)
#define rep(i,a,n) for(int i=0;i<=(a);i++)
#define sz(v) = (int) v.size()
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define srt(v) sort(v.begin(),v.end())
#define rev(v) sort(v.rbegin(),v.rend())
#define dbg(var) cout<<#var<<" = "<<var<<nl;
#define unq(v)  v.resize(distance(v.begin(), unique(v.begin(), v.end())))
#define nl "\n"
#define ws " "


const int  MOD=1e9+7; 
const int INF = INT64_MAX-4;
const double eps = 0.000000001;


void solve() {
    int n;cin>>n;
    vector<int> v(n);
    int ops = 0;
    cin>>v;

    reverse(v.begin(),v.end());
    while(v.back()==1)v.pop_back();
    el(a,v){
        if(a==1){
            cout<<-1<<nl;
            return;
        }
    }
    reverse(v.begin(),v.end());
    // dbg(v);
    n=v.size();
    vector<double> b(n);

    fr(i,n){
        b[i] =log2(log2(v[i]));
    }

    // dbg(b);

    for(int i =1;i<n;i++){
        double need = b[i-1]-b[i];
        if(need>eps){
            int tmp = 1 + (need-eps);
            b[i]+=tmp*log2(2);
            ops+=tmp;
        }
    }
    cout<<ops<<nl;
}


int32_t main()
{
 
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

submission : 272991530

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

Написать комментарий?

FuyuMai12

4 месяца назад, # |

Using direct floating point arithmetic is a gamble if you don't understand what you are doing.

→ Ответить

ManasXD

4 месяца назад, # ^ |

Then what is the solution, how to avoid such errors.

I am really curious about how the second approach avoids floating point errors.

I don't trust FP in this problem either. I'd rather do a full integer-based solution.

For this one, the eps used in AC solution helped a little bit in circumventing. TL;DR there might be cases where the "equal" comparison for FP numbers aren't accurate, somehow making two identical number having slight errors (turning $$$0$$$ into $$$10^{-15}$$$ or something that similarly low, pushing ceil to $$$1$$$). eps sets a threshold for ignored error.

Блог пользователя ManasXD