loboelita's blog

Facebook HackerCup: Problem 2

By loboelita, history, 9 years ago, In English

https://www.facebook.com/hackercup/problem/1527664744192390/

I know how to solve this problem using Dp and greedy. But I am interested in knowing how to solve this problem using Maxflow. Can someone please help me out?

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

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'd like to know how it would be solved using DP approach? I couldn't think about how the problem would be divided into sub-problems.

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

    Processing the map from left to right, we need to keep track if there is a guard placed behind us (to the left) on the top row and bottom row.

    If there isn't and this is a free square, we need to place one guard. Then we need to do some case analysis depending on the top and bottom squares being free or not.

    The caveat is that we need to pick carefully when a guard is controlling a square above/below his row. I used 3 states for each of the rows: NONE = no guard, HAS_USED = placed a guard and it is guarding a row above/below him, HAS = I need to place a guard here. Take a look at this example:

    ...#.#
......

    We need to place a guard both on the top and bottom rows, but we can preserve both rows with "HAS" state. Then, when we process the second to last column, we assign that square to the guard on the bottom row.

    This takes O(N). Here's my code http://ideone.com/Q1ebEu

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

    Another way to solve it with dp, with O(N^2) complexity — DP[i][j] is for smallest number of guards needed to cover i cells in first row and j cells in second row. When trying to extend your state, you can either move by 1 cell for free, if that cell contains #, or cover that cell by placing guard either in this cell or in matched cell in other row (just don't forget to update information about covered cells in other row). Code.

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

Maybe they meant the following:

The first part is the same as greedy solution. After you find "segments", construct a bipartite graph. Left vertices correspond to segments on the top row. Right vertices correspond to segments on the bottom row. Then, add an edge between a left vertex and a right vertex iff the corresponding segments share an edge and exactly one of them has length one. Compute bipartite matching of this graph.

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

    Actually it is the same with greedy approach. Because each segment of length one will have degree at most one, so the MM can be found greedy.

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

    Is the same problem on a NxM grid solvable in polynomial time?

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

    Then, add an edge between a left vertex and a right vertex iff the corresponding segments share an edge and exactly one of them has length one.

    Why exactly one of them should have length one? even if both of them have length one, we will still need to do a bipartite matching of them. The answer is then, the no. of segments in the grid-the result we find from bipartite matching.

    Please tell me where am I going wrong in this.

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

      Yes, you are correct. It should be "at least one".

      → Reply