KMHAMHA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kaushik Iska
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Vertex cover, König’s theorem, Hopcroft–Karp algorithm

PROBLEM:

Given a set of points S in a rectangular grid, find the size of the smallest set T containing rows and columns such that for each point in S either its row or column is in the selected set T.

QUICK EXPLANATION:

The problem can be reduced to finding the size of the optimum vertex cover in a bipartite graph, which can then be computed using Hopcroft-Karp algorithm.

EXPLANATION:

We are given a set of points S, where the demons stand in the beginning. In a single attack Goku can kill all demons in a single row or in a single column.

Since Goku wants to kill all demons, for each demon he must call an attack either on its row or on its column. Hence, the problem is equivalent to find a set T of smallest size containing rows and columns, such that for each demon standing on the point (Rx, Cy) either Rx is in the set T, or Cy is in the set T.

Reduction into vertex cover:

The problem can be easily reduced to finding the optimum vertex cover in a bipartite graph. Let us create a bipartite graph G = (R, C, E), where the vertices on the left side R correspond to rows of the grid, and the vertices on the right side C correspond to the columns of the grid. For each demon standing at point (Rx, Cy) create an edge between the vertex Rx and Cy.

For example, if we have 4 demons standing at (1, 8), (5, 6), (3, 8), (5, 4), we will end with the following bipartite graph:

R = {1, 3, 5}
C = {4, 6, 8}
E = {(1, 8), (5, 6), (3, 8), (5, 4)}

Here each demon is represented by an edge, and in order to kill that demon Goku must pick at least one of its two incident vertices, and call an attack on the picked row (or column), e.g., in order to kill the demon standing at (5, 6) he must attack either Row 5, or Column 6.

In other words, we want to find a set T of smallest size of vertices in the created bipartite graph such that for each edge, one of its incident vertices is in T. Such a set is called vertex cover of the graph.

Finding the Vertex cover:

Finding the optimum vertex cover in a general graph is an NP-hard problem. However, for a bipartite graph the problem can be solved in polynomial time thanks to König’s theorem which states that the size of the vertex cover in a bipartite graph is the same as the size of the maximum matching.

Finding the maximum matching in a bipartite graph is a well known problem, and can be solved in O (E√N) time using Hopcroft–Karp algorithm, where N is the number of vertices and E is the number of edges.

In our problem the number of edges is the same as the number of demons (N). The number of vertices can be at most 2N (N rows and N columns), as each edge will create at most two new vertices.

Use of hash map to create the graph:

In the problem each of the Rx and Cy can be as large as 109. However, there are at most N such values. Hence, one can assign a unique id in [1, N] to each Rx and Cy. A hash map can be used to ensure that the same values of Rx (and Cy) are assigned the same id.

Time Complexity:

O (N1.5)

Weak test cases:

Unfortunately, the test cases for this problem were weak, and allowed greedy solutions to pass. This was pointed out by many participants during the contest. We added new test cases to avoid the false positives, but still there were many solutions which are using greedy and randomized algorithm and are being accepted.

Here is one test case which helped us removing many false positives
1
15
0 0
0 1
0 2
1 0
1 3
1 4
2 0
2 5
2 6
3 0
3 7
3 8
4 9
5 9
6 9

The correct answer is 5, however many accepted solutions were providing 6 as answer.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution can be found here.

27 Likes

can’t it be solved by dp?

6 Likes

code for visualizing points on the graphs
alt text

8 Likes

Hi Ajay, Can you please give the test case failed by my code http://www.codechef.com/viewsolution/2826193 . It passes the above test case.

hello please look into my solution and tell me at which case is my solution failing.
My solution http://www.codechef.com/viewsolution/2828457
It is getting right answer for the given case but still its failing somewhere.

2 Likes

my code is giving 5 for the give test case and i verified it for many test cases it gave correct answer, still my code was not AC during the contest
http://www.codechef.com/viewsolution/2820678
if anyone can point out the problem, that would be great

Thanks

How would it be solved if the number of demons are around 10^8 or 10^9 ??

Here is a case where ur code goes wrong: http://pastie.org/8401415

Answer should be 3

ur ouput is 4

1 Like

http://www.codechef.com/viewsolution/2823452

it would be nice if anyone could give me a test case where my code fails. It’s giving correct results for above test case and all the others in comment section of the problem

I am not able to get the Routine by tester can someone provide me a good source to get this concept ,please!

inline bool augment(int x)
    {
        for (int i = 0; i < adj[x].size(); ++ i) {
            int y = adj[x][i];
            if (mark[y] == stamp) {
                continue;
            }
            mark[y] = stamp;
            if (match[y] == -1 || augment(match[y])) {
                match[y] = x;
                return true;
            }
        }
        return false;
    }

hashing is the only solution i guess.you need to map the higher values to lower values as the input of demons is maximum 1000.

Yash I ran your code for test case given in editorial it outputs 6.

1 Like

@anu1234 The notion of augmenting path is explained here http://en.wikipedia.org/wiki/Matching_(graph_theory)

hey vikrant1433. plz suggest a testcase for my solution. Its giving correct answer http://www.codechef.com/viewsolution/2828457. I dont know what is wrong.

@tibip i am getting augmenting path an alternating path having start and end point free. But i am not getting it’s implementation ,I need explanation.At wikipedia it is quit confusing to me get the implementation .Please help me!

i got !! thanx :slight_smile:

http://www.codechef.com/viewsolution/2828457 please tell me where my solution goes wrong.

hi admin,
my code is working fine for all above mentioned testcases can you give me any testcase for which it is failing.
http://www.codechef.com/viewsolution/2821524

hi admin, my code is working fine for all above mentioned testcases can you give me any testcase for which it is failing. http://www.codechef.com/viewsolution/2821524

I did not know about any of the algorithms mentioned in the prerequisites but was able to arrive at a pretty simple logical solution. Thought I’d share it.

For killing any demon either its row has to be destroyed or its column. Now if a demon is alone in its row ie. there is only one demon in that row, then destroying that row would be useless as one attack will kill only one demon. So in that case the column will be destroyed for that particular demon. It does not matter how many demons are there in that column because this attack will kill one or more demons instead of only one if we used the attack on the row. Similarly for a column having only one demon, the optimal way will be to destroy the corresponding row for that demon instead of the column.
So the basic form of the program will be :

  • keep a count of demons for all rows and columns.
  • do this until every row has more than one demon : if a row has a single demon(say ith row and jth column) then all the demons in the jth column will be destroyed. Count for that column will become 0 and update the count for all the rows. The answer will be incremented by 1.
  • repeat step 2 for the columns so that all columns have more than one demon now.
  • Now every column and every row has more than one demon. All we need to do now is find the minimum of ( no. of rows with atleast one demon , no.of columns with atleast one demon) and add this to the answer calculated before.

Implementation was a little tricky but fortunately got AC on first try. Here is the solution
http://www.codechef.com/viewsolution/2795618

4 Likes