### 10718 - Bit Mask

Posted:

**Wed Sep 22, 2004 10:14 am**How to solve it?

Plz give me some hints,thanks!

Plz give me some hints,thanks!

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=29&t=11106

Page **1** of **2**

Posted: **Wed Sep 22, 2004 10:14 am**

How to solve it?

Plz give me some hints,thanks!

Plz give me some hints,thanks!

Posted: **Wed Sep 22, 2004 10:35 am**

I solved it in the contest using the following idea:

1. i decide upon the bits of M from the left most one by one.

2. when deciding upon i ensure that value of M is inbetween low and high.

3. and finally with this constraint, i will turn on a bit in M if the same bit is off in N. (this is to minimise M but to maximise N).

bye

abi

1. i decide upon the bits of M from the left most one by one.

2. when deciding upon i ensure that value of M is inbetween low and high.

3. and finally with this constraint, i will turn on a bit in M if the same bit is off in N. (this is to minimise M but to maximise N).

bye

abi

Posted: **Wed Sep 22, 2004 10:55 am**

Is it a brute force solution ?

The time complexity is O(2 ^ 32)?

The time complexity is O(2 ^ 32)?

Posted: **Wed Sep 22, 2004 11:02 am**

no it is not a brute force solution at all

the complexity is O(n) where n is number of bits of the given numbers (32 steps in this case)

we need to build this number bit by bit starting from the Most significant bit.

the complexity is O(n) where n is number of bits of the given numbers (32 steps in this case)

we need to build this number bit by bit starting from the Most significant bit.

Posted: **Wed Sep 22, 2004 11:37 am**

Thank you, I got AC now

Posted: **Wed Sep 22, 2004 6:54 pm**

Hello, I got WA all the time.liulike wrote:Thank you, I got AC now

Could you give me tricky input/output? Thx

Posted: **Wed Sep 22, 2004 11:27 pm**

abishek, I used as follows: (but got WA)

1. convert N to binary

2. for up to low of binary N

{

tmp=prev. val+2^i;

iif(tmp<l) {val=tmp;continue;}

if(tmp>u) continue;

if(a*==0) val=tmp;*

}

3. before step 2 I used the folowing special cases:

let n = no. of bit in N and m=no. of bit in M

if(n==m) and all 1 bits in both then output lowerlimit

