Hi,
I need help to solve this problem http://www.spoj.pl/problems/OILCOMP/
in this problem we 2D array A[H][W] and we need to select elements of the array without selecting any two neighbor elements and maximize the sum of the elements selected.
the neighbors of element A[ i ][ j ] is A[ i-1 ][ j ] , A[ i+1 ][ j ] , A[ i ][ j-1 ] , A[ i ][ j+1 ].
I heard that this problem can be solved two ways, the first is network flow and the second is dp with bitmasks
I need to know both ways please.
I'm also interested for learning two mentioned approaches for this problem. anyone help please :)
One approach could be to pre-compute all possible bitmasks of H rows and 2 columns s.t. no 2 adjacent bits are one. The number of such bitmasks is less than Fib(20)*Fib(20) {Fib(i) is the ith Fibonacci number). However, I expect the number of such bitmasks to be much less than Fib(20)*Fib(20).
Now, its easy to propagate information from the 1st i columns to the 1st i+1 columns. Let DP[i][mask] denote the maximum fuel possible considering the 1st i columns, such that the configuration of the ith column is given by 'mask'. For DP[i+1][], we need to try out all our H*2 bitmasks. For example, if a H*2 bitmask is [mask1 in column 1][mask2 in column 2], then DP[i+1][mask2] is max(DP[i+1][mask2], DP[i][mask1]+fuel[i+1][mask2]). fuel[i+1][mask2] is the amount of fuel available from column i+1 if only the bits set in mask are used.
Also there can be used "Broken-profile dynamic programming". I don't know for sure how it is called in English.
You don't need to store two entire rows. let's fill table rows, from top to bottom, and each row fill from left to right. for x 0 to H — 1, for y 0 to W — 1. Now we are at cell (x, y) we need to know cells (x, 0),(x, 1),...,(x, y-1), (x-1, y), (x-1,y+1)...(x-1,W-1) Paint some images and mark this cells on paintings to understand what i am talking about. (image H = 7, W = 7, x = 3, y = 3). on this step we have to try set value of cell (x, y) to 0, and to 1. In both cases we go to the cell (x, y + 1). Paint this picture too x = 3, y = 4. each profile contains bitmask of length W, but there will be about fib(W) different masks. complexity is H * W * fib(W)
Can you explain where fib(W) comes from?
it means Wth-number from fibonacci sequence
No, i asked why there will be at most fib(W) different masks?
because we can't select any two neighbor elements. try to solve the same problem for one row. dp[i] = dp[i — 1] + dp[i — 2];
thanks. Another problem is memorizing. Though i need H * W * fib(W) memory, i need to declare 20*20*(2^20) size array for memorization because i dont know in advance which masks are needed. What is the trick in these situations?
first you don't need H*W*fib(W) because every dp for every row is dependent on previous row only so only 2*W*fib(W) is needed ,
morever you can only declare 2*20*fib(20) only
after calculating "number_of_good_bitmask" you can declare array with size 2*H*number_of_good_bitmask
then you have to use ranks of bitmasks instead of bitmask itself in this array
if you want to know what is the rank of some bitmask use bitmask_to_rank
if you want to know what is the bitmask of some rank use rank_to_bitmask
So, if you have fib(20) good bitmasks in each row, then for each row entry you have to check against each entry in the previous row for the highest value, that's O(fib20*fib20*20), right? But that's like over 6 billion operations in the 20x20 case.
What am I overlooking?
Appreciated, Derek
According to post by alias, the bits you need to keep track of looks like this:
row1-> "....bbbb"
row2-> "bbbbx..."
x is your current position, and "b" are the bits you need to know. so the state is (current row, current col, mask). At each step you can place either 0 or 1(if valid) and As there are fib(20) different bits total complexity is 20*20*fib(20).
replying to dillchuk
there's also one extra optimization
note that not all pairs of good bitmasks are good pairs for example 1010,1001 are two good bitmasks but we combining those two bitmasks we have:
this is not good because we have two adjacent 1-bits
so pre-compute all good pairs of good bitmasks and then you have O(20*good_pairs) solution
good_pairs is equal to 27,304,196
fib(20)*fib(20) is equal to 313,679,521
becuase fib(W)=fib(1)+fib(2)+fib(3) ... fib(W-2)+1
Shouldn't it be fib(22) instead of fib(20) since it's the sum of fib(1->20) = fib(20+2)-1? the number of good pairs by me is 54,608,393 (ordered pairs) and I'm getting TLE for 20 * 54608393 + pre-calculation :(
I knew how to solve it using flows ,here is how:
let's constuct a graph for every cell in input grid we have a node in this graph having weight equal to value of that cell
for every node we connent it by edges with nodes that adjacent to corresponding cell
now our problem is reduced to find maximum-weight independent set in this graph but it's NP-hard problem in general graphs,
but we can see that we have a bipartite graph , all nodes that have i+j is odd in one side and all nodes that have i+j even in the other side
so, finding maximum-weight independent set can be done using flows