10718 - Bit Mask

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

10718 - Bit Mask

Post by liulike » Wed Sep 22, 2004 10:14 am

How to solve it?
Plz give me some hints,thanks!

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » 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

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike » Wed Sep 22, 2004 10:55 am

Is it a brute force solution ?
The time complexity is O(2 ^ 32)?

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » 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.

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike » Wed Sep 22, 2004 11:37 am

Thank you, I got AC now :D

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Wed Sep 22, 2004 6:54 pm

liulike wrote:Thank you, I got AC now :D
Hello, I got WA all the time.
Could you give me tricky input/output? Thx :D

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » 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??
"Everything should be made simple, but not always simpler"

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » 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.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » 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?
"Everything should be made simple, but not always simpler"

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » 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. :wink:

zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

10718

Post by zzzzzddddd » 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]

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike » Fri Sep 24, 2004 6:08 pm

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

zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

to liulike

Post by zzzzzddddd » 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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Sep 25, 2004 11:51 am

Some random input:
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
Output:
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

zzzzzddddd
New poster
Posts: 6
Joined: Tue Sep 21, 2004 5:53 pm

Here are my output.

Post by zzzzzddddd » 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

Post Reply

Return to “Volume 107 (10700-10799)”