Блог пользователя kingofnumbers

Автор kingofnumbers, 12 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain where fib(W) comes from?

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        it means Wth-number from fibonacci sequence

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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?

              • »
                »
                »
                »
                »
                »
                »
                »
                11 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                  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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                  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

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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