kingofnumbers's blog

OILCOMP spoj.
By kingofnumbers, 12 years ago, In English

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.

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

Comments Comments (15)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm also interested for learning two mentioned approaches for this problem. anyone help please :)

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain where fib(W) comes from?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it means Wth-number from fibonacci sequence

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No, i asked why there will be at most fib(W) different masks?

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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];

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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 

                #include <iostream>
using namespace std;
int bitmask_to_rank[2<<20],number_of_good_bitmask=0;
int rank_to_bitmask[2<<20];
int main(){
	for(int i=0;i<(2<<20);i++){
		if(is_good_bitmask(i)){
			bitmask_to_rank[i]=number_of_good_bitmask;
			rank_to_bitmask[number_of_good_bitmask]=i;
			number_of_good_bitmask++;
		}
	}
	// declare array with size 2*H*number_of_good_bitmask here after calculating number_of_good_bitmask
}

                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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                  ← Rev. 3   Vote: I like it 0 Vote: I do not like it

                  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

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                  ← Rev. 3   Vote: I like it +5 Vote: I do not like it

                  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).

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                  ← Rev. 3   Vote: I like it 0 Vote: I do not like it

                  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:

                  1010
1001

                  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

                  → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            becuase fib(W)=fib(1)+fib(2)+fib(3) ... fib(W-2)+1

            → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 :(

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply