sinmish's blog

By sinmish, history, 2 months ago, In English

We are given an array of size N, we can delete a subset b1b2b3...bk from the array if 2^b1 + 2^b2 + …..2^bk = 2^x for non-negative integer x where ^ is the power operator. Find the minimum number of steps required to delete the complete array.

0 <= ai <= 1000000

1 <= N <= 1000000

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sinmish (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

So first observation is that answer is the number of set bits in $$$\sum2^{v[i]}$$$ for $$$i$$$ varies from $$$1$$$ to $$$n$$$. But since the values are large we cannot find it just by summation. We have to simulate the entire process of binary addition. For that sort the array and traverse from left. Initialize an empty array $$$val[1000001]$$$ with 0. Suppose we are at $$$v[i]$$$, add $$$1$$$ to $$$val[v[i]]$$$.

Two cases may arise $$$val[v[i]]$$$ consists of 0, then change that to 1. Else if $$$val[v[i]]$$$ consists of 1, we have to make everything 0 till the next location of 0. And add 1 to the next location of 0. (That's how binary addition works). This assignment to 0 can be done using lazy segtree.

But we need to also maintain next location of 0 for each 1 in an array say $$$nxt[1000001]$$$. Two cases arise. If $$$val[v[i]]$$$ is 0, then if $$$val[v[i]+1]$$$ is 0 then $$$nxt[v[i]]=v[i]+1$$$, or else $$$nxt[v[i]]=nxt[v[i]+1]$$$. If it is 1, then update $$$nxt[v[i]]$$$ in the same way as mentioned before. At the end, the number of 1 in the array $$$val$$$ is the answer.

Code

The nested loop in the code should be done using lazy segtree.