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

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 9:09 pm

Try this case:
2345515 3444441325 3444441325

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

o...

Post by zzzzzddddd » Sun Sep 26, 2004 1:58 am

my program outputs 2345515!!!!
thanks u very much.

james299
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

Post by james299 » Fri Jul 29, 2005 4:55 am

hi ! :)
I got WA, and i can't figure it out.

1. I translate N,L,U to binary bit.
2. I use a temp array to store the reslut.
3. First, I copy the data from U to temp, and from leading bit to decide following two case.
if(U==0&&N==0)

I check if I changed the value and it wouldn't exceed the limit(up).

else if(U==1&&N==1)

This part is a little bit complicated for I to explain.
I try to minus 1 for this case ,so I change the value to 0 , and set all rest bits to 1. And then I check it wouldn't exceed the limit(down).
If it's smaller than the lower bound I reset the data as original one.
It starts from the largest one toward smaller one, so I don't have to handle the case

Code: Select all

U[i]==1&&N[i]==0
U[i]==0&&N[i]==1
for it has been the maxium we wanted.

if my statement can't help you to help me, just give me some critical I/O.
As Krzysztof Duleba posted my output :)

Code: Select all

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
I use unsigned int to store data input and use << to pick out every bit and store in a int array.
As the problem statement

Code: Select all

given a 32-bit unsigned integer
I don't think there is any input over 2147483648.
:-?

Thanks for your precious time. :P

james299
New poster
Posts: 10
Joined: Tue Jul 26, 2005 8:58 am
Location: Taiwan

Post by james299 » Sat Jul 30, 2005 6:14 pm

I find what's wrong in my code. And AC now :D .

My judger for upper and lower limits are both wrong when difference is one.

Input

Code: Select all

127 50 60
My output

Code: Select all

51
But should be

Code: Select all

50
:wink: Good luck!

predator
New poster
Posts: 3
Joined: Sun Jun 25, 2006 6:33 pm
Location: Bangladesh
Contact:

10718 WA

Post by predator » Mon Jul 03, 2006 8:54 pm

hi i am getting WA in this problem. now i checked my code with the sample given in the other post .. they don't match but i dont know whats wrong with my code or algo. can anyone check it plz?

Code: Select all

unsigned int L,U,N;


unsigned int get_M();

int main()
{
	while(1)
	{
		cin>>N>>L>>U;
		if(cin.eof())	break;
		cout<<get_M()<<endl;
	}


	return 0;
}

unsigned int get_M()
{
	unsigned int M,t;
	int i;

	for(M=L,i=31;i>=0;i--)
	{
		if(!(N&(1<<i))) //if the ith bit is OFF
		{
			t=M|(1<<i);	//turn ON the ith bit of M
			
			if(t<=U)
				M=t;
		}
	}

	return M;
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10718 WA

Post by Martin Macko » Sun Jul 23, 2006 10:35 pm

predator wrote:hi i am getting WA in this problem. now i checked my code with the sample given in the other post .. they don't match but i dont know whats wrong with my code or algo. can anyone check it plz?
Consider using (1u<<31) instead of (1<<31).

CSGrandeur
New poster
Posts: 5
Joined: Tue Aug 16, 2011 11:15 am

Re: 10718 - Bit Mask

Post by CSGrandeur » Wed Aug 17, 2011 7:14 pm

Try these test cases
??????
inputs

Code: Select all

2709727097 1717317173 3015630156
1142911429 2225322253 3015630156
3083430834 3060830608 3230932309
2832328323 1288712887 3230932309
1390913909 1367713677 3230932309
2150721507 53335333 3230932309
21072107 2429024290 3230932309
3274332743 2447124471 3230932309
2660126601 1153311533 3265532655
outputs

Code: Select all

2122111110
3013643834
3224802381
1462638972
2904053386
2144245788
3230930708
3168118200
1634840694

sadia_atique
New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

Re: 10718 - Bit Mask

Post by sadia_atique » Tue Jun 05, 2012 12:49 am

I'm getting WA in this problem..What I did is setting ans initially to zero..then checking every bit starting from MSB,if its zero,then set that bit in "ans",and check whether the new ans is smaller than upper limit,if yes,then set that bit,otherwise didn't set.When 1 found in any bit,made that bit 0 in ans and every smaller bit 1,then check whether this new value is greater or equals to lower limit,if yes,then set that bit to zero,otherwise one.I think there might be problem in handling long or unsigned..my algo seems ok,don't know whats wrong..someone please help,what's wrong with my code? :cry: :cry:

Code: Select all

AC
Last edited by sadia_atique on Wed Jun 06, 2012 5:24 pm, edited 1 time in total.

sadia_atique
New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

Re: 10718 - Bit Mask

Post by sadia_atique » Tue Jun 05, 2012 1:52 pm

Can anyone help??I'm getting WA in this problem...please help :cry:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10718 - Bit Mask

Post by brianfry713 » Tue Jun 05, 2012 9:27 pm

Try the I/O CSGrandeur posted.
Check input and AC output for thousands of problems on uDebug!

sadia_atique
New poster
Posts: 25
Joined: Thu Nov 24, 2011 6:32 am

Re: 10718 - Bit Mask

Post by sadia_atique » Wed Jun 06, 2012 5:25 pm

Thanks,Got AC..a stupid mistake in loop..

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 10718 - Bit Mask

Post by AKJ88 » Fri Mar 08, 2013 7:19 pm

I used this algorithm for this question:
I start with a mask equal to 0. I find the MSB in U then try to set corresponding bit in the mask 1 in the condition that 1) the result is less than U
and 2) if this bit is 0 in N or it's 1 but if we don't set this bit, with the remaining bits we can't produce a number which is greater than or equal to L.
Can anyone tell me what's is wrong with this algorithm??? because I keep getting WA!:-(
Here is my code: (I know it produces wrong result for 2 cases in the sample input provided in this forum but I can't understand why!)
Thanks.

Code: Select all

 Algorithm is correct it was because of a simple mistake in implementation that I'd got WA. 

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 10718 - Bit Mask

Post by tiendaotd » Wed Mar 20, 2013 8:48 pm

I got AC with the following "greedy" method, but I dont know why it works : assigned M = U and M = L . For each value of M , I check every bit position from 32 down to 0 if I can turn it on or turn it off. I can turn it on if the current bit in N is off , and by turned on the value of M still smaller than U . I can turn it off if the current bit in N is on , and by turned off the value of M still bigger than L . Then I simply compare the value of N^M in each case and get the result.

martijnn2008
New poster
Posts: 2
Joined: Sun Aug 31, 2014 5:46 pm

Re: 10718 - Bit Mask

Post by martijnn2008 » Sun Aug 31, 2014 5:47 pm

Code: Select all

import java.util.*;

public class BitMask {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            solve(sc.nextLong(), sc.nextLong(), sc.nextLong());
        }
        sc.close();
    }

    private static void solve(long N, long L, long U) {
        long M = 0;
        for (int i = 31; i >= 0; --i) {
            if ((N & 1L << i) == 0) {
                if (M + (1L << i) <= U) {
                    M += 1L << i;
                }
            } else {
                if (M + (1L << i) - 1 < L) {
                    M += 1L << i;
                }
            }
        }
        System.out.println(M);
    }
}
Tried a lot of input/output, but it all seems to be correct

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10718 - Bit Mask

Post by brianfry713 » Wed Sep 03, 2014 7:01 pm

Use class Main
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 107 (10700-10799)”