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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What's the relevance of $M,N\leq 10^5$? $\endgroup$
    – David Richerby
    Feb 8, 2014 at 15:57
  • $\begingroup$ @DavidRicherby Limits imply anything above $O(N* log N)$ worst case will not be feasible. $\endgroup$
    – Alice
    Feb 8, 2014 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, 2014 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, 2014 at 18:14

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
10
  • $\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, 2014 at 18:10
  • $\begingroup$ Yes, that's the idea. $\endgroup$
    – Yuval Filmus
    Feb 8, 2014 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, 2014 at 19:02
  • $\begingroup$ I added another hint. $\endgroup$
    – Yuval Filmus
    Feb 8, 2014 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, 2014 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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