CIELRCPT - Editorial

editorial
, , ,
21

if someone interested in dynamic programming solution

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>



using namespace std;
  #define MAX 1000007
   vector<int>v(12);
   vector<int>dp(100002,-1);


 int recu(int p)
    {
      if(p==0)
       return 0;
       if(p<0)
       return MAX;
    
      if(dp[p]!=-1)
       return dp[p];
       int q=MAX;
       for(int i=0;i<12;i++)
       {
        q=min(q,recu(p-v[i])+1);
       }
      return dp[p]=q;
    }


  int main()
        {
        int t,p;
        cin>>t;
        
        dp[0]=0;
        dp[1]=1;
        for(int i=0;i<12;i++)
        {
          v[i]=(1<<i);
        }
        
        while(t--)
        { 
            int ans=0;
           cin>>p;
     
           ans=recu(p);
          cout<<ans<<"\n";
    
       }
    return 0;
    }
22

link text

23

I am not familiar with Python but it seems that you are using file for input. You should read from the standard input and output to the standard output.

1 Like
24

I actually am using standard input. It reads from an input file on my computer (for testing), but if that file doesnā€™t exist (when I submit) it uses raw_input() instead. Iā€™ve tested this method on the codechef judge and it works for other problems, so I donā€™t understand why it gets runtime error now.

1 Like
25

The reason is:
Traceback (most recent call last):
File ā€œprog.pyā€, line 17, in
NameError: name ā€˜binā€™ is not defined

2 Likes
26

That doesnā€™t make senseā€¦ bin is a built-in function, how could it not be defined? I thought it must be something with the input because this solution CodeChef: Practical coding for everyone got accepted.

1 Like
27

You will be angry, but your code works - CodeChef: Practical coding for everyone , is there problem with whitespace, PY is ā€œwhitespace sensitiveā€, isnā€™t it?

2 Likes
28

That link doesnā€™t work, but I see that you got my solution accepted. So I tried it myself and got runtime error CodeChef: Practical coding for everyone. (this is the exact same code that you got accepted, right?) And yeah, python is whitespace-sensitive, but I donā€™t see how that could be the problem because the solution I posted above got accepted. Something really weird is going onā€¦

1 Like
29

problem was with comma in link, try again, is your editor replacing multiple spaces with one tab (but it is just a tip)?

1 Like
30

@anton_lunyov, can you make diff of these two solutions on filesystem?

1 Like
31

wow this is total B.S. How does the exact same code get accepted for betlista but runtime error for me???

1 Like
32

No. Your solution will not work for, suppose, 4096. You have to first divide p with 2048 and then count number of one in the remainder.

2 Likes
33 
for _ in range(int(input())):
p = int(input())
c = 0
if p<=2048:
    print(bin(p).replace("0b","").count('1'))
    continue
else:
    c = p//2048
    p = p - 2048*(c)
    print(c + bin(p).replace("0b","").count('1'))

Check out this

1 Like
34

When I run my code sometimes its showing correct results, sometimes wrong results.
#include
#include<bits/stdc++.h>
using namespace std;

long long d;
long long n;

int findOpt(int d,int size,int a[])
{
int count=0;
for(int j=size;j>=1;jā€“)
{
while(a[j]<=d){
d=d-a[j];
count++;
}
}
return count;
}

int main() {
cin>>n;
int a[12];
for(int i=1;i<=12;i++){
double result = pow(2, i-1);
a[i] = (int)round(result);
}
int size=sizeof(a)/sizeof(a[1]);
sort(a, a+size+1);
while(nā€“)
{
d=0;
cin>>d;
int c=findOpt(d,size,a);
cout<<c;
cout<<ā€™\nā€™;
}
}

1 Like
35 
#include <iostream>

using namespace std;

int main(){
int t;
cin >> t;
while(tā€“){
long long n,flag = 0;
cin >> n;

    long long cnt = 0;
    while(n > 2048){
        n = n - 2048;
        cnt++;
    }

    while(n != 0){       
        if(n & 1){
            flag++;
        }
        n >>= 1;
        // cout << n << " ";
    }
    flag = flag + cnt;
    cout << flag << endl;
}

}

1 Like
36

we can solve this using recursion

37

this will only true upto 2048 in this problem.

1 Like
38

https://www.codechef.com/viewsolution/36129602
An easy way to solve this que using lower bound of C++ stl :slight_smile:

41

#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long int t;
cin>>t;
while(tā€“)
{
long long int a;
cin>>a;
auto k=__builtin_popcount(2048);
if(a > 2048)
{
auto x=a/2048;
auto y=a%2048;
if(y==0)
{
cout<<xk(X multiplied by k)<<endl;
}
else
{
auto sum=xk;
sum+=__builtin_popcount(y);
cout<<sum<<endl;
}
}
else
{
cout<<__builtin_popcount(a)<<endl;
}

}

}

42

#include <bits/stdc++.h>

#define ll long long

#define endl ā€œ\nā€

using namespace std;

int main()

{

ios::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

int t;

cin >> t;

while (t--)

{

    int n;

    cin >> n;

    int count = 0;

    for (int i = 11; i >= 0; i--)

    {

        int d = pow(2, i);

        int num = n % d;

        if (num == 0)

        {

            count += (n / d);

            break;

        }

        else

        {

            if (n != num)

                count++;

            n %= d;

        }

    }

    cout << count << endl;

}

return 0;

}

what is wrong in this approach
:frowning: