Blog entries - Codeforces

#	User	Rating
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

#	User	Contrib.
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

Full text and comments »

ManasXD's blog