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

dp bitmask or greedy
Автор babak, 13 лет назад, По-английски

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. :-)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Jury's solution has complexity O(2^n).
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Flow actually.
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.



    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      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.
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        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.
        → Ответить
»
13 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
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.
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится
    Edit:you can't bomb more than N times so complexity is O(number of bombs*N^2)=O(N^3)
    → Ответить