Hammington's Mayhem - Editorial

Problem Link

C_CODENITE24

Author: aryansanghi

Solution

Observation

  1. The maximum number of set bits is 2000. So, we can precompute F(N) for all N in [1,2000] recursively by using F(1) = 0 and F(N)=F(H(N))+1.

Algorithm

  1. Precompute values of F for integers from 1 to 2000.
  2. Start moving from MSB to LSB. If the current bit is set bit and is the k^{th} MSB, let the number of bits after the current bit be x and let the number of set bits till now(excluding current set bit) be y. For all values of i from 0 to x(inclusive), add (F(i+y)+1)\times(^xC_i) to the answer.

Code

//Written By Aryan Sanghi

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<queue>
#include<utility>
#include<set>
#include<unordered_map>

using namespace std;

#define ll long long int
#define rep(i, n) for(ll i = 0; i < n;i++)
#define repi(i, a, n) for(ll i = a;i < n;i++)
#define repii(i, a, n, b) for(ll i = a;i < n;i += b)
#define mod 1000000007
#define pb push_back

vector<vector<ll> > v;
vector<ll> cp;

ll gcd(ll a, ll b)
{
    if(b == 0)
    return a;
    
    if(a == 0)
    return b;
    
    if(a > b)
    return gcd(b, a % b);
    
    return gcd(a, b % a);
}

ll maxi(ll a, ll b)
{
    if(a > b)
    return a;
    
    else
    return b;
}

ll mini(ll a, ll b)
{
    if(a > b)
    return b;
    
    else
    return a;
}

int modpower(ll a, ll b, ll c)
{
    ll r=1;
    
    a=a%c;
    
    while(b>0)
    {
        if(b%2==1)
        r=(r*a)%c;
        
        b=b/2;
        a=(a*a)%c;
        
    }
    
    return r;
}

int main()
{
    ll t;
    cin>>t;

    ll f[2001];
    f[0]=0;
    f[1]=0;

    repi(i, 2, 2001) {
        ll count = 0, temp=i;
        while(temp>0){
            count+=temp%2;
            temp/=2;
        }
        f[i]=f[count]+1;
    }

    ll fact[2001];
    fact[0] = 1;

    repi(i, 1, 2001) fact[i] = (fact[i-1]*i)%mod;


    while(t--)
    {
        string s;
        cin>>s;

        ll n = s.size();
        vector<ll> a(n+1, 0);
        
        ll count = 0;

        rep(i, n){
            if(s[i]=='1'){
                repi(j, count, count+(n-i)){
                    ll x=n-i-1, y=j-count;
                    ll k=fact[x];
                    k*=modpower(fact[y], mod-2, mod);
                    k%=mod;
                    k*=modpower(fact[x-y], mod-2, mod);
                    k%=mod;
                    a[j]+=k;
                    a[j]%=mod;
                }
                count++;
            }
        }

        a[count]+=1;
        a[count]%=mod;

        ll ans=0;

        a[1]--;

        repi(i, 1, n+1) {
            // cout<<a[i]<<" "<<f[i]<<"\n";
            ll k=a[i]*(f[i]+1);
            k%=mod;
            ans+=k;
            ans%=mod;
        }
        // cout<<"\n";

        cout<<ans<<"\n";
    }
}
2 Likes

Incorrect Conditionals

Incorrect conditionals are one of the most common types of logical errors. They occur when you put an incorrect condition in if-else.

Example

The code below is supposed to do the following

  • If an integer is even, then output even
  • If an integer is odd, then output odd
int n = 10;
if (n % 2 == 0) {
    printf("odd");
} else {
    printf("even");
}

The above code is incorrect because it outputs odd when the number is even. Changing the if condition will fix the error.

Task

Given a program to check whether a number is greater than 5 or not.

  • Run the code without changing anything, it will give wrong answer.
  • Find the wrong condition and correct it.

Sample 1:

Input

Output

5

the number is smaller than or equal to 5

Sample 2:

Input

Output

6

the number is greater than 5

Did you like the problem?

36 users found this helpful