### Med0b1011's blog

By Med0b1011, history, 11 months ago, ,

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.

•
• +18
•

 » 11 months ago, # |   +11 '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.
•  » » 11 months ago, # ^ |   0 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.
 » 11 months ago, # | ← Rev. 2 →   +19 You can consult this wonderful post: LinkIt explains quite nicely different ways to use bitset.
•  » » 11 months ago, # ^ |   0 Thank you, I found it quite useful.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +3 On a serious note, are the optimizations mentioned in the link legit?
•  » » » 11 months ago, # ^ |   0 Yes?!
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 Is that floyd's optimization really possible ? The O(n^2) one.
•  » » » » » 11 months ago, # ^ |   0 No, only Floydsss's.
 » 11 months ago, # | ← Rev. 2 →   +29 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.
•  » » 11 months ago, # ^ |   +11 We can add 2D fft with points (black, white) and get O(N/(N-log(N)/log(N)/log(N))
•  » » 11 months ago, # ^ |   +26 Thank you. Got AC.BTW if you use 3D logarithmic bitset in #1 you can drop complexity to O(N/(N-1.678))
 » 2 months ago, # |   0 Hi, I know I am late , but I was solving this problem all I could think of was a O(P *sqrt(N)) solution ( sqrt decomposition)...Can you tell me what your segment tree approach was?! I can seem to get a segment tree solution
•  » » 2 months ago, # ^ |   0 Sorry, nevermind , solved it now!