babak's blog

dp bitmask or greedy
By babak, 13 years ago, In English

I solved this problem with dp bitmask but when I saw this I knew that it may has a better solution , maybe greedy.


but I cannot find any greedy approach for this problem.

tnx for any hints about it. :-)
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Flow actually.
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
A bipartite matching between bomb position and rocks sud work i guess.

A greedy approach could be , find which cell destroys maximal numbers of rocks in each iteration until all are destroyed.
But I cannot prove correctness.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The bipartite matching is actually between the rows and columns. Whenever you pick a cell you destroy all cells in that row and that column (or one matching). The maximum matching is equal to the minimum bombs used. You place an edge for each rock location (i,j) between row i and column j. (two sides of the bipartite matching) 

    I don't believe your greedy is optimal intuitively but I'm having difficult time forming a counterexample. I think the fastest solutions use this matching idea.



    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      The greedy is suboptimal where all greedy solutions are suboptimal: when there are multiple equally right possibilities.

      x000
      xx00
      00x0
      0xx0

      Now, moves (row, column): (1, 0), (1, 1), (3, 1) and (3, 2) will all get 3 pieces.
      But, if you make (1,0) or (3, 2), you can finish in two moves.
      If you take the other ones, you will need 3. And there's no way for a greedy solution to know which one to take.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it
        Excellent counter example, as for my bipartite matching idea I think it is incorrect as well because I messed up reducing this problem. My guess is the fast solutions are turning the dp solution into a bfs and not all states are then reached improving the average case or they are using branch and bound with the heuristic.
        → Reply
»
13 years ago, # |
  Vote: I like it -12 Vote: I do not like it
Let count[i][j] be the number of rocks you destroy if you bomb [i][j].You can do this easily in O(N^2)


While the number of rocks is greater than 0
{
     find max in matrix count[][]
    bomb that possition
   re-initilize\update count[][]     
}          

There's your greedy.

Complexity O(N^4) and since N<25 its no biggie.  

Pretty sure there's no counter example for this.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it
    Edit:you can't bomb more than N times so complexity is O(number of bombs*N^2)=O(N^3)
    → Reply