AlphaNode's blog

By AlphaNode, history, 2 months ago, In English,

Hello!

I was recently solving this problem : http://poj.org/problem?id=1823

The problem basically says given an array of maximum size of 16000 where each element is one or zero, we need to perform the following two operations.

-Set range [L,R] to ones or zeros.

-Query maximum length of a subarray of ones

The problem can be indeed be solved by a segment tree, however using bitset we can do updates in O(N/32), and with N being 16000 that's just 500.

The problem is in querying the maximum length, I haven't reached any solution better than N operations, are there any ways to achieve something like N/32 ?

Please note, I already know the segment tree solution, I'm interested in bitset.

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

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

'Something like N/32' solution (O(N/20) — slower than O(N/32) but can be enough): just precalculate same values like in SegmentTree solution (if we have same solutions it is count ones on the prefix, suffix, and max count consecutive ones) for each of 2^20 mask, so further calculation is simple — just iterates over each 20 bits, and merge previous segment with len 20 with current, and pick the best.

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

    Also this is nice, it still gets TLE. :) I'm starting to think either problem just requires fast updates so something like 500 per query is not sufficient, or maybe I can't implement it efficiently.

»
2 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

You can consult this wonderful post: Link

It explains quite nicely different ways to use bitset.

»
2 months ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

I think I can help you with this question, my friend.

I see you are new in the fields of bitset optimizations — your optimization is very nice but has a lot of room for improvement. I will demonstrate to you now how you will be able to handle updates in O(N/(N-log(N))) time with some simple bitset usage.

1) Gather all ones from the initial array into a bitset.

2) Do the same with the zeros, but this time store them separately.

3) Merge the two bitsets from steps 1 and 2, creating in this way something very similar to a Fenwick tree, as you can see.

4) Divide the tree into components in which you can perform simple Fenwick tree operations, but instead of updating the actual values, you will be creating new bitsets to fill up the spaces of the logarithmic jumps.

Now you can see how you can simply answer queries in O(N/(N-log(N))) time as mentioned above.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    We can add 2D fft with points (black, white) and get O(N/(N-log(N)/log(N)/log(N))

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Thank you. Got AC.

    BTW if you use 3D logarithmic bitset in #1 you can drop complexity to O(N/(N-1.678))