Tuesday, July 22, 2014

a bit of bitmask : UVa 10718 - Bit Mask

So today I learn a new bitwise manipulation technique :D

Problem Statement:
UVa 10718 - Bit Mask

Summary
For \(N, M, U, L\) such that \(L \leq M \leq U\), find minimum \(M\) such that \(M\) OR \(N\) is maximum (where OR refers to bitwise OR operation).

This problem requires a strategy to switch on bits on M (starting from all 0 bit) such that we only switch on a bit on M when we absolutely need to, but we must also ensure that M can fall between L and U.

Strategy:
For i-th bit of N starting from the leftmost bit:
1. If the i-th bit of N is ON, the best case scenario is we do not need to turn on the i-th bit of M. That is, if by letting the i-th bit of M off, we can still have M in between L and U, we will do so. Otherwise, the i-th bit of M must be on.
2. Else, if the i-th bit of N is OFF, the best case to maximize M OR N is by switching the i-th bit of M to ON. However, if the resulting M is higher than U, we must switch the i-th bit of M to OFF instead.

As such, the resulting M will be in between L and U.

For example, when N = 101101, L = 011010, U = 011110

i = 5:
leftmost bit of N is ON, hence M should be off, and indeed the resulting M can still fall between L and U.
i = 4:
bit of N is OFF, hence we would like to turn it on. The resulting M = 01**** can still be less than U, i.e the lowest M = 010000 is indeed less than U, so we can do so.
i = 3:
bit of N is ON, hence we want that bit on M to be OFF. but M = 010*** will always be less than L, i.e the highest possible M = 010111 is not lower than L, hence we must have that bit to be switched ON, i.e M = 011***
i = 2:
bit of N is ON, and we want M to be OFF. M = 0110** can still be in between L and U, i.e. the highest possible M = 011011 is not lower than L.
i = 1:
bit of N is OFF. If we switch that bit of M on, M = 01101* can still be less than U.
i = 0:
the rightmost bit is ON, so we want that bit on M OFF, and we have our minimum M such that M OR N is maximum.

Here is the code:



#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;

int main(){
 ll N,U,L,ans;
 while(scanf("%lld %lld %lld",&N,&L,&U)!=EOF){
  ans = 0;
  for(int i=0;i<=32;++i){
   ll state = (N & (1L<<(32-i)));
   //printf("%lld\n", state);
   //printf("%lld\n", ans);
   if(state){
    //if the bit is set
    //if not setting this bit can still fulfill the constraint
    ll temp = state -1;
    temp |= ans;
    if(temp < L){
     ans |= state;
    }
   } else {
    //if not set, should set if fulfill constraint
    ll temp = ans;
    temp |= (1L<<(32-i));
    if(temp <= U){
     ans = temp;
    }
   }
  }
  printf("%lld\n",ans);
 }
 return 0;
}

No comments:

Post a Comment