Codeforces Round 647 Div 2 Problem C

https://codeforces.com/contest/1362/problem/C

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int

//-4%3=-1
int main() {
	// your code goes here
            ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	lld arr[61],power[61];
	arr[0]=0; power[0]=1LL;
	arr[1]=3; power[1]=2 ;
	for(int i=2;i<=61;i++)
	{
	    arr[i]=2*arr[i-1]+1LL;
	    power[i]=2*power[i-1];
	}
    arr[0]=1LL;
        power[0]=1LL;
       

    lld t;
    cin>>t;
    while(t--)
    {
        lld n;
        cin>>n;
        lld val=log2(n);
        //cout<<"VAL "<<val<<"\n";
        lld res=0;
        res+=arr[val];
        n-=power[val];
        //cout<<res<<"a\n";
        while(n!=0)
        {
            val=log2(n);
            //cout<<val<<" "<<arr[val]<<" "<<power[val]<<"c\n";
            res+=arr[val];
            n-=power[val];

        }
        cout<<res<<"\n";
    }
}

I have wasted a lot of time in this queestion (during and after the contest). This code fails on n=576460752303423487 When I find its log2 then it gives 59. But power[59] is giving value greater than 1. Can someone tell me my mistake?
Also do ide of cc and cf work differently?

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 

//-4%3=-1
int main() {
	// your code goes here
	
	lld arr[61],power[61];
	arr[0]=1, power[0]=1;
	arr[1]=3, power[1]=2 ;
	for(int i=2;i<=61;i++)
	{
	    arr[i]=2*arr[i-1]+1;
	    power[i]=2*power[i-1];
	}
	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    while(t--)
    {
        lld n;
        cin>>n;
        lld val=log2(n);
        lld res=0;
        res+=arr[val];
        n-=power[val];
        while(n!=0)
        {
            val=log2(n);
            res+=arr[val];
            n-=power[val];
        }
        cout<<res<<"\n";
    }
}

This code gives correct output for sample TC in cc ide but in cf ide it gives WA. Garbage value is stored in first index of power[] and arr[]. Can someone help me?
@ssjgz @galencolin @everule1

use log2l for long long

3 Likes

Is log2 valid for int only?

2 Likes

Ya…I also didn’t know untill I solved FIBEASY from Sept Challenge 2k19. I got to know after the contest.

1 Like

Do out of bound give wrong result even if that value is not used?
Like in second code I ran loop till 59 and changed log2 into log2l, it gives AC

Can you elaborate? I couldn’t understand you.

Here I ran till 59 only. I changed log2 into log2l. Now, it got AC. Initially it was showing Out of bound (when contest was over) and when contest was live it just gave WA on first TC. If arr[60] is out of bound then it should store some garbage value, it should not give WA?

Oh I got my mistake, I declared arr with size 61 only but why cc ide didn’t show error? :thinking:

A lesson learnt for me too… I had the same scene, a lot of time wasted and finally failing system test!
Thanks for sharing this!

1 Like

your pfp though

arr[60] is not out of bounds but arr[61] is.

Yeah, I got that. I just wanted to ask why cc ide didn’t give error when out of bound was accessed?

I don’t think it gives error when out of bounds is accessed in array. It just gives garbage value.

https://codeforces.com/contest/1362/submission/82535720 (during contest)
https://codeforces.com/contest/1362/submission/82572374 (after contest)
Both are same codes but they are giving WA. They give garbage value for sample TC but in cc ide they give correct result. Can you please tell me why?

https://codeforces.com/contest/1362/submission/82571103 (accepted code)

one liner solution :slight_smile:

print (2*n - count_1_in_binary_of(2 * n ))

Here u go -

#include<bits/stdc++.h>
using namespace std;
#define lli long long int

lli cntones(lli n){
lli cnt=0;
while(n){
    if(n%2==0)cnt++;
    n/=2;
}
return cnt;
}

int main(){
lli t;
cin>>t;
while(t--){
     lli n;
     cin>>n;
     cout<<(2*n - cntones(2*n))<<endl;   // or cout<<(2*n - cntones(n))<<endl;
 }
 return 0;
}

If this type of questions occur in which there is a series like in this 1 3 4 7 8 10 11 then go to OEIS :—> https://oeis.org/A005187

1 Like

While accessing out of bounds (arr[61]), it also fills arr[0] with garbage value both on codeforces and my system (don’t know why??) but on codechef, arr[0]=1 and no garbage value is filled. I am not the right person to answer this as I have less knowledge of technicalities of c++ . You may ask any other experienced person. I’d also like to know.
maybe @galencolin

yep

1 Like

Bro I don’t need solution. I just want to know the reason of problem

This error due to internal precision and type casting .

or i think @ssjgz will help in this case :slight_smile:

1 Like