Bitmasking Challenges Not so Easy MAth

#1

Hi,

How to solve this problem?
https://hack.codingblocks.com/contests/c/126/821

This is one of the bitmasks challenges competetive programming course

Whats wrong in this code ( Not so easy math)
#2

Hi,

This question is based on inclusion exclusion principle (Set theory)
let a,b,c,d,e,f… represent set of prime numbers less than 20.

Now you have to find
a union b union c union d…

this can be found by inclusion exclusion principle.

In case you need explanation do post it.

Hit like if you get it

1 Like
#3

Please give More hint!

#4

Hi

Check out this video, post if you still have doubts.

Hit like if you get it. :stuck_out_tongue:

1 Like
#5

Hi I wrote this code for it:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main() {
  ll n;cin >> n;
  ll res=0;
  ll it=1<<8-1;
  ll primes[8]={2,3,5,7,11,13,17,19};
  for(ll i=1;i<=it;++i){
    ll bit = i;ll c=0;
    unsigned long long thisres=0;
    for(ll j=0;bit!=0;++j){
      if(bit&1){
        ++c;
        thisres=thisres*primes[j];
      }
      bit>>=1;
    }
    if(c&1){
      res+=(n/thisres);
    }
    else{
      res-=(n/thisres);
    }
  }
  cout << res;
  return 0;
}

Why this is uncorrect and it gets tle?

#6

this is incorrect, the way you are creating subsets is wrong.
try to do a dry run on this,

for(ll j=0;bit!=0;++j) // this will go infinity.

Hit like if you get it.

1 Like
#7

Why its Wrong?
bit Every time is divided by 2 and after some number of dividing it will be 0?

#8

Ohh I didn’t saw bit>>=1 line,

question requires testcase as input but you are not it as input and initialise thisres=1. with 0 it will always be 0.

1 Like
#9

Oh! Thanks a lot.Please Answer my another question about rat in a maze.
And Why it goes to infinite loop?Because it only changes the answer but why it goes to infinite loop?

#10

yeah sure, Please tag me in that

#11

How to tag you?
And Why it goes to infinite loop?Because it only changes the answer but why it goes to infinite loop?

#12

have you posted a new doubt?
if not please post a new doubt of rat in maze will discuss it in new posts.

#13

one more thing in this question you will have to put bracket in line it=(1<<8)-1

#14

Ok This is the link Please answer the up question to.

#15

check this https://ide.codingblocks.com/s/63000

#16

Yes tusharask cleared me

1 Like