minimario's blog

Baltic BOI 2006 Bitwise
By minimario, history, 7 years ago, In English

Hi, I've been struggling with this problem recently: BOI06_BITWISE

If you're lazy, I'll summarise: We have an expression in the form (v1|v2|v3)&(v4|v5)&(v6), which is AND of OR operators. Each variable appears once, and there are at most 100 variables. We have a range for each variable (range is contained in [0, 2e9]). Calculate the maximum value of the expression.

I've only got obvious ideas: check if 1st bit can be 1, then if so, check if 2nd bit can be 1, etc. But it's nothing substantial.

So if anyone has some ideas, that would be great :^)

Thanks!

-minimario

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check if 1st bit can be 1, then if so, check if 2nd bit can be 1, etc. Now we want to get 1 in each part, so let's consider each (v1|v2|...|vn) separately.

If there is at least one vi that can be anything, it can always be 1.

Otherwise each vi now has 3 status : (1) can only be 0. (2) can only be 1. (3) can be both 0 and 1. There are 3 different cases :

A. If all variables are in status (1) or (2), then just do it, the decision is unique.

B. If there is only one variables in status (3), first let's check whether it can be 0(according to the existence of (2)), if it can be 0, it can always be 0111111111..., so we make it 0 and regard it as 1 in the future. But if it can't be 0(there is no (2)), we must keep it 1.

C. There are at least two variables in status (3), we can always make the first one 10000000... and the second one 011111111..., so we will always get 1 in the future.

Thus the whole algorithm runs in .

→ Reply