BURGER - Editorial

Same. Huge numbers.

1 9520884497965793
31 9769873759224593
1 9365680313404807

That’s because __builtin_popcount accepts a parameter as unsigned int x, for large numbers this will overflow and give wrong results. For large numbers there are 2 more inbuilt functions namely __builtin_popcountl (accepts unsigned long) and __builtin_popcountll (accepts unsigned long long), use the long long variant here and you will get AC.

2 Likes

I changed the built in power function to pre computed values of 2, these testcases passed, but still it is giving WA.
https://www.codechef.com/viewsolution/46840413

I referred to my solution while mentioning time complexity.

In my solution, I’m not using bitcount. Just iterating over log(Y/X) streak lengths in descending order.

Right I did mention setter’s solution though. Was it intended to allow those solutions to pass?

This is really annoying. I guess I changed the variables x, y, size around 100 times and still couldn’t find the test case where your code fails.

Test Case Generator
"""
Author: Chitturi Sai Suman
Created: 2021-05-23 21:24:10
Contest: May Cook-Off 2021 Division 2
"""
from random import randint

def generate_input_as_string():
    size = 10**5
    x = randint(1, 1)
    y = randint(1, size)
    return str(x) + ' ' + str(y)

def main():
    test = 10**5
    with open("in.in","w") as file:
        file.write(str(test)+'\n')
        for t in range(test):
            file.write(generate_input_as_string() + '\n')

main()

You can refer to AC submissions, pick a code and run both (yours and the picked one) against the same input generated using the above script. Some useful commands:

python3 script.py
# Will generate random input depending on the variable 'size'

g++ -o my_sol my_sol.cpp -O2
# Compile your solution

./my_sol < in.in > out1.out
# Output of your code will be stored in out1.out

g++ -o picked_sol picked_sol.cpp -O2
# Compile Picked Solution

./picked_sol < in.in > out2.out
# Run against same input and capture the output into out2.out

cmp out1.out out2.out
# Compares the outputs of both solutions
# If they match, nothing will be printed
# If they don't, line number and some other details will be printed

# Note: These commands work only for Linux environment

I have AC solution, I am running it for both AC and WA, checking for every possible values in range 1 to 1E18, but it is running since last 1 hour and has not found any wrong answer.

Same here. I am not able to find the test case where your code fails.

My WA

can someones please figure out the mistake in my code, the logic used is almost the same as in editorial (greedy) still WA,i couldt find a bug

I have been generating 2000 random numbers (1-1e18) and comparing outputs in my code and tester’s code …they are showing up same

This is totally messy but I want to know where my code fails

why are we taking i<=60 can anyone explain?

What is wrong in this code???

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

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t–){
ll x,y;
cin>>x>>y;
if(y%x!=0) {
cout<<"-1\n";
continue;
}
y=y/x;
vector p;
ll m=1;
ll sum=0;
for(int i=0;i<100;i++){
sum+=m;
if(sum>y) break;
p.push_back(sum);
m*=2;
}
ll ans=-1;
for(int i=p.size()-1;i>=0;i–){
// cout<<y<<" “<<p[i]<<”\n";
if(y==0) break;
ans++;
if(y>=p[i]) {
y-=p[i];
ans+=i+1;
}
}
if(y==0){
cout<<ans<<"\n";
}
else{
cout<<"-1\n";
}
}
return 0;
}

Can someone give me the test cases for which my solution isn’t working.

https://www.codechef.com/viewsolution/46880284

Thanks in advance!

Input

1
5 100

Expected Output

-1

Your Output

11

For the input

1
2 38

Expected Output

9

Your Output

10

Explanation

38 can be written as:

2 + 4 + 8 + 16 // Streak length = 4
2 + 4          // Streak length = 2
2              // Streal length = 1

Minimum time required = 4 + (1) + 2 + (1) + 1 = 9
n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    m=a
    t=0
    l=[]
    if b%a!=0:
        print(-1)
        continue
    while b>0:
        if a>b:
            break
        if m<=b:
            l.append(m)
            t+=1
            b-=m
            m*=2
        else:
            m=a
            t+=1
    if b==0:
        if len(l)>=2:
            if l[-1]!=l[-2]:
                print(t)
            else:
                print(-1)
        else:
            print(t)
    else:
        print(-1)
        
       
    

it is giving wrong answer …what is the mistake / or any test cases ?

I tried the test cases here it is giving CA for all but still on submission it is giving WA. Anything iam missing?

Any help on my code please

Input:

1
1 44

Expected Output:

-1

Your Output

15

thanks @suman_18733097 for the input :smiley:

Could someone please tell me why this code is giving runtime error?

https://www.codechef.com/viewsolution/46918640