11645 - Bits

[andysoft]

Hi folks.
During the latest contest I tried to solve this problem, and even came up with an idea.

But unfortunately after implementation, I have realized that fuctions with long numbers are required to solve this problem, as the answer will be too large even for unsigned long long. But when I implemented long number routines, it started working too slow even on small numbers as input data.
I followed this logic:
<spoiler>

Consider 1101000 (binary) as an input. To sum up all the “adjacent bits” from 1 to 1101000 we may do the following.
We may take each “1” digit in the binary representation of the given number, then replace it with a zero, and the rest of digits right to it may be arbitrary. For example: we take our number 1101000, replace the rightmost “1” with a zero and get 1100xxx, where xxx can be arbitrary binary digits. Then we need to compute the sum of all “adjacent bits” for this xxx. Let's do it via function F(xxx), or better F(3), where 3 is the length of the xxxx…xx stuff where digits may be arbitrary. The F(argument) function is calculated pretty simple (But even its result for F(61) is larger than max unsigned int64!) in a recursive/DP way.
After that, we compute the whole thing for 10xxxxx and, finally, for 0xxxxxx. By “whole thing” I mean summing F(argument) values with some extra hints which are simple.

</spoiler>

But after I have implemented it, I realized that long maths is needed, because answers are too large. But when I implemented long numbers routines, it started working too sloooow. And I stucked. Really stucked.

So, any hint (maybe not the entire solution, just a hint)? I surmise that I am making stuff too complex and it's actually much easier than I think. Is it so?

Thank you guys

[andysoft]

Oh, and by the way, is this i/o correct:

Code: Select all

9223372036854775806
Case 1: 142962266571249024962

?

[mmonish]

>>andysoft

My Accepted code gives the same output.

regards,
Monish

[andysoft]

oh thanx.
Now I got accepted
I followed my logic with no changes, but I implemented long numbers in a different way.

<spoiler>

the long number is represented as an array of 3 longs, which is sufficient for this problem

</spoiler>

[noor_aub]

Any body help me to solve this problem.
I am able to handle big number. How I can use DP Here.

[noor_aub]

Bro What is this.

[Jehad Uddin]

dp dimension is [length][stateOfNo][lastBit][AnyAdjacentOne] ,it will return how many nos having 11 pattern,
stateOfNo is whether it is <=N
AnyAdjacentOne is whether 11 occurs or not
Using this you can calculate number of 11s using another 4d BigIntArray

[plamplam]

There is a much simpler recurrence using the powers of 2.

[ioi]

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef unsigned long long i64;
typedef long long LLD;

i64 dp[66][2][2];
i64 dp2[66][2];
char bit[66];
int len;

i64 solve2(int pos,int has_small)
{
    int up,i;
    i64 res;
    if(pos==len) return 1;
    if(dp2[pos][has_small]!=0)
        return dp2[pos][has_small];
    if(has_small)
        up=1;
    else
        up=bit[pos]-'0';
    res=0;
    for(i=0;i<=up;i++)
    {
        res+=solve2(pos+1,(has_small||i<bit[pos]-'0'));
        dp2[pos][has_small]=res;
    }
    return dp2[pos][has_small];
}

i64 solve(int pos,int has_small,int adj)
{
    int up,i;
    i64 res;
    if(pos==len) return 0;
    if(dp[pos][has_small][adj]!=0)
        return dp[pos][has_small][adj];
    if(has_small)
        up=1;
    else
        up=bit[pos]-'0';
    res=0;
    for(i=0;i<=up;i++)
    {
        res+=solve(pos+1,(has_small||i<bit[pos]-'0'),i)+(adj & i)*solve2(pos+1,(has_small||i<bit[pos]-'0'));
        dp[pos][has_small][adj]=res;
    }
    return dp[pos][has_small][adj];
}

i64 call(i64 n)
{
    if(n<=0) return 0;
    int i,j,k;
    i64 ret;
    i=0;
    int a[100];
    memset(bit,0,sizeof(bit));
    while(n)
    {
        a[i++]=n%2;
        n/=2;
    }
    j=0;
    i--;
    while(i>-1)
    {
        if(a[i]==0)
            bit[j++]=48;
        else
            bit[j++]=49;
        i--;
    }
    len=j;
    memset(dp,0,sizeof(dp));
    memset(dp2,0,sizeof(dp2));
    ret=solve(0,0,0);
    return ret;
}


int main()
{
  //  freopen("C:\\Users\\ioi\\Desktop\\input.txt","r",stdin);
   // freopen("C:\\Users\\ioi\\Desktop\\output.txt","w",stdout);
    LLD a,b;
    i64 res;
    int kas=1;
    while(scanf("%lld",&a)==1)
    {
       if(a<0) break;
       res=call(a);
       printf("Case %d: %llu\n",kas++,res);
    }
    return 0;
}

whats wrong with this pls help
thanks in advance...

[brianfry713]

Input:

Code: Select all

9223372036854775806
-1

AC output:

Code: Select all

Case 1: 142962266571249024962