1
$\begingroup$

We have $M$ bits. $M\le10^5$ Also we have N ranges in the form $[L,R]$. $N\le10^5$ We can choose any range from the given ranges and flip all bits in our number from $L$ to $R$, both inclusive. We can apply each operation any number of times and in any order. We have to calculate the number of $M$ bit numbers that can be formed thus.

for Example if $N=3$ and our ranges are : $[0,0]$, $[1,1]$, $[2,2]$. Now if we need to find number of three bit numbers that can be formed using the above restrictions, our answer would be 8, since we can form everything from 0 to 7.

Example 2: if we have 3 bits and two ranges $[0,1]$, $[1,2]$, we can form $4$ distinct numbers : $0 (000)$, $3 (011)$, $6 (110)$ and $5 (101)$.

I was thinking of doing something like if we could just obtain the $i^{th}$ bit as $1$ after performing some operations we could simply take $2^X$ for all such bits and that many numbers can be formed. But this approach doesn't seem to work in general.

$\endgroup$
  • 1
    $\begingroup$ What's the relevance of $M,N\leq 10^5$? $\endgroup$ – David Richerby Feb 8 '14 at 15:57
  • $\begingroup$ @DavidRicherby Limits imply anything above $O(N* log N)$ worst case will not be feasible. $\endgroup$ – Alice Feb 8 '14 at 18:25
  • 1
    $\begingroup$ An algorithm that took $N^2$ steps would be only around 10s of compute time on a 1GHz CPU. $\endgroup$ – David Richerby Feb 8 '14 at 19:21
  • 2
    $\begingroup$ @DavidRicherby For what it's worth, this appears to be a currently active competition problem on codechef.com with a time limit of one second. $\endgroup$ – mhum Feb 13 '14 at 18:14
3
$\begingroup$

Hint: For given $N$ and a range $[L,H]$, let $v \in \mathbb{Z}_2^N$ be the characteristic vector of $[L,H]$, i.e. $v_i = 1$ if $L \leq i \leq H$ and $v_i = 0$ otherwise. Given a list of ranges $[L_j,H_j]$ and correspond vectors $v_j$, how can you represent the characteristic vectors of all numbers reachable by the operations you mention? What is the relevant parameter?

Another hint: What happens if all $L_i$ are distinct? How can you handle cases in which $L_i = L_j$ for some $i \neq j$? Try to reduce it to the former case.

$\endgroup$
  • $\begingroup$ I can think of forming an N*N matrix with 1's for all [L,R] range for each row. And then maybe the rank of that matrix will be our answer? Rank in finite field 2. $\endgroup$ – Alice Feb 8 '14 at 18:10
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus Feb 8 '14 at 18:59
  • $\begingroup$ yes I had that in mind before, but finding the rank of a matrix of the order N*N will be extremely unfeasible. 10^20 ops in worst case, maybe more. I was looking for an alternate approach. Or if we could exploit the structure of our matrix ? I am not aware of much in that direction. $\endgroup$ – Alice Feb 8 '14 at 19:02
  • $\begingroup$ I added another hint. $\endgroup$ – Yuval Filmus Feb 8 '14 at 19:20
  • $\begingroup$ if all $L_i$'s are distinct, our answer will simply be $2^M$, next case, when some of them overlap. there can be thing like $[0,2]$,$[3,5]$,$[0,5]$ rank remains $2$ not $3$. Also for $[0,6]$,$[0,3]$,$[3,6]$,$[3,3]$ rank remains $3$ not $4$. I am aware of such cases, simply not able to handle them :). $\endgroup$ – Alice Feb 8 '14 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.