Tags: bits, analysis, math, counting problem
This time, you will have a lot of fun. Get ready for some high level analysis! :D
So this is some mind-boggling, extremely beautiful problem from AtCoder: you are having a collection of natural numbers from $L$ to $R(<10^{18})$ inclusive, you want to count the number of unique elements you can obtain by performing OR operation to the collection of your numbers.
The approach I am mentioning below will not pass TL, but is something worth mentioning.
I have solved a similar problem on CsAcademy, with the only difference being:
1. We can use AND operation between the numbers from our collection.
2. The collection of numbers was having no pattern, unlike here where we have nos from $L$ to $R$.
Approach 1(Slow):
You might not understand this if you are unaware of SOS DP. Also this solution will cause TLE.
So you can SKIP this, otherwise you also learn one more technique.
We can form a number $X$, only if $res = OR_i(a_i)$ is same as $X$, where $a_i$ is a number from our collection which is a subset of $X$ i.e $X\&a_i=a_i$. So if we perform OR operation on all such nos and the result is still not $X$, then unfortunately $X$ cannot be formed.
This can be done in $O(A)$ or $O(Alg(A))$, where $A=max(a_1,a_2,...,a_n)$.
How?
Simple DP:
Let dp[i][j] be the OR of all such elements that are subsets of $i$ and differ from $i$ in first $j$ bits.
Then,
if $j^{th}$ bit is set in $i$, $dp[i][j]=dp[i][j-1] | dp[i$^$(1<<j)][j-1]$
otherwise $dp[i][j]=dp[i][j-1]$
This is commonly known as SOS DP. If you didn't understand the above thing, see it from the link mentioned.
Here is the code for implementation above.
So this will not pass TL. We need to make use of the fact that in our problem we just don't have any numbers. We are given nos from $L$ to $R$.
Approach 2:
The analysis is very beautiful and I really enjoyed solving this.
Let $r$ be the 1st bit from left where $A,B$ differ. So we can remove the bits before this from both $A,B$ as they won't affect our answer because no matter what nos we select in OR operation those bits will remain as it is, and thus have just 1 choice.
Now, $A<2^r\le B <2^{r+1}$
This equation is really very important as we will see later on.
Let $T=2^r$, and lets partition the nos from $A$ to $B$ into 2 sets:
$X=\{A,A+1,...,T-1\}$ and $Y=\{T,T+1,...,B\}$
1. Taking nos from only X:
We can obtain all nos from $A$ to $T-1$. That's it. We can't obtain higher nos as $T-1$ is already a bit sequence of all ones.
2. Taking nos from only Y:
This is interesting.
Note that $T\le B <2^{r+1}$, so $T,B$ have same number of bits.
The highest bit set in both $T,B$ is $r$. Infact $T$ has only one bit set.
Let the next highest bit set in $B$ be $k$.
Now refer to the pic below.
We can trivially obtain all nos from $T$ to $B$. Point is how far can we go from $B$.
Now refer to the image on left and read the following.
The nos between $2^r$ and $2^r+2^k$ will be of form $1000*****$.
The shaded portion of length $k-1$ bits will have all permutations of $0$s and $1$s(from $0$ to $2^k-1$).
So we can set any pattern of $0$s and $1$s in the first $k-1$ bits of $B$ by suitable OR operations.
This enables us to obtain any number from $B$ to $2^r+2^{k+1}-1$. Voila!
So in this case, we can obtain nos from $T$ to $2^r + 2^{k+1}-1$.
3. Taking nos from X and Y:
The min number thus obtained will be the OR of $A,T$ = $A+T=A+2^r$.
Note that $T$ just has a bit set at $r^{th}$ position, while all nos from $X$ have bits from $0$ to $r-1$.
$\therefore$, OR of $T=2^r$ with elements from $X$ will give us nos from $A+T$ to $T-1+T=2T-1$.
Well, this is the highest number that we can achieve as it is $2^{r+1}-1$ i.e all bits set to $1$. So we can't go any further.
Finally we have 3 segments, some of which may overlap. All that is left is to find the total length spanned by these segments. Phew!
Here is the SMALL code implementing the above too BIG an idea.
I loved this problem very much and had a lot of fun writing the explanation for it.
Hope you have also learnt SOS DP trick incase you didn't know about it.
Feel free to ask comment below incase of any queries.
This time, you will have a lot of fun. Get ready for some high level analysis! :D
So this is some mind-boggling, extremely beautiful problem from AtCoder: you are having a collection of natural numbers from $L$ to $R(<10^{18})$ inclusive, you want to count the number of unique elements you can obtain by performing OR operation to the collection of your numbers.
The approach I am mentioning below will not pass TL, but is something worth mentioning.
I have solved a similar problem on CsAcademy, with the only difference being:
1. We can use AND operation between the numbers from our collection.
2. The collection of numbers was having no pattern, unlike here where we have nos from $L$ to $R$.
Approach 1(Slow):
You might not understand this if you are unaware of SOS DP. Also this solution will cause TLE.
So you can SKIP this, otherwise you also learn one more technique.
We can form a number $X$, only if $res = OR_i(a_i)$ is same as $X$, where $a_i$ is a number from our collection which is a subset of $X$ i.e $X\&a_i=a_i$. So if we perform OR operation on all such nos and the result is still not $X$, then unfortunately $X$ cannot be formed.
This can be done in $O(A)$ or $O(Alg(A))$, where $A=max(a_1,a_2,...,a_n)$.
How?
Simple DP:
Let dp[i][j] be the OR of all such elements that are subsets of $i$ and differ from $i$ in first $j$ bits.
Then,
if $j^{th}$ bit is set in $i$, $dp[i][j]=dp[i][j-1] | dp[i$^$(1<<j)][j-1]$
otherwise $dp[i][j]=dp[i][j-1]$
This is commonly known as SOS DP. If you didn't understand the above thing, see it from the link mentioned.
Here is the code for implementation above.
So this will not pass TL. We need to make use of the fact that in our problem we just don't have any numbers. We are given nos from $L$ to $R$.
Approach 2:
The analysis is very beautiful and I really enjoyed solving this.
Let $r$ be the 1st bit from left where $A,B$ differ. So we can remove the bits before this from both $A,B$ as they won't affect our answer because no matter what nos we select in OR operation those bits will remain as it is, and thus have just 1 choice.
Now, $A<2^r\le B <2^{r+1}$
This equation is really very important as we will see later on.
Let $T=2^r$, and lets partition the nos from $A$ to $B$ into 2 sets:
$X=\{A,A+1,...,T-1\}$ and $Y=\{T,T+1,...,B\}$
1. Taking nos from only X:
We can obtain all nos from $A$ to $T-1$. That's it. We can't obtain higher nos as $T-1$ is already a bit sequence of all ones.
2. Taking nos from only Y:
This is interesting.
Note that $T\le B <2^{r+1}$, so $T,B$ have same number of bits.
The highest bit set in both $T,B$ is $r$. Infact $T$ has only one bit set.
Let the next highest bit set in $B$ be $k$.
Now refer to the pic below.
We can trivially obtain all nos from $T$ to $B$. Point is how far can we go from $B$.Now refer to the image on left and read the following.
The nos between $2^r$ and $2^r+2^k$ will be of form $1000*****$.
The shaded portion of length $k-1$ bits will have all permutations of $0$s and $1$s(from $0$ to $2^k-1$).
So we can set any pattern of $0$s and $1$s in the first $k-1$ bits of $B$ by suitable OR operations.
This enables us to obtain any number from $B$ to $2^r+2^{k+1}-1$. Voila!
So in this case, we can obtain nos from $T$ to $2^r + 2^{k+1}-1$.
3. Taking nos from X and Y:
The min number thus obtained will be the OR of $A,T$ = $A+T=A+2^r$.
Note that $T$ just has a bit set at $r^{th}$ position, while all nos from $X$ have bits from $0$ to $r-1$.
$\therefore$, OR of $T=2^r$ with elements from $X$ will give us nos from $A+T$ to $T-1+T=2T-1$.
Well, this is the highest number that we can achieve as it is $2^{r+1}-1$ i.e all bits set to $1$. So we can't go any further.
Finally we have 3 segments, some of which may overlap. All that is left is to find the total length spanned by these segments. Phew!
Here is the SMALL code implementing the above too BIG an idea.
I loved this problem very much and had a lot of fun writing the explanation for it.
Hope you have also learnt SOS DP trick incase you didn't know about it.
Feel free to ask comment below incase of any queries.
tnx for this good problem.
ReplyDeleteWelcome :)
Delete