UVa 10718

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1659

Summary[edit]

In bit-wise expression, mask is a common term. You can get a certain bit-pattern using mask. For example, if you want to make first 4 bits of a 32-bit number zero, you can use 0xFFFFFFF0 as mask and perform a bit-wise AND operation. Here you have to find such a bit-mask. Consider you are given a 32-bit unsigned integer N. You have to find a mask M such that L ≤ M ≤ U and N OR M is maximum. For example, if N is 100 and L = 50, U = 60 then M will be 59 and N OR M will be 127 which is maximum. If several value of M satisfies the same criteria then you have to print the minimum value of M.


Explanation[edit]

This problem can be solved using a greedy algorithm


Implementations[edit]

What you want to do is have a loop running backwards from 31 to 0; then you start to construct the answer. First you would check if not adding a one to bit i would cause the answer to be lower than the minimum, you do this by checking if (ans + 1<<i - 1 < lower) this is becasue 1<<i-1 is putting all ones after the one that you wouldn't add meaning that if it is less than the lower limit then you wont be able to find an answer. Next you check the given number to see if it has a 0 at i meaning you would want to put a 1 there in your answer. you can do this using (num & (1<<i)) if it has a zero you check to see if adding a 1 to your answer at i would make it be greater than the upper limit. This is simply done by (ans+(1<<i) > upper). if it does not then you add the one. you just repeat this until you reach 0. What allows you to do this solution is that fact that 1<<i is greater than if you where to put ones all the way up to but not including i. Because of this choosing to put a one at a higher i and thus perhaps taking away the ability to put a 1 later on will always lead to a more optimal solution.