if m>n then output the value of (bits from n+1 pos to m of M concatenated by n zeroes.

What am I doing wrong??

1. convert N to binary

2. for up to low of binary N

{

tmp=prev. val+2^i;

iif(tmp<l) {val=tmp;continue;}

if(tmp>u) continue;

if(a

}

3. before step 2 I used the folowing special cases:

let n = no. of bit in N and m=no. of bit in M

if(n==m) and all 1 bits in both then output lowerlimit

if m>n then output the value of (bits from n+1 pos to m of M concatenated by n zeroes.

What am I doing wrong??

Posted: **Thu Sep 23, 2004 1:04 am**

I don't understand all what you are doing. For example, what does:

"if m>n then output the value of (bits from n+1 pos to m of M concatenated by n zeroes. " mean?

It doesn't look correct to me, especially that you concatenate these n zeros. what if N is 101 binary? you could need the bit of 2^1.

And I think this step is wrong:

iif(tmp<l) {val=tmp;continue;}

think of N = 6, l = 0, u = 7

I think you would answer 5, but it should be 1.

"if m>n then output the value of (bits from n+1 pos to m of M concatenated by n zeroes. " mean?

It doesn't look correct to me, especially that you concatenate these n zeros. what if N is 101 binary? you could need the bit of 2^1.

And I think this step is wrong:

iif(tmp<l) {val=tmp;continue;}

think of N = 6, l = 0, u = 7

I think you would answer 5, but it should be 1.

Posted: **Thu Sep 23, 2004 9:14 pm**

So, what may be the algorithm that abishek described. I think I didn't understand it properly. Can you help how to proceed?

Posted: **Fri Sep 24, 2004 3:56 pm**

Let us clarify with an example.

100 50 60

100 in binary mode is: 0001100100 ( Considering 10 bits, although in general it should be 32 bits.)

Now, start from the leftmost bit to decide, whether this bit should be set or not. The decision is based on the current status of the bit in (0001100100). Here the first three bit is 0, so if they are set, then the smallest value obtained would be more than the upper limit. So they can not be set.

Now, come to the fourth, it is already set, and if we don't set it we could still obtain a number larger than or equal to lower limit.

Now, the fifth bit is already set, but if we don't set it we could never obtain a numer more than or eqaul to 50. So it has to be set.

If this process is continued, we would get a binary pattern as follows:

0 0 0 0 1 1 1 0 1 1

Which is that for 59, hence 59 is the answer.

Good Luck.

100 50 60

100 in binary mode is: 0001100100 ( Considering 10 bits, although in general it should be 32 bits.)

Now, start from the leftmost bit to decide, whether this bit should be set or not. The decision is based on the current status of the bit in (0001100100). Here the first three bit is 0, so if they are set, then the smallest value obtained would be more than the upper limit. So they can not be set.

Now, come to the fourth, it is already set, and if we don't set it we could still obtain a number larger than or equal to lower limit.

Now, the fifth bit is already set, but if we don't set it we could never obtain a numer more than or eqaul to 50. So it has to be set.

If this process is continued, we would get a binary pattern as follows:

0 0 0 0 1 1 1 0 1 1

Which is that for 59, hence 59 is the answer.

Good Luck.

Posted: **Fri Sep 24, 2004 4:00 pm**

I used brute froce to check my program, my code can pass all test data I made. Can anyone told me why I got WA?

Thanks a lot!

[cpp]#include <stdio.h>

#include <iostream.h>

unsigned int n,lo,hi;

int main()

{

unsigned int alr;

int i;

while(cin>>n>>lo>>hi)

{

alr=0;

for(i=31;i>=0;i--)

if((n&(1<<i))==(1<<i))

{

if(!(alr+(1<<i)-1>=lo&&alr<=hi))

alr+=(1<<i);

}

else

if(alr+(1<<(i+1))-1>=lo&&alr+(1<<i)<=hi)

alr+=(1<<i);

cout<<alr<<endl;

}

return(0);

}

[/cpp]

Thanks a lot!

[cpp]#include <stdio.h>

#include <iostream.h>

unsigned int n,lo,hi;

int main()

{

unsigned int alr;

int i;

while(cin>>n>>lo>>hi)

{

alr=0;

for(i=31;i>=0;i--)

if((n&(1<<i))==(1<<i))

{

if(!(alr+(1<<i)-1>=lo&&alr<=hi))

alr+=(1<<i);

}

else

if(alr+(1<<(i+1))-1>=lo&&alr+(1<<i)<=hi)

alr+=(1<<i);

cout<<alr<<endl;

}

return(0);

}

[/cpp]

Posted: **Fri Sep 24, 2004 6:08 pm**

If anyone want, I would sent him my ac code, Good Luck!

Posted: **Sat Sep 25, 2004 5:58 am**

can u tell me why i got wa?

thanks a lot.

see my program in message i have post.

thanks a lot.

see my program in message i have post.

Posted: **Sat Sep 25, 2004 11:51 am**

Some random input:

Output:22 1 21

17 3 5

12 9 17

622 435 516

774 887 905

398 119 981

550 99 427

823 684 966

22398 14719 27341

29787 21141 30633

3113 24242 29497

5021 11052 19571

7359 6669 19790

993331 367623 921769

810986 227838 492138

987964 208251 1034287

1002648 217556 236589

680047 402532 767548

27719912 10747535 22001285

16862072 13339946 28844391

20421198 11724734 31928748

1541522 10226990 20764468

22651935 2478699 31095674

1995360670 908222743 1868651617

305542918 594331857 1426036714

1265639777 1580376576 1885248297

1442823820 658800174 1919310996

604563406 1050668699 2128532112

9

4

17

435

905

625

409

712

14721

23460

29462

19554

17216

382924

237589

257219

234343

499600

14223127

16692359

13133233

19429997

10902496

957429345

1305069817

1880088222

704659827

1542920241

Posted: **Sat Sep 25, 2004 12:46 pm**

9

4

17

435

905

625

409

712

14721

23460

29462

19554

17216

382924

237589

257219

234343

499600

14223127

16692359

13133233

19429997

10902496

957429345

1305069817

1880088222

704659827

1542920